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  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 <nodeCount> <edgeCount>
44     * <p>
45     * the first argument gives the desired node count of the graph 
46     * and the second argumnent gives the desired edge count of the 
47     * graph.
48     */
49    public static void main(String args[])
50    {
51      int nodeCount = 30;
52      int edgeCount = 60;
53      
54      if(args.length == 2) {
55        try {
56          nodeCount = Integer.parseInt(args[0]);
57          edgeCount = Integer.parseInt(args[1]);
58        } catch(NumberFormatException ex) {
59          usage();
60        }
61      }
62      
63      // Create a random graph with the given edge and node count
64      RandomGraphGenerator randomGraph = new RandomGraphGenerator(0L);
65      randomGraph.setNodeCount(nodeCount);
66      randomGraph.setEdgeCount(edgeCount);
67      Graph graph = randomGraph.generate();
68      
69      // Create an edgemap and assign random double weights to 
70      // the edges of the graph.
71      EdgeMap weightMap = graph.createEdgeMap();
72      YRandom random = new YRandom(0L);
73      for(EdgeCursor ec = graph.edges(); ec.ok(); ec.next())
74      {
75        Edge e = ec.edge();
76        weightMap.setDouble(e,100.0*random.nextDouble());
77      }
78      
79      
80      
81      // Calculate the shortest path from the first to the last node
82      // within the graph
83      if(!graph.isEmpty())
84      {
85        
86        Node from = graph.firstNode();
87        Node to   = graph.lastNode();
88        EdgeList path;
89        double sum = 0.0;
90        
91        // The undirected case first, i.e. edges of the graph and the
92        // resulting shortest path are considered to be undirected
93        
94        path = ShortestPaths.singleSourceSingleSink(graph, from, to, false, weightMap);
95        for(EdgeCursor ec = path.edges(); ec.ok(); ec.next())
96        {
97          Edge e = ec.edge();
98          double weight = weightMap.getDouble( e );
99          D.bug( e + " weight = " + weight );
100         sum += weight;
101       }
102       if(sum == 0.0)
103         D.bug("NO UNDIRECTED PATH");
104       else
105         D.bug("UNDIRECTED PATH LENGTH = " + sum);
106       
107       
108       // Next the directed case, i.e. edges of the graph and the
109       // resulting shortest path are considered to be directed.
110       // Note that this shorteszt path can't be shorter then the one
111       // for the undirected case
112       
113       path = ShortestPaths.singleSourceSingleSink(graph, from, to, true, weightMap );
114       sum = 0.0;
115       for(EdgeCursor ec = path.edges(); ec.ok(); ec.next())
116       {
117         Edge e = ec.edge();
118         double weight = weightMap.getDouble( e );
119         D.bug( e + " weight = " + weight );
120         sum += weight;
121       }
122       if(sum == 0.0)
123         D.bug("NO DIRECTED PATH");
124       else
125         D.bug("DIRECTED PATH LENGTH = " + sum);
126       
127       
128       D.bug("\nAuxiliary distance test\n");
129       
130       NodeMap distanceMap = graph.createNodeMap();
131       NodeMap predMap     = graph.createNodeMap();
132       ShortestPaths.singleSource(graph, from, true, weightMap, distanceMap, predMap);
133       if(distanceMap.getDouble(to) == Double.POSITIVE_INFINITY)
134         D.bug("Distance from first to last node is infinite");
135       else
136         D.bug("Distance from first to last node is " + distanceMap.getDouble(to));
137       
138       // Dispose distanceMap since it is not needed anymore
139       graph.disposeNodeMap(distanceMap);
140       
141     }
142     
143     // Dispose weightMap since it is not needed anymore
144     graph.disposeEdgeMap( weightMap );
145     
146   }
147   
148   static void usage()
149   {
150     System.err.println("Usage: java demo.algo.ShortestPathDemo <nodeCount> <edgeCount>");
151     System.err.println("Usage: Both <nodeCount> and <edgeCount> must be integral values.");
152     System.exit(1);
153   }
154   
155 }
156