import java.util.*; public class AStar { Graph graph; Map aStarNodes; private class GraphAStarNode extends AStarNode { private String name; public GraphAStarNode(String name) { this.name = name; } public String getName() { return this.name; } /** * This return the cost from this node to the given node. * Note that if there are more than one edge that * connects the two nodes, this will return just the first one!! */ public float getCost(AStarNode node) { GraphAStarNode paramNode = (GraphAStarNode) node; // does the edge exists? if (graph.hasEdge(this.getName(), paramNode.getName())) { Edge e = graph.getEdge(this.getName(), paramNode.getName()); return (float) e.getCost(); } else { return Float.MAX_VALUE; } } public float getEstimatedCost(AStarNode node) { GraphAStarNode paramNode = (GraphAStarNode) node; Node n1 = graph.getNode(this.getName()); Node n2 = graph.getNode(paramNode.getName()); return (float) graph.getEstimatedCost(n1, n2); } public List getNeighbors() { List neigh = new ArrayList(); List edges = graph.getNode(this.getName()).getEdges(); ListIterator lIt = edges.listIterator(); Edge tmpEdge; String tmpKeySource; String tmpKeyDest; String neighName = ""; while (lIt.hasNext()) { tmpEdge = (Edge) lIt.next(); tmpKeySource = tmpEdge.getSource().getKey(); tmpKeyDest = tmpEdge.getDest().getKey(); // one of the two edges is not the current node, thus is the neighbor if (tmpKeySource != this.getName()) neighName = tmpKeySource; //neigh.add(new GraphAStarNode(tmpKeySource)); else if (tmpKeyDest != this.getName()) neighName = tmpKeyDest; if ( aStarNodes.containsKey(neighName) ) neigh.add( aStarNodes.get(neighName) ); else { GraphAStarNode newNode = new GraphAStarNode(neighName); aStarNodes.put(neighName, newNode); neigh.add(newNode); } } return neigh; } public boolean equals(Object node) { GraphAStarNode paramNode = (GraphAStarNode) node; return paramNode.getName() == this.getName(); } public String toString() { return this.getName(); } } /** * Static function that can be called anywhere */ public static List findShortestPath(Node start, Node end, Graph graph) { AStar as = new AStar(); return as.find(start, end, graph); } private List find(Node start, Node end, Graph graph) { this.graph = graph; AStarSearch s = new AStarSearch(); GraphAStarNode startNode = new GraphAStarNode(start.getKey()); GraphAStarNode endNode = new GraphAStarNode(end.getKey()); aStarNodes = new HashMap(); aStarNodes.put(start, startNode); aStarNodes.put(end, endNode); // this is a list of AStarNodes List pathAStarNodes = s.findPath(startNode, endNode); ListIterator lIt = pathAStarNodes.listIterator(); Node tmpNode; String nodeKey; // this is the list of Nodes I will return List pathGraphNodes = new ArrayList(); // add the first node which was not returned by findPath pathGraphNodes.add( start ); while (lIt.hasNext()) { nodeKey = ((GraphAStarNode) lIt.next()).getName(); tmpNode = graph.getNode(nodeKey); pathGraphNodes.add(tmpNode); } return pathGraphNodes; } }