1
28 package demo.algo;
29
30
31 import demo.base.RandomGraphGenerator;
32 import y.algo.GraphChecker;
33 import y.algo.ShortestPaths;
34 import y.base.Edge;
35 import y.base.EdgeCursor;
36 import y.base.Graph;
37 import y.base.Node;
38 import y.base.NodeCursor;
39 import y.util.D;
40 import y.util.Timer;
41 import y.util.YRandom;
42
43
44
48 public class ShortestPathTest {
49 static long seed = 0;
50
51 private Timer timerA = new Timer( false );
52 private Timer timerB = new Timer( false );
53 private Timer timerC = new Timer( false );
54 private Timer timerD = new Timer( false );
55
56
59 public static void main( String[] args ) {
60 try {
61 seed = Long.parseLong( args[0] );
62 }
63 catch ( Exception ex ) {
64 }
65
66 (new ShortestPathTest()).doIt();
67
68 }
69
70 private void doIt() {
71 testSP( true );
72 testAllPairs( true );
73 testSingleSourceSingleSink( true );
74 testSP( false );
75 testAllPairs( false );
76 testSingleSourceSingleSink( false );
77 }
78
79
80
83 private void testSingleSourceSingleSink( boolean directed ) {
84 D.bug( ">>> testSingleSourceSingleSink(" + directed + ")" );
85
86 timerA.reset();
87 timerB.reset();
88
89 YRandom random = new YRandom( seed );
90
91 RandomGraphGenerator rg = new RandomGraphGenerator( seed );
92
93 rg.allowCycles( true );
94 rg.setNodeCount( random.nextInt( 200 ) );
95 rg.setEdgeCount( random.nextInt( 1600 ) );
96
97 Graph G = rg.generate();
98
99 double[] cost = new double[G.E()];
100 double[] distA = new double[G.N()];
101 double[] distB = new double[G.N()];
102
103 for ( EdgeCursor ec = G.edges(); ec.ok(); ec.next() ) {
104 Edge e = ec.edge();
105 int eid = e.index();
106 cost[eid] = random.nextInt( 10000 );
107 }
108
109 for ( NodeCursor nc = G.nodes(); nc.ok(); nc.next() ) {
110 Node v = nc.node();
111 if ( v.index() % 60 == 59 ) D.bug( "." );
112 else D.bu( "." );
113 for ( NodeCursor ncc = G.nodes(); ncc.ok(); ncc.next() ) {
114 Node w = ncc.node();
115 timerA.start();
116 ShortestPaths.dijkstra( G, v, directed, cost, distA );
117 timerA.stop();
118 timerB.start();
119 double dist = ShortestPaths.singleSourceSingleSink( G, v, w, directed, cost, new Edge[G.N()] );
120 timerB.stop();
121 if ( distA[w.index()] != dist ) {
122 D.bug( "\ndist mismatch: v = " + v + " w = " + w );
123 D.bug( "distA = " + distA[w.index()] + " dist = " + dist );
124 }
125 }
126 }
127
128 D.bug( "\ndijkstra= " + timerA + "\nsource-target-dijkstra " + timerB );
129
130 D.bug( "<<< testSingleSourceSingleSink(" + directed + ")\n\n" );
131 }
132
133
134
138 private void testAllPairs( boolean directed ) {
139 D.bug( ">>> testAllPairs(" + directed + ")" );
140
141 timerA.reset();
142 timerB.reset();
143
144 YRandom random = new YRandom( seed );
145
146 RandomGraphGenerator rg = new RandomGraphGenerator( seed );
147
148 rg.allowCycles( true );
149 rg.setNodeCount( random.nextInt( 1000 ) );
150 rg.setEdgeCount( random.nextInt( 100000 ) );
151
152 Graph G = rg.generate();
153
154 double[] cost = new double[G.E()];
155 double[][] distA = new double[G.N()][G.N()];
156 double[] distB = new double[G.N()];
157
158
159 for ( EdgeCursor ec = G.edges(); ec.ok(); ec.next() ) {
160 Edge e = ec.edge();
161 int eid = e.index();
162 cost[eid] = random.nextInt( 100000 );
163 }
164
165
166 timerA.start();
167 ShortestPaths.allPairs( G, directed, cost, distA );
168 timerA.stop();
169
170
171 for ( NodeCursor nc = G.nodes(); nc.ok(); nc.next() ) {
172 Node v = nc.node();
173
174 timerB.start();
175 ShortestPaths.singleSource( G, v, directed, cost, distB );
176 timerB.stop();
177 if ( v.index() % 60 == 59 ) D.bug( "." );
178 else D.bu( "." );
179
180 for ( NodeCursor ncc = G.nodes(); ncc.ok(); ncc.next() ) {
181 Node w = ncc.node();
182 if ( distA[v.index()][w.index()] != distB[w.index()] ) {
183 D.bug( "dist mismatch! v = " + v + " w = " + w );
184 D.bug( "distA = " + distA[v.index()][w.index()] + " distB = " + distB[w.index()] );
185 System.exit( 1 );
186 }
187
188 }
189 }
190 D.bug( "\nallPairs = " + timerA + "\nsingleSource " + timerB );
191
192 D.bug( "<<< testAllPairs(" + directed + ")\n\n" );
193 }
194
195
198 private void testSP( boolean directed ) {
199 D.bug( ">>> testSP(" + directed + ")" );
200
201 timerA.reset();
202 timerB.reset();
203 timerC.reset();
204 timerD.reset();
205
206 timerD.start();
207 for ( int i = 0; i < 100; i++ ) {
208 if ( i % 60 == 59 ) D.bug( "." );
209 else D.bu( "." );
210
211 testSP( i, directed );
212 }
213 D.bug( "" );
214 timerD.stop();
215 D.bug( "overall = " + timerD + "\ndijkstra = " + timerA + "\nbellmanFord = " + timerB + "\nacyclic = " + timerC );
216
217 D.bug( "<<< testSP(" + directed + ")\n\n" );
218
219 }
220
221
225 private void testSP( int loop, boolean directed ) {
226 YRandom random = new YRandom( seed + loop );
227
228 RandomGraphGenerator rg = new RandomGraphGenerator( seed + loop );
229
230 rg.allowCycles( false );
231 rg.setNodeCount( random.nextInt( 100 ) );
232 rg.setEdgeCount( random.nextInt( 5555 ) );
233
234 Graph G = rg.generate();
235
236
238 double[] cost = new double[G.edgeCount()];
239 double[] distA = new double[G.nodeCount()];
240 double[] distB = new double[G.nodeCount()];
241 double[] distC = new double[G.nodeCount()];
242
243 for ( EdgeCursor ec = G.edges(); ec.ok(); ec.next() ) {
244 Edge e = ec.edge();
245 int eid = e.index();
246 cost[eid] = random.nextInt( 100000 );
247 }
248
249 for ( NodeCursor nc = G.nodes(); nc.ok(); nc.next() ) {
250 Node s = nc.node();
251 int sid = s.index();
252 timerA.start();
253 ShortestPaths.dijkstra( G, s, directed, cost, distA );
254 timerA.stop();
255
256 timerB.start();
257 boolean resultB = ShortestPaths.bellmanFord( G, s, directed, cost, distB );
258 timerB.stop();
259
260
261 boolean resultC = GraphChecker.isAcyclic( G ) && directed;
262 timerC.start();
263 if ( resultC ) ShortestPaths.acyclic( G, s, cost, distC );
264 timerC.stop();
265 if ( resultB ) {
266 for ( NodeCursor ncc = G.nodes(); ncc.ok(); ncc.next() ) {
267 Node w = ncc.node();
268 int wid = w.index();
269
270 if ( distA[wid] != distB[wid] ) {
271 D.bug( "dist mismatch" );
272 D.bug( "" + w + " dijkstra: " + distA[wid] + " bellmanford: " + distB[wid] );
273 System.exit( 1 );
274 }
275 }
276 }
277
278 if ( resultC ) {
279 for ( NodeCursor ncc = G.nodes(); ncc.ok(); ncc.next() ) {
280 Node w = ncc.node();
281 int wid = w.index();
282
283 if ( distA[wid] != distC[wid] ) {
284 D.bug( "dist mismatch" );
285 D.bug( "" + w + " dijkstra: " + distA[wid] + " acyclic: " + distC[wid] );
286 System.exit( 1 );
287 }
288 }
289 }
290
291 }
292 }
293
294 }
295