1   /****************************************************************************
2    **
3    ** This file is part of yFiles-2.9. 
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-2011 by yWorks GmbH, Vor dem Kreuzberg 28, 
11   ** 72070 Tuebingen, Germany. All rights reserved.
12   **
13   ***************************************************************************/
14  package demo.algo;
15  
16  import y.base.Graph;
17  import y.base.Edge;
18  import y.base.Node;
19  import y.base.EdgeList;
20  import y.base.EdgeCursor;
21  import y.base.EdgeMap;
22  import y.base.NodeMap;
23  import y.util.D;
24  import y.util.YRandom;
25  
26  import demo.base.RandomGraphGenerator;
27  
28  import y.algo.ShortestPaths;
29  
30  
31  
32  /**
33   * Demonstrates the usage of the ShortestPaths class that
34   * provides easy to use algorithms for finding shortest paths 
35   * within weighted graphs.
36   *
37   */
38  public class ShortestPathDemo
39  {
40    /**
41     * Main method:
42     * <p>
43     * Usage: java demo.algo.ShortestPathDemo &lt;nodeCount&gt; &lt;edgeCount&gt;
44     * </p><p>
45     * the first argument gives the desired node count of the graph 
46     * and the second argument gives the desired edge count of the
47     * graph.
48     * </p>
49     */
50    public static void main(String[] args)
51    {
52      int nodeCount = 30;
53      int edgeCount = 60;
54      
55      if(args.length == 2) {
56        try {
57          nodeCount = Integer.parseInt(args[0]);
58          edgeCount = Integer.parseInt(args[1]);
59        } catch(NumberFormatException ex) {
60          usage();
61        }
62      }
63      
64      // Create a random graph with the given edge and node count
65      RandomGraphGenerator randomGraph = new RandomGraphGenerator(0L);
66      randomGraph.setNodeCount(nodeCount);
67      randomGraph.setEdgeCount(edgeCount);
68      Graph graph = randomGraph.generate();
69      
70      // Create an edgemap and assign random double weights to 
71      // the edges of the graph.
72      EdgeMap weightMap = graph.createEdgeMap();
73      YRandom random = new YRandom(0L);
74      for(EdgeCursor ec = graph.edges(); ec.ok(); ec.next())
75      {
76        Edge e = ec.edge();
77        weightMap.setDouble(e,100.0*random.nextDouble());
78      }
79      
80      
81      
82      // Calculate the shortest path from the first to the last node
83      // within the graph
84      if(!graph.isEmpty())
85      {
86        
87        Node from = graph.firstNode();
88        Node to   = graph.lastNode();
89        EdgeList path;
90        double sum = 0.0;
91        
92        // The undirected case first, i.e. edges of the graph and the
93        // resulting shortest path are considered to be undirected
94        
95        path = ShortestPaths.singleSourceSingleSink(graph, from, to, false, weightMap);
96        for(EdgeCursor ec = path.edges(); ec.ok(); ec.next())
97        {
98          Edge e = ec.edge();
99          double weight = weightMap.getDouble( e );
100         D.bug( e + " weight = " + weight );
101         sum += weight;
102       }
103       if(sum == 0.0)
104         D.bug("NO UNDIRECTED PATH");
105       else
106         D.bug("UNDIRECTED PATH LENGTH = " + sum);
107       
108       
109       // Next the directed case, i.e. edges of the graph and the
110       // resulting shortest path are considered to be directed.
111       // Note that this shorteszt path can't be shorter then the one
112       // for the undirected case
113       
114       path = ShortestPaths.singleSourceSingleSink(graph, from, to, true, weightMap );
115       sum = 0.0;
116       for(EdgeCursor ec = path.edges(); ec.ok(); ec.next())
117       {
118         Edge e = ec.edge();
119         double weight = weightMap.getDouble( e );
120         D.bug( e + " weight = " + weight );
121         sum += weight;
122       }
123       if(sum == 0.0)
124         D.bug("NO DIRECTED PATH");
125       else
126         D.bug("DIRECTED PATH LENGTH = " + sum);
127       
128       
129       D.bug("\nAuxiliary distance test\n");
130       
131       NodeMap distanceMap = graph.createNodeMap();
132       NodeMap predMap     = graph.createNodeMap();
133       ShortestPaths.singleSource(graph, from, true, weightMap, distanceMap, predMap);
134       if(distanceMap.getDouble(to) == Double.POSITIVE_INFINITY)
135         D.bug("Distance from first to last node is infinite");
136       else
137         D.bug("Distance from first to last node is " + distanceMap.getDouble(to));
138       
139       // Dispose distanceMap since it is not needed anymore
140       graph.disposeNodeMap(distanceMap);
141       
142     }
143     
144     // Dispose weightMap since it is not needed anymore
145     graph.disposeEdgeMap( weightMap );
146     
147   }
148   
149   static void usage()
150   {
151     System.err.println("Usage: java demo.algo.ShortestPathDemo <nodeCount> <edgeCount>");
152     System.err.println("Usage: Both <nodeCount> and <edgeCount> must be integral values.");
153     System.exit(1);
154   }
155   
156 }
157