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    
10   import java.util.*;
11   import edu.uci.ics.jung.graph.*;
12   
13   public class AStarSearch {
14       private UndirectedSparseGraph<MyVertex, WeightedEdge> m_g;
15       private int m_length;
16       
17       public AStarSearch(UndirectedSparseGraph<MyVertex, WeightedEdge> g) {
18           m_g = g;
19           m_length = 0;
20       }
21           
22       public List<WeightedEdge> search(MyVertex start, MyVertex goal) {
23           /** Initialization **/
24           // Set of nodes to be evaluated, ordered by whichever node has the lower heuristic
25           PriorityQueue<MyVertex> openset = new PriorityQueue<MyVertex>();
26           // The openset initially contains the start node
27           openset.add(start);
28           // Distance from goal along optimal path
29           HashMap<MyVertex, Integer> gScore = new HashMap<MyVertex, Integer>();
30           // The distance from the start node to itself is 0
31           gScore.put(start, 0);
32           HashMap<MyVertex, Integer> hScore = new HashMap<MyVertex, Integer>();
33           hScore.put(start, start.getDistance(goal));
34           start.setFScore(hScore.get(start));
35           /** End Initialization **/
36           
37           MyVertex x;
38           int tentativeGScore;
39           boolean tentativeIsBetter;
40           while(!openset.isEmpty()) {
41               // Grab the value at the priority queue.  This will have the lowest
42               // f-score.
43               x = openset.poll();
44               if(x.equals(goal)) return reconstructPath(x);   
45               // Put x on the closed set
46               x.close();
47               // Iterate through the neighbors of x
48               for(MyVertex y : m_g.getNeighbors(x)) {
49                   if(y.isClosed()) continue;
50                   tentativeGScore = gScore.get(x) + m_g.findEdge(x, y).getWeight();
51                   tentativeIsBetter = false;
52                   if(!openset.contains(y)) {
53                       openset.add(y);
54                       hScore.put(y, y.getDistance(goal));
55                       tentativeIsBetter = true;
56                   } else if(tentativeGScore < gScore.get(y)) {
57                       tentativeIsBetter = true;
58                   }
59                   if(tentativeIsBetter) {
60                       y.setPredecessor(x);
61                       gScore.put(y, tentativeGScore);
62                       y.setFScore(gScore.get(y) + hScore.get(y));
63                   }
64               } // end for
65           } // end while
66           return null;
67       }
68       
69       // Reconstruct the path taken from the goal vertex to the start vertex
70       private List<WeightedEdge> reconstructPath(MyVertex end) {
71           MyVertex tempV = end;
72           WeightedEdge tempE;
73           LinkedList<WeightedEdge> path = new LinkedList<WeightedEdge>();
74           while(tempV.getPredecessor() != null) {
75               tempE = m_g.findEdge(tempV, tempV.getPredecessor());
76               tempE.setPath();
77               m_length += tempE.getWeight();
78               path.add(tempE);
79               tempV = tempV.getPredecessor();
80           }
81           return path;
82       }
83       
84       public int getLength() {
85           return m_length;
86       }
87   }