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