[Seite 204↓]

Appendix B – Ein Algorithmus zur Bestimmung von Pfaden zwischen zwei gegebenen Knoten

import java.sql.*;
public class DetermineDemo{
static BitNode[] nodes;
static int nnodes;
static int act_maxperm;
/** Connection to sql database. */
static Connection conn;
static boolean real_max = true;
/** ID database name. */
static String iddb = "wordweb_ids";
/** Name of relation database. */
static String reldb = "wordweb_rel";
/** Main Determination function. */
public static int[] determine(int webnr, int id1, int id2, int len, int min_resist){
nodes = new BitNode[100000];
nnodes = 0;
int act_len = 1;
int halflen = (int) Math.floor((double)len/2f);
int[] oldleft = new int[1];
int[] oldright = new int[1];
int[][] nextleft = null;
int[][] nextright = null;
oldleft[0] = id1;
oldright[0] = id2;
getMaxPerm(webnr);
for(int j=0;j<halflen;j++){
					
[Seite 205↓]// shoot left
for(int k=0;k<oldleft.length;k++){
nextleft = getReachableBroth(webnr,oldleft[k],min_resist,false);
if(nextleft == null) continue;
for(int i=0;i<nextleft.length;i++){
nodeReached(nextleft[i][0], nextleft[i][1], act_len,true);
}
}
if(nextleft == null) return null;
oldleft = new int[nextleft.length];
for(int k=0;k<nextleft.length;k++){
oldleft[k] = nextleft[k][0];
}
// shoot right
for(int k=0;k<oldright.length;k++){
nextright = getReachableBroth(webnr,oldright[k],min_resist,false);
if(nextright == null) continue;
for(int i=0;i<nextright.length;i++){
nodeReached(nextright[i][0],nextright[i][1], act_len,false);
}
}
if(nextright == null) return null;
oldright = new int[nextright.length];
for(int k=0;k<nextright.length;k++){
oldright[k] = nextright[k][0];
}
act_len++;
}
// find possible centers
int[] poss_center_broth = new int[nnodes];
					
[Seite 206↓]int nposs = 0;

				
for(int i=0;i<nnodes;i++){
// odd
if(2*halflen != len){
// node bits match ...
if((nodes[i].left & halflen) == halflen && (nodes[i].right & halflen) == halflen) {
if(nodes[i].id != id1 && nodes[i].id != id2){
poss_center_broth[nposs] = i;
nposs++;
}
}
}
}
int[] way = new int[len];
way[0] = id1;
way[len-1] = id2;
while(true){
// select one
if(nposs == 0) return null;
int choice = getRdUpTo(nposs);
way[halflen] = nodes[poss_center_broth[choice]].id;
int act_left = nodes[poss_center_broth[choice]].id;
int act_right = nodes[poss_center_broth[choice]].id;
boolean poros = true;
// find way back
for(int i= halflen -1;i>0;i--){
int[] back_left = getWayBroth(webnr, act_left, i, true, min_resist, way);
if(back_left.length == 0) {
					
[Seite 207↓]// delete center, backleft circle
if(choice != poss_center_broth.length-1){
System.arraycopy(poss_center_broth , choice + 1 , poss_center_broth , choice, poss_center_broth.length - choice - 1);
}
poss_center_broth[choice] = 0;
nposs --;
poros = false;
break;
}
choice = getRdUpTo(back_left.length);
act_left = nodes[back_left[choice]].id;
way[i] = nodes[back_left[choice]].id;
int[] back_right = getWayBroth(webnr, act_right, i, false, min_resist, way);
if(back_right.length == 0) {
// delete center, backright circle
if(choice != poss_center_broth.length-1){ 
System.arraycopy(poss_center_broth , choice + 1 , poss_center_broth , choice, poss_center_broth.length - choice - 1);
}
poss_center_broth[choice] = 0;
nposs --;
poros = false;
break;
}
choice = getRdUpTo(back_right.length);
act_right = nodes[back_right[choice]].id;
way[len-1-i] = nodes[back_right[choice]].id;
}
if(poros){
					
[Seite 208↓]return way;
} 
}
}
/** Update the value for the highest permeability in this web. */
public static int getMaxPerm(int webnr) {
int max_perm = -1;
try{
if(conn == null){ 
executeConnect("localhost","3306","username","password",“dbname“);
}
Statement stmt = conn.createStatement();
String q ="";
if (real_max) q ="select max(resist) from "+reldb+webnr+","+iddb+" as ID1, "+iddb+" as ID2 where (id_1 = ID1.id and ID1.type not like 0) and (id_2 = ID2.id and ID2.type not like 0)";
else q = "select max(resist) from "+reldb+webnr;
ResultSet rs = stmt.executeQuery(q);
boolean hasMore = rs.next();
if (hasMore) {
max_perm = rs.getInt(1);
}
stmt.close();
act_maxperm = max_perm;
return max_perm;
}
catch (SQLException ex){System.err.println("E>>>in getmaxperm, web"+webnr+" "+ex);}
return -1;
}
/** Get all neighbours of the word for <i>id1</i> that have a permeability bigger than [Seite 209↓]<i>min_resist</i>. In the array returned int[0] is the ID of the neighbour, int[1] is the permeability to the neighbour. */
public static int[][] getReachableBroth(int webnr, int id1, int min_resist, boolean update_perm) {
int[][] ret;
Statement stmt = null;
int max_perm = act_maxperm;
if(update_perm) max_perm = getMaxPerm(webnr);
try{
if(conn == null){ 
executeConnect("localhost","3306","username","password",“dbname“);
}
stmt = conn.createStatement();
String q = "select count(*) from "+reldb+webnr+" where (((id_1 = "+id1+") or (id_2 = "+id1+" ))) and resist > "+min_resist;
ResultSet rs = stmt.executeQuery(q);
boolean hasMore = rs.next();
if (hasMore) {
int mass = rs.getInt(1);
if(mass == 0){
stmt.close();
return null;
}
ret = new int[mass][2];
int nret = 0;
q = "select id_1,id_2,resist from "+reldb+webnr+" where (((id_1 = "+id1+") or (id_2 = "+id1+" ))) and resist > "+min_resist+" order by resist desc";
rs = stmt.executeQuery(q);
hasMore = rs.next();
while (hasMore) {
int one = rs.getInt(1);
					
[Seite 210↓]if (one != id1) {
ret[nret][0] = one;
}
else {
int two = rs.getInt(2);
ret[nret][0] = two;
} 
//return relative perm;
ret[nret][1] = Math.round((float)rs.getInt(3)*100f/(float)max_perm);
nret++;
hasMore = rs.next();
}
stmt.close();
return ret;
}
else {
stmt.close();
return null;
}
}catch(SQLException ex){
System.err.println(ex);
}finally{try{stmt.close();}catch(SQLException exx){};}
return null;
}
/** Construct a BitNode object for every node reached */
public static void nodeReached(int id, float power, int len, boolean fromleft){
for(int i=0;i<nnodes;i++){
if(nodes[i].id == id) {
nodes[i].reached(len,fromleft,power);
return;
					
[Seite 211↓]}
}
nodes[nnodes] = new BitNode(id);
nodes[nnodes].reached(len,fromleft,power);
nnodes++;
}
/** Follow the way back to the start and end nodes. */
public static int[] getWayBroth(int webnr, int id, int len, boolean toleft, int min_resist, int[] without){
int[][] broth = getReachableBroth(webnr,id,min_resist,false);
int[] tempbroth = new int[broth.length];
int nbroth = 0;
for(int j=0;j<broth.length;j++){
// translate db id into bitnode array id
int bnr = findNode(broth[j][0]);
if(bnr == -1) continue;
if(nodes[bnr].wasReachedBy(len,toleft)){
boolean circle = false;
// don't take neighbours already in way ... == without
for(int i=0;i<without.length;i++){
if(without[i] == broth[j][0]) {
circle = true;
break;
}
}
if(circle) continue;
tempbroth[nbroth] = bnr;
nbroth++;
} 
}
					
[Seite 212↓]int[] retbroth = new int[nbroth];
System.arraycopy(tempbroth,0,retbroth,0,nbroth);
return retbroth;
}
/** Translate global node id into position in BitNode-array */
public static int findNode(int id){
for(int i=0;i<nnodes;i++){
if(nodes[i].id == id) {
return i;
}
}
return -1;
}

				
/** Get a word for an ID from ID database. */
public static String lookup(int id) {
String ret = "";
try {
Statement stmt = conn.createStatement();
ResultSet rs = stmt.executeQuery("select word from "+iddb+" where id = "+id);
boolean hasMore = rs.next();
if (hasMore){
ret= rs.getString(1);
}
stmt.close();
}catch (SQLException ex) {System.err.println(ex);}
return ret;
}
/** Lookup the resistency between two nodes. */
private static int getResist(int webnr, int id1, int id2){
					
[Seite 213↓]try{
if(conn == null){
executeConnect("localhost","3306","username","password",“dbname“);
}
Statement stmt = conn.createStatement();
ResultSet rs = stmt.executeQuery("select id,resist from "+reldb+webnr+" where (id_1 = "+id1+" and id_2 = "+id2+") or (id_1 = "+id2+" and id_2 = "+id1+")");
boolean hasMore = rs.next();
//already in DB **********************************
if (hasMore){
String id = rs.getString(1);
int act_resist = rs.getInt(2);
return act_resist;
}
// NEW ***************************************************
else { 
return -1;
}
}catch (SQLException ex){System.err.println(ex);}
return -1;
}
/** Get a random number up to a */
public static int getRdUpTo(int a) {
int rd = (int) (Math.random()*(float)a);
return rd;
}
/** Connect to SQL database */
private static void executeConnect(String host, String port, String user, String password, String database){
try{
Class.forName ("twz1.jdbc.mysql.jdbcMysqlDriver");
					
[Seite 214↓]StringBuffer bufferURL = new StringBuffer();
bufferURL.append("jdbc:z1MySQL:");
if (host != null && host.length() != 0){
bufferURL.append("//" + host);
if (port != null && port.length() != 0)
bufferURL.append(":" + port + "/");
else
bufferURL.append("/");
}
else if (port != null && port.length() != 0){
bufferURL.append("//localhost:" + port + "/");
}
bufferURL.append(database);
if (user == null || user.length() == 0)
user = System.getProperty("user.name");
bufferURL.append("?user=" + user);
if (password == null)
password = "";
bufferURL.append(";password=" + password);
String url = new String(bufferURL);
System.out.println("Connecting to "+url);
conn = DriverManager.getConnection (url);
}catch (SQLException e){
System.out.println (e.getMessage ());
e.printStackTrace();
//System.exit(1);
}catch (Exception e){
e.printStackTrace();
//System.exit(1);
}
					
[Seite 215↓]}
/** Main method. Mainly for testing. */
public static void main(String[] args) {
int webnr = 9;
int[] way = DetermineDemo.determine(webnr,152,150,5,2);
if(way == null) {
System.out.println("APOROS");
return;
}
for(int i=0;i<way.length;i++){
System.out.print(DetermineDemo.lookup(way[i])+"("+way[i]+") ");
if(i != way.length-1) System.out.print(" = " + DetermineDemo.getResist(webnr, way[i], way[i+1]) + " = ");
}
System.out.println();
}
/** INNER CLASS BITNODE - represents a node. Stores the length of the way needed to reach it in the two bytes „left“ and „right“ */
public static class BitNode {
int id;
byte left, right;
float left_cheapest, right_cheapest;
/** Construct BitNode with id */
public BitNode(int id){
this.id = id;
}
/** Tells if this node was reached by a shot of a certain length from left or right.*/
public boolean wasReachedBy(int len, boolean fromleft){
int binlen = 1;
for(int i=0;i<len-1;i++){
					
[Seite 216↓]binlen*=2;
} 
if(fromleft) { 
return ((left & binlen) == binlen);
}
else {
return ((right & binlen) == binlen);
}
}
/** Sets the bits that save the information that this Node was reached by a shot from left or right with a certain length. */
public void reached(int len, boolean fromleft){
int binlen = 1;
for(int i=0;i<len-1;i++){
binlen*=2;
} 
if(fromleft) {
left |= binlen;
}
else {
right |= binlen;
}
}
/** Sets the bits that save the information that this Node was reached by a shot of a certain power from left or right with a certain length. */
public void reached(int len, boolean fromleft, float power){
int binlen = 1;
for(int i=0;i<len-1;i++){
binlen*=2;
} 
if(fromleft) {
					
[Seite 217↓]left |= binlen;
if(power > left_cheapest) left_cheapest = power;
}
else {
right |= binlen;
if(power > right_cheapest) right_cheapest = power;
}
}
}// EOF INNER CLASS
}


© Die inhaltliche Zusammenstellung und Aufmachung dieser Publikation sowie die elektronische Verarbeitung sind urheberrechtlich geschützt. Jede Verwertung, die nicht ausdrücklich vom Urheberrechtsgesetz zugelassen ist, bedarf der vorherigen Zustimmung. Das gilt insbesondere für die Vervielfältigung, die Bearbeitung und Einspeicherung und Verarbeitung in elektronische Systeme.
XDiML DTD Version 4.0Zertifizierter Dokumentenserver
der Humboldt-Universität zu Berlin
HTML-Version erstellt am:
15.04.2005