| Search.java |
1 /**
2 * @author Nick Peters
3 * COMP 469 - Search
4 * Creates a randomly generated graph and finds the shortest path between two
5 * random vertices.
6 */
7
8 package search;
9 import edu.uci.ics.jung.algorithms.shortestpath.DijkstraShortestPath;
10 import edu.uci.ics.jung.graph.*;
11
12 import java.util.*;
13
14 import org.apache.commons.collections15.Transformer;
15
16
17 public class Search {
18 final int N = 30;
19 final double PROB = .25;
20 final int MAX_WEIGHT = 100;
21
22 private DijkstraShortestPath<MyVertex, WeightedEdge> alg;
23 public UndirectedSparseGraph<MyVertex, WeightedEdge> g;
24
25 public Search() {
26 g = new UndirectedSparseGraph<MyVertex, WeightedEdge>();
27 initializeGraph();
28
29 Transformer<WeightedEdge, Integer> weightTransformer = new Transformer<WeightedEdge, Integer>() {
30 public Integer transform(WeightedEdge link) {
31 return link.getWeight();
32 }
33 };
34
35 alg = new DijkstraShortestPath(g, weightTransformer);
36 }
37
38 public void initializeGraph() {
39 // Random number generatotr
40 Random rand = new Random();
41 // These will hold the values of two iterators when determining whether
42 // or not two given vertices have an edge between them.
43 MyVertex curNode, neighborNode;
44 // Temporary variable for holding weights
45 int weight;
46 // Create an undirected graph where Integer is data type of the vertices and String
47 // is the type of the edges.
48 // Add N vertices. From above we defined these to be type Integer.
49 for(int i = 1; i <= N; i++) g.addVertex(new MyVertex(i));
50
51 // A collection of vertices in the graph.
52 Collection<MyVertex> vertices = g.getVertices();
53 // Each vertex has a 25% chance of being connected to another vertex.
54 // We will iterate through a list of vertices and then determine if
55 // there is an edge between it and another vertex. We do not want there
56 // to be parallel edges (an edge between two vertices that already have
57 // an edge between them) since this is an undirected graph. Further, we
58 // also do not want loops (when there is an edge between the same vertex).
59 Iterator<MyVertex> itOut = vertices.iterator();
60 Iterator<MyVertex> itIn = vertices.iterator();
61 while(itOut.hasNext()) {
62 curNode = itOut.next();
63 while(itIn.hasNext()) {
64 neighborNode = itIn.next();
65 // To prevent loops
66 if(!curNode.equals(neighborNode)) {
67 // The nextInt function accepts a value such that it generates
68 // an integer between 0 and the given value. If the given value
69 // is between 0 and the 25, then we will create an edge between
70 // the two vertices.
71 if(Math.random() < PROB) {
72 // Make sure we don't add a parallel edge
73 if(!g.containsEdge(g.findEdge(neighborNode, curNode))) {
74 // Create an edge between the current node and the
75 // potential neighbor node.
76 // Weights between edges will be random values between 0 and 100
77 weight = rand.nextInt(MAX_WEIGHT);
78 g.addEdge(new WeightedEdge(weight, curNode, neighborNode),curNode, neighborNode);
79 } // end if
80 } // end if
81 } // end if
82 } // end while
83 itIn = vertices.iterator();
84 } // end while
85 } // end initializeGraph()
86
87 public void findShortestPath(MyVertex src, MyVertex dest) {
88 // Runs Dijkstra's Algorithm to determine the shortest path.
89 // Returns a list of edges on the path.
90 java.util.List<WeightedEdge> l = alg.getPath(src, dest);
91 // Mark the given edges as being on the path
92 for(WeightedEdge edge : l) edge.setPath();
93 // Debugging information
94 System.out.println("The path is: " + l);
95 Number dist = alg.getDistance(src, dest);
96 System.out.println("The length of the path is: " + dist);
97 }
98
99 } // end Search