| 1 |
package tools; |
| 2 |
|
| 3 |
import java.sql.*; |
| 4 |
import java.io.*; |
| 5 |
import java.util.*; |
| 6 |
|
| 7 |
/* find the maximum Spanning Tree structure data |
| 8 |
author: Michael Lappe, 2005-04-15 |
| 9 |
*/ |
| 10 |
|
| 11 |
public class calcMST |
| 12 |
{ |
| 13 |
|
| 14 |
static int graphIDX, reportLevel=0, pre_num=0, act_num=0, root_num=0; |
| 15 |
static String pre_cid="", act_cid="", root_cid=""; |
| 16 |
static Connection C = null; // The Connection to the SQL-database |
| 17 |
|
| 18 |
public static void setConnection( Connection xC) { C = xC; } |
| 19 |
|
| 20 |
public static void setRootCID( String CID) { root_cid = CID; } |
| 21 |
public static String getRootCID() { return root_cid; } |
| 22 |
|
| 23 |
public static void setRootNUM( int NUM) { root_num = NUM; } |
| 24 |
public static int getRootNUM() { return root_num; } |
| 25 |
|
| 26 |
public static void setGraphIDX( int GIDX) { graphIDX = GIDX; } |
| 27 |
public static int getGraphIDX() { return graphIDX; } |
| 28 |
|
| 29 |
|
| 30 |
/** Sets the reportLevel, so that only messages below or equal the level given are displayed. |
| 31 |
The following levels are available: (0 is default - no messages) |
| 32 |
3 - talkative mode |
| 33 |
2 - normal mode |
| 34 |
1 - basic mode |
| 35 |
0 - silent mode |
| 36 |
This means by a higher level you get more detailed information, while on a reportLevel |
| 37 |
of 0 only the most basic results and errors are displayed */ |
| 38 |
public static void setReportLevel( int newLevel) { reportLevel = newLevel; } |
| 39 |
/** gets the currently set reportLevel */ |
| 40 |
static int getReportLevel() { return reportLevel; } |
| 41 |
|
| 42 |
static void report(String text, int level) { |
| 43 |
if (level<=reportLevel) { |
| 44 |
System.out.print( text); |
| 45 |
} // end if level of the curent message is above the current level |
| 46 |
} // end of report |
| 47 |
|
| 48 |
static void reportln(String text, int level) { |
| 49 |
if (level<=reportLevel) { |
| 50 |
System.out.println( text); |
| 51 |
} // end if level of the curent message is above the current level |
| 52 |
} // end of report |
| 53 |
|
| 54 |
|
| 55 |
public static void initSums() { |
| 56 |
try { |
| 57 |
|
| 58 |
reportln("Total Sums for Graph IDX#"+getGraphIDX()+" are initialised.", 2); |
| 59 |
Statement S; |
| 60 |
S = C.createStatement(); |
| 61 |
S.executeQuery( "update spath_nodes set used_total=0, dist_total=0, reached=0 where IDX="+getGraphIDX()+";"); |
| 62 |
S.close(); |
| 63 |
|
| 64 |
S = C.createStatement(); |
| 65 |
S.executeQuery( "update spath_edges set used_total = 0 where IDX="+getGraphIDX()+";"); |
| 66 |
S.close(); |
| 67 |
} catch (SQLException E) { |
| 68 |
System.out.println("SQLException:\t" + E.getMessage()); |
| 69 |
System.out.println("SQLState:\t" + E.getSQLState()); |
| 70 |
System.out.println("VendorError:\t" + E.getErrorCode()); |
| 71 |
} |
| 72 |
} // end initStartTable() |
| 73 |
|
| 74 |
|
| 75 |
/** Initialising the calculation by first emptying all status and then marking adjacent edges |
| 76 |
of the start-node as Q |
| 77 |
back-edges to the start node are excluded by marking them as B |
| 78 |
*/ |
| 79 |
public static void initCounts() { |
| 80 |
reportln("Counts for Graph IDX#"+getGraphIDX()+" are initialised.", 2); |
| 81 |
try { |
| 82 |
// empty the edge table |
| 83 |
Statement S = C.createStatement(); |
| 84 |
S.executeQuery( "UPDATE spath_edges set i_stat=\'R\', j_stat=\'R\', used=0 where IDX="+getGraphIDX()+";"); |
| 85 |
// and Initialise it with the start node |
| 86 |
S = C.createStatement(); |
| 87 |
S.executeQuery( "UPDATE spath_nodes set stat=\'R\', pre_cid=\"\", pre_num=0, used=0, dist=0 where IDX="+getGraphIDX()+";"); |
| 88 |
|
| 89 |
} catch (SQLException E) { |
| 90 |
System.out.println("SQLException:\t" + E.getMessage()); |
| 91 |
System.out.println("SQLState:\t" + E.getSQLState()); |
| 92 |
System.out.println("VendorError: \t" + E.getErrorCode()); |
| 93 |
} |
| 94 |
} // end |
| 95 |
|
| 96 |
|
| 97 |
public static void addSums() { |
| 98 |
try { |
| 99 |
Statement S; |
| 100 |
|
| 101 |
S = C.createStatement(); |
| 102 |
S.executeQuery( "update spath_nodes set used_total=used_total+used, dist_total=dist_total+dist where IDX="+getGraphIDX()+";"); |
| 103 |
S.close(); |
| 104 |
|
| 105 |
S = C.createStatement(); |
| 106 |
S.executeQuery( "update spath_edges set used_total = used_total+used where IDX="+getGraphIDX()+";"); |
| 107 |
S.close(); |
| 108 |
} catch (SQLException E) { |
| 109 |
System.out.println("SQLException:\t" + E.getMessage()); |
| 110 |
System.out.println("SQLState:\t" + E.getSQLState()); |
| 111 |
System.out.println("VendorError:\t" + E.getErrorCode()); |
| 112 |
} |
| 113 |
} // end initStartTable() |
| 114 |
|
| 115 |
|
| 116 |
/** Performs the maximum Spanning Tree Calculation from the root |
| 117 |
*/ |
| 118 |
public static void performMST() { |
| 119 |
int rootdist = 1; |
| 120 |
initCounts(); |
| 121 |
act_cid = getRootCID(); |
| 122 |
act_num = getRootNUM(); |
| 123 |
pre_cid = act_cid; |
| 124 |
pre_num = act_num; |
| 125 |
reportln("Performing MaximumSpanningTree (MST) calculation from root node ["+act_cid+":"+act_num+"]", 2); |
| 126 |
|
| 127 |
while (act_num > 0) { // while we get a NodeID out of Q |
| 128 |
report(".", 0); |
| 129 |
reportln( "\n----------------> ["+act_cid+":"+act_num+"]", 2); |
| 130 |
addNode2P( rootdist); |
| 131 |
backtrack(); |
| 132 |
followMaxEdgeP2Q(); // setting new (act & pre) cid:num |
| 133 |
reportln("new node is ["+act_cid+":"+act_num+"]", 3); |
| 134 |
rootdist = 0; // root to root distance correction only on first run |
| 135 |
} // end while there are nodes left in Q |
| 136 |
} // end of performMST |
| 137 |
|
| 138 |
/* |
| 139 |
get the distance of the predescessing node |
| 140 |
*/ |
| 141 |
public static int getPreDistance() { |
| 142 |
String Query; |
| 143 |
int distance = 0; |
| 144 |
try { |
| 145 |
if (! ( pre_cid.equals(root_cid) && (pre_num==root_num) ) ) { |
| 146 |
|
| 147 |
// getting the distance of the predecessor |
| 148 |
Statement S = C.createStatement(); |
| 149 |
Query = "select dist from spath_nodes where cid=\'"+pre_cid+"\' and num="+pre_num+" and IDX="+getGraphIDX()+" limit 1;"; |
| 150 |
// reportln( ">2P> "+Query, 3); |
| 151 |
ResultSet R = S.executeQuery( Query); |
| 152 |
if ( R.next()) distance = R.getInt( 1); |
| 153 |
R.close(); |
| 154 |
S.close(); |
| 155 |
} |
| 156 |
} catch (SQLException E) { |
| 157 |
System.out.println("SQLException:\t" + E.getMessage()); |
| 158 |
System.out.println("SQLState:\t" + E.getSQLState()); |
| 159 |
System.out.println("VendorError: \t" + E.getErrorCode()); |
| 160 |
} |
| 161 |
return distance; |
| 162 |
} // end |
| 163 |
|
| 164 |
|
| 165 |
/* |
| 166 |
Moving actual Node from Q to P |
| 167 |
*/ |
| 168 |
public static void addNode2P( int root) { |
| 169 |
String Query; |
| 170 |
reportln("adding node "+act_cid+":"+act_num+" to P", 2); |
| 171 |
try { |
| 172 |
// getting the distance of the predecessor |
| 173 |
int dist = getPreDistance()-root; |
| 174 |
// updating the actual Node |
| 175 |
Statement S = C.createStatement(); |
| 176 |
Query = "UPDATE spath_nodes set stat=\'P\', pre_cid=\'"+pre_cid+"\', pre_num="+pre_num+", reached=reached+1, dist="+(dist+1)+" where IDX="+getGraphIDX()+" and cid=\'"+act_cid+"\' and num="+act_num+";"; |
| 177 |
// reportln( ">2P> "+Query, 3); |
| 178 |
S.executeQuery( Query); |
| 179 |
// mark outgoing edges |
| 180 |
S = C.createStatement(); |
| 181 |
S.executeQuery( "UPDATE spath_edges set i_stat=\'P\' where i_cid=\'"+act_cid+"\' and i_num="+act_num+" and IDX="+getGraphIDX()+";"); |
| 182 |
S.close(); |
| 183 |
// mark incoming edges |
| 184 |
S = C.createStatement(); |
| 185 |
S.executeQuery( "UPDATE spath_edges set j_stat=\'P\' where j_cid=\'"+act_cid+"\' and j_num="+act_num+" and IDX="+getGraphIDX()+";"); |
| 186 |
S.close(); |
| 187 |
} catch (SQLException E) { |
| 188 |
System.out.println("SQLException:\t" + E.getMessage()); |
| 189 |
System.out.println("SQLState:\t" + E.getSQLState()); |
| 190 |
System.out.println("VendorError: \t" + E.getErrorCode()); |
| 191 |
} |
| 192 |
} // end |
| 193 |
|
| 194 |
|
| 195 |
static void followMaxEdgeP2Q() { |
| 196 |
|
| 197 |
reportln("\nRetrieving the max.edge P -> Q", 2); |
| 198 |
try { |
| 199 |
Statement S = C.createStatement(); |
| 200 |
|
| 201 |
ResultSet R = S.executeQuery("select i_cid, i_num, SC_SC, j_cid, j_num from spath_edges where IDX="+getGraphIDX()+" and i_stat=\"P\" and j_stat=\"R\" and SC_SC>0 order by SC_SC DESC limit 1;"); |
| 202 |
|
| 203 |
if ( R.next() ) { |
| 204 |
pre_cid = R.getString( 1); |
| 205 |
pre_num = R.getInt( 2); |
| 206 |
act_cid = R.getString( 4); |
| 207 |
act_num = R.getInt( 5); |
| 208 |
reportln("nextEdge ["+pre_cid+":"+pre_num+"] --("+R.getInt(3)+")--> ["+act_cid+":"+act_num+"]", 2); |
| 209 |
} else { |
| 210 |
pre_cid =""; |
| 211 |
pre_num = 0; |
| 212 |
act_cid =""; |
| 213 |
act_num = 0; |
| 214 |
} |
| 215 |
R.close(); |
| 216 |
S.close(); |
| 217 |
} catch (SQLException E) { |
| 218 |
System.out.println("SQLException:\t" + E.getMessage()); |
| 219 |
System.out.println("SQLState:\t" + E.getSQLState()); |
| 220 |
System.out.println("VendorError:\t" + E.getErrorCode()); |
| 221 |
} |
| 222 |
|
| 223 |
} // end followMaxEdgeP2Q() |
| 224 |
|
| 225 |
|
| 226 |
/** backtracking from actual node to root |
| 227 |
*/ |
| 228 |
|
| 229 |
static void backtrack() { |
| 230 |
int s_num=0, t_num=act_num, weight=0, dista, counter=0; |
| 231 |
String s_cid="", t_cid=act_cid, Query; |
| 232 |
Statement S, Stmt; |
| 233 |
ResultSet R, RS; |
| 234 |
reportln("backtracking path from ["+act_cid+":"+act_num+"] to root ["+root_cid+":"+root_num+"]", 3); |
| 235 |
reportln("#n target -(dist)-> source", 3); |
| 236 |
// report the path that we have found |
| 237 |
try { |
| 238 |
while ( !( s_cid.equals(root_cid) && (s_num==root_num) && t_cid.equals(root_cid) && (t_num==root_num)) ) { // while not back to root yet |
| 239 |
counter ++; |
| 240 |
Stmt = C.createStatement(); |
| 241 |
RS = Stmt.executeQuery( "select pre_cid, pre_num, dist from spath_nodes where IDX="+getGraphIDX()+" and cid=\'"+t_cid+"\' and num="+t_num+";"); |
| 242 |
if ( RS.next()) { // get the predecessor |
| 243 |
s_cid = RS.getString(1); // previous node cid |
| 244 |
s_num = RS.getInt(2); // previous node num |
| 245 |
dista = RS.getInt(3); // distance |
| 246 |
reportln("#"+counter+" ["+t_cid+":"+t_num+"] -("+dista+")-> ["+s_cid+":"+s_num+"]", 2); |
| 247 |
// increase usage source node |
| 248 |
S = C.createStatement(); |
| 249 |
S.executeQuery( "update spath_nodes set used = used+1 where IDX="+getGraphIDX()+" and cid =\'"+s_cid+"\' and num="+s_num+";"); |
| 250 |
S.close(); |
| 251 |
|
| 252 |
// increase usage edge |
| 253 |
S = C.createStatement(); |
| 254 |
S.executeQuery( "update spath_edges set used = used+1 where IDX="+getGraphIDX()+" and i_cid =\'"+s_cid+"\' and i_num="+s_num+" and j_cid =\'"+t_cid+"\' and j_num="+t_num+";"); |
| 255 |
S.close(); |
| 256 |
t_cid = s_cid; |
| 257 |
t_num = s_num; |
| 258 |
} else { |
| 259 |
reportln("\n",2); |
| 260 |
break; |
| 261 |
} // end if R.next() |
| 262 |
} // end while we haven't reached back to the source |
| 263 |
|
| 264 |
} catch (SQLException E) { |
| 265 |
System.out.println("SQLException:\t" + E.getMessage()); |
| 266 |
System.out.println("SQLState:\t" + E.getSQLState()); |
| 267 |
System.out.println("VendorError:\t" + E.getErrorCode()); |
| 268 |
} |
| 269 |
} // end of reportShortestPath() |
| 270 |
|
| 271 |
} // end class calcPathway |
