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