1   /****************************************************************************
2    **
3    ** This file is part of yFiles-2.6. 
4    ** 
5    ** yWorks proprietary/confidential. Use is subject to license terms.
6    **
7    ** Redistribution of this file or of an unauthorized byte-code version
8    ** of this file is strictly forbidden.
9    **
10   ** Copyright (c) 2000-2008 by yWorks GmbH, Vor dem Kreuzberg 28, 
11   ** 72070 Tuebingen, Germany. All rights reserved.
12   **
13   ***************************************************************************/
14  package demo.algo;
15  
16  
17  import demo.base.RandomGraphGenerator;
18  import y.algo.GraphChecker;
19  import y.algo.ShortestPaths;
20  import y.base.Edge;
21  import y.base.EdgeCursor;
22  import y.base.Graph;
23  import y.base.Node;
24  import y.base.NodeCursor;
25  import y.util.D;
26  import y.util.Timer;
27  import y.util.YRandom;
28  
29  
30  /**
31   * This class compares the performance and results of some shortest path
32   * algorithms available in yFiles.
33   */
34  public class ShortestPathTest {
35    static long seed = 0;
36  
37    private Timer timerA = new Timer( false );
38    private Timer timerB = new Timer( false );
39    private Timer timerC = new Timer( false );
40    private Timer timerD = new Timer( false );
41  
42    /**
43     * programm launcher. Accepts a random seed on the command line.
44     */
45    public static void main( String[] args ) {
46      try {
47        seed = Long.parseLong( args[0] );
48      }
49      catch ( Exception ex ) {
50      }
51  
52      (new ShortestPathTest()).doIt();
53  
54    }
55  
56    private void doIt() {
57      testSP( true );
58      testAllPairs( true );
59      testSingleSourceSingleSink( true );
60      testSP( false );
61      testAllPairs( false );
62      testSingleSourceSingleSink( false );
63    }
64  
65  
66    /**
67     * Tests single source single sink shortest path algorithms
68     */
69    private void testSingleSourceSingleSink( boolean directed ) {
70      D.bug( ">>> testSingleSourceSingleSink(" + directed + ")" );
71  
72      timerA.reset();
73      timerB.reset();
74  
75      YRandom random = new YRandom( seed );
76  
77      RandomGraphGenerator rg = new RandomGraphGenerator( seed );
78  
79      rg.allowCycles( true );
80      rg.setNodeCount( random.nextInt( 200 ) );
81      rg.setEdgeCount( random.nextInt( 1600 ) );
82  
83      Graph G = rg.generate();
84  
85      double[] cost = new double[G.E()];
86      double[] distA = new double[G.N()];
87      double[] distB = new double[G.N()];
88  
89      for ( EdgeCursor ec = G.edges(); ec.ok(); ec.next() ) {
90        Edge e = ec.edge();
91        int eid = e.index();
92        cost[eid] = random.nextInt( 10000 );
93      }
94  
95      for ( NodeCursor nc = G.nodes(); nc.ok(); nc.next() ) {
96        Node v = nc.node();
97        if ( v.index() % 60 == 59 ) D.bug( "." );
98        else D.bu( "." );
99        for ( NodeCursor ncc = G.nodes(); ncc.ok(); ncc.next() ) {
100         Node w = ncc.node();
101         timerA.start();
102         ShortestPaths.dijkstra( G, v, directed, cost, distA );
103         timerA.stop();
104         timerB.start();
105         double dist = ShortestPaths.singleSourceSingleSink( G, v, w, directed, cost, new Edge[G.N()] );
106         timerB.stop();
107         if ( distA[w.index()] != dist ) {
108           D.bug( "\ndist mismatch: v = " + v + "  w = " + w );
109           D.bug( "distA = " + distA[w.index()] + "  dist = " + dist );
110         }
111       }
112     }
113 
114     D.bug( "\ndijkstra= " + timerA + "\nsource-target-dijkstra " + timerB );
115 
116     D.bug( "<<< testSingleSourceSingleSink(" + directed + ")\n\n" );
117   }
118 
119 
120   /**
121    * Compares the builtin all pairs shortest path algorithm with
122    * multiple calls to single source shortest path algorithms
123    */
124   private void testAllPairs( boolean directed ) {
125     D.bug( ">>> testAllPairs(" + directed + ")" );
126 
127     timerA.reset();
128     timerB.reset();
129 
130     YRandom random = new YRandom( seed );
131 
132     RandomGraphGenerator rg = new RandomGraphGenerator( seed );
133 
134     rg.allowCycles( true );
135     rg.setNodeCount( random.nextInt( 1000 ) );
136     rg.setEdgeCount( random.nextInt( 100000 ) );
137 
138     Graph G = rg.generate();
139 
140     double[] cost = new double[G.E()];
141     double[][] distA = new double[G.N()][G.N()];
142     double[] distB = new double[G.N()];
143 
144 
145     for ( EdgeCursor ec = G.edges(); ec.ok(); ec.next() ) {
146       Edge e = ec.edge();
147       int eid = e.index();
148       cost[eid] = random.nextInt( 100000 );
149     }
150 
151 
152     timerA.start();
153     ShortestPaths.allPairs( G, directed, cost, distA );
154     timerA.stop();
155 
156 
157     for ( NodeCursor nc = G.nodes(); nc.ok(); nc.next() ) {
158       Node v = nc.node();
159 
160       timerB.start();
161       ShortestPaths.singleSource( G, v, directed, cost, distB );
162       timerB.stop();
163       if ( v.index() % 60 == 59 ) D.bug( "." );
164       else D.bu( "." );
165 
166       for ( NodeCursor ncc = G.nodes(); ncc.ok(); ncc.next() ) {
167         Node w = ncc.node();
168         if ( distA[v.index()][w.index()] != distB[w.index()] ) {
169           D.bug( "dist mismatch! v = " + v + "  w = " + w );
170           D.bug( "distA = " + distA[v.index()][w.index()] + "   distB = " + distB[w.index()] );
171           System.exit( 1 );
172         }
173 
174       }
175     }
176     D.bug( "\nallPairs = " + timerA + "\nsingleSource " + timerB );
177 
178     D.bug( "<<< testAllPairs(" + directed + ")\n\n" );
179   }
180 
181   /**
182    * calls testSP with different random seeds.
183    */
184   private void testSP( boolean directed ) {
185     D.bug( ">>> testSP(" + directed + ")" );
186 
187     timerA.reset();
188     timerB.reset();
189     timerC.reset();
190     timerD.reset();
191 
192     timerD.start();
193     for ( int i = 0; i < 100; i++ ) {
194       if ( i % 60 == 59 ) D.bug( "." );
195       else D.bu( "." );
196 
197       testSP( i, directed );
198     }
199     D.bug( "" );
200     timerD.stop();
201     D.bug( "overall = " + timerD + "\ndijkstra = " + timerA + "\nbellmanFord = " + timerB + "\nacyclic = " + timerC );
202 
203     D.bug( "<<< testSP(" + directed + ")\n\n" );
204 
205   }
206 
207   /**
208    * Compares dijkstra with bellman-ford shortest path algorithms and with
209    * special routine for acyclic graphs.
210    */
211   private void testSP( int loop, boolean directed ) {
212     YRandom random = new YRandom( seed + loop );
213 
214     RandomGraphGenerator rg = new RandomGraphGenerator( seed + loop );
215 
216     rg.allowCycles( false );
217     rg.setNodeCount( random.nextInt( 100 ) );
218     rg.setEdgeCount( random.nextInt( 5555 ) );
219 
220     Graph G = rg.generate();
221 
222     //D.bug("\nn="  + G.N() + " m=" + G.E());
223 
224     double[] cost = new double[G.edgeCount()];
225     double[] distA = new double[G.nodeCount()];
226     double[] distB = new double[G.nodeCount()];
227     double[] distC = new double[G.nodeCount()];
228 
229     for ( EdgeCursor ec = G.edges(); ec.ok(); ec.next() ) {
230       Edge e = ec.edge();
231       int eid = e.index();
232       cost[eid] = random.nextInt( 100000 );
233     }
234 
235     for ( NodeCursor nc = G.nodes(); nc.ok(); nc.next() ) {
236       Node s = nc.node();
237       int sid = s.index();
238       timerA.start();
239       ShortestPaths.dijkstra( G, s, directed, cost, distA );
240       timerA.stop();
241 
242       timerB.start();
243       boolean resultB = ShortestPaths.bellmanFord( G, s, directed, cost, distB );
244       timerB.stop();
245 
246 
247       boolean resultC = GraphChecker.isAcyclic( G ) && directed;
248       timerC.start();
249       if ( resultC ) ShortestPaths.acyclic( G, s, cost, distC );
250       timerC.stop();
251       if ( resultB ) {
252         for ( NodeCursor ncc = G.nodes(); ncc.ok(); ncc.next() ) {
253           Node w = ncc.node();
254           int wid = w.index();
255 
256           if ( distA[wid] != distB[wid] ) {
257             D.bug( "dist mismatch" );
258             D.bug( "" + w + " dijkstra: " + distA[wid] + " bellmanford: " + distB[wid] );
259             System.exit( 1 );
260           }
261         }
262       }
263 
264       if ( resultC ) {
265         for ( NodeCursor ncc = G.nodes(); ncc.ok(); ncc.next() ) {
266           Node w = ncc.node();
267           int wid = w.index();
268 
269           if ( distA[wid] != distC[wid] ) {
270             D.bug( "dist mismatch" );
271             D.bug( "" + w + " dijkstra: " + distA[wid] + " acyclic: " + distC[wid] );
272             System.exit( 1 );
273           }
274         }
275       }
276 
277     }
278   }
279 
280 }
281