1
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
52 public class ShortestPathDemo
53 {
54
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 RandomGraphGenerator randomGraph = new RandomGraphGenerator(0L);
78 randomGraph.setNodeCount(nodeCount);
79 randomGraph.setEdgeCount(edgeCount);
80 Graph graph = randomGraph.generate();
81
82 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 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
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
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 graph.disposeNodeMap(distanceMap);
153
154 }
155
156 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