1   /****************************************************************************
2    * This demo file is part of yFiles for Java 2.14.
3    * Copyright (c) 2000-2017 by yWorks GmbH, Vor dem Kreuzberg 28,
4    * 72070 Tuebingen, Germany. All rights reserved.
5    * 
6    * yFiles demo files exhibit yFiles for Java functionalities. Any redistribution
7    * of demo files in source code or binary form, with or without
8    * modification, is not permitted.
9    * 
10   * Owners of a valid software license for a yFiles for Java version that this
11   * demo is shipped with are allowed to use the demo source code as basis
12   * for their own yFiles for Java powered applications. Use of such programs is
13   * governed by the rights and conditions as set out in the yFiles for Java
14   * license agreement.
15   * 
16   * THIS SOFTWARE IS PROVIDED ''AS IS'' AND ANY EXPRESS OR IMPLIED
17   * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
18   * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN
19   * NO EVENT SHALL yWorks BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
20   * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
21   * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
22   * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
23   * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
24   * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
25   * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26   *
27   ***************************************************************************/
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  /**
45   * This class compares the performance and results of some shortest path
46   * algorithms available in yFiles.
47   */
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    /**
57     * Program launcher. Accepts a random seed on the command line.
58     */
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    /**
81     * Tests single source single sink shortest path algorithms
82     */
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   /**
135    * Compares the built-in all pairs shortest path algorithm with
136    * multiple calls to single source shortest path algorithms
137    */
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   /**
196    * calls testSP with different random seeds.
197    */
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   /**
222    * Compares dijkstra with bellman-ford shortest path algorithms and with
223    * special routine for acyclic graphs.
224    */
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     //D.bug("\nn="  + G.N() + " m=" + G.E());
237 
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