I'm having some problems implementing AStar or A* algorithm for practice, it looks like the code is all good just when i try to do some tests it crashes on
Exception in thread "main" java.lang.ClassCastException: AStar.Node cannot be cast to java.util.Map
at AStar.GraphAStar.addNode(GraphAStar.java:51)
at AStar.AStar.main(AStar.java:283)
It looks like the casting doesn't quite work as it says on GraphAStar class specifictly in this line.
nodeIdNode.put(nodeId, (Map<T, Double>) new Node<T>(nodeId, heuristicMap.get(nodeId)));
Any ideas???
I'm adding my code down here.
Node class
public class Node <T> {
T nodeId;
Map<T, Double> heuristic;
double g; //distance to new node
double h; //distante to goal
double f; // f = g + h;
public Node(T nodeId,Map<T,Double> heuristic){
this.nodeId = nodeId;
this.g = Double.MAX_VALUE;
this.heuristic = heuristic;
}
public T getNode(){
return nodeId;
}
public double getGPath(){
return g;
}
public void setGPath(double g){
this.g = g;
}
public void CalculateF(T destination){
this.h = heuristic.get(destination);
this.f = g + h;
}
public double getH(){
return g;
}
public double getF(){
return f;
}
}
GraphAStar class
public class GraphAStar<T> implements Iterable<T> {
/***
* A map from the Node id to outgoing edge.
* An outgoing edge is represented as a Node and the length
*/
Map<T, Map<Node<T>, Double>> graph;
/***
* A map of heuristic from a node to each other node in the graph
*/
Map<T, Map<T,Double>> heuristicMap;
/***
* A map between the Node id and its data.
*/
Map<T, Map<T,Double>> nodeIdNode;
public GraphAStar(Map<T, Map<T,Double>> heuristicMap){
if(heuristicMap == null){
throw new NullPointerException("The heuristic map should not be null");
}
graph = new HashMap<T, Map<Node<T>, Double>>();
nodeIdNode = new HashMap<>();
this.heuristicMap = heuristicMap;
}
/***
* Adds a new node to the graph
* Internally it creates the Node and populate the heuristic map with node input to node data
* @param nodeId the node to be added
*/
public void addNode(T nodeId){
if(nodeId == null){
throw new NullPointerException("The node cannot be null");
}
if(!heuristicMap.containsKey(nodeId)){
throw new NoSuchElementException("This node is not part of the heuristic Map");
}
graph.put(nodeId, new HashMap<Node<T>,Double>());
nodeIdNode.put(nodeId, (Map<T, Double>) new Node<T>(nodeId, heuristicMap.get(nodeId)));
}
/***
* Adds an edge from source node to destination node
* there can only be a single edge from source to node.
* Adding additional edge would be overwrite the value.
* @param From the first node to be in the edge
* @param To the second node to be in the edge
* @param length the length of node From and To
*/
public void addEdge(T From, T To, double length){
if(From == null || To == null){
throw new NullPointerException("Either of the nodes cannot be null");
}
if(!heuristicMap.containsKey(To) || !heuristicMap.containsKey(From)){
throw new NoSuchElementException("Either of the nodes should be listed in the heuristic map");
}
if(!graph.containsKey(To) || !graph.containsKey(From)){
throw new NoSuchElementException("Either of the nodes should be part of the graph");
}
graph.get(From).put((Node<T>) nodeIdNode.get(To), length);
graph.get(To).put((Node<T>) nodeIdNode.get(From), length);
}
/***
* Returns immutable view of edges
* @param nodeId the node whose outgoing needs to be returned.
* @return An immutable view of the edges leaving that node.
*/
public Map<Node<T>,Double> edgesFrom(T nodeId){
if(nodeId == null){
throw new NullPointerException("The input node should not be null");
}
if(!heuristicMap.containsKey(nodeId)){
throw new NoSuchElementException("This node should be part of the heuristic map");
}
if(!graph.containsKey(nodeId)){
throw new NoSuchElementException("Thsi node should be null");
}
return Collections.unmodifiableMap(graph.get(nodeId));
}
/***
* the node data corresponding to the current nodeId
* @param nodeId the nodeId to be returned
* @return the node data from the node
*/
public Node<T> getNodeData(T nodeId){
if(nodeId == null){
throw new NullPointerException("The node should not be empty");
}
if(!nodeIdNode.containsKey(nodeId)){
throw new NoSuchElementException("The node does not exist");
}
return (Node<T>) nodeIdNode.get(nodeId);
}
/***
* Returns an iterator that can traverse the nodes of the graph
* @return an iterator
*/
@Override
public Iterator<T> iterator() {
return graph.keySet().iterator();
}
}
AStar class
public class AStar<T> {
GraphAStar<T> graph;
public AStar(GraphAStar<T> graphA){
this.graph = graphA;
}
//extends comparator
public class NodeComparator implements Comparator<Node<T>>{
public int compare(Node<T> first,Node<T> second){
if(first.getF() > second.getF()){
return 1;
}
if(second.getF() > first.getF()){
return -1;
}
return 0;
}
}
public List<T> Astar(T source, T destination){
Queue<Node<T>> openQueue = new PriorityQueue<Node<T>>(11,new NodeComparator());
Node<T> sourceNode = graph.getNodeData(source);
sourceNode.setGPath(0);
sourceNode.CalculateF(destination);
openQueue.add(sourceNode);
Map<T, T> path = new HashMap<T, T>();
Set<Node<T>> closedList = new HashSet<Node<T>>();
while(!openQueue.isEmpty()){
Node<T> node = openQueue.poll();
if(node.getNode().equals(destination)){
return path(path,destination);
}
closedList.add(node);
for(Entry<Node<T>, Double> neighborEntry : graph.edgesFrom(node.getNode()).entrySet()){
Node<T> neighbor = neighborEntry.getKey();
if(closedList.contains(neighbor)){
continue;
}
double distanceBetweenTwoNodes = neighborEntry.getValue();
double tentativeG = distanceBetweenTwoNodes + node.getGPath();
if(tentativeG < neighbor.getGPath()){
neighbor.setGPath(tentativeG);
neighbor.CalculateF(destination);
path.put(neighbor.getNode(), node.getNode());
if(!openQueue.contains(neighbor)){
openQueue.add(neighbor);
}
}
}
}
return null;
}
private List<T> path(Map<T,T> path, T destination){
assert path != null;
assert destination != null;
List<T> pathList = new ArrayList<T>();
pathList.add(destination);
while(path.containsKey(destination)){
destination = path.get(destination);
pathList.add(destination);
}
Collections.reverse(pathList);
return pathList;
}
public static void main(String[] args){
Map<String, Map<String,Double>> heuristic = new HashMap<String, Map<String,Double>>();
//distance from Node N to all
Map<String, Double> MapA = new HashMap<String,Double>();
MapA.put("A", 0.0);
MapA.put("B", 2.0);
MapA.put("C", 3.0);
MapA.put("D", 5.0);
MapA.put("E", 7.0);
MapA.put("F", 4.0);
MapA.put("G", 10.0);
MapA.put("H", 13.0);
MapA.put("I", 15.0);
Map<String, Double> MapB = new HashMap<String,Double>();
MapB.put("A", 2.0);
MapB.put("B", 0.0);
MapB.put("C", 5.0);
MapB.put("D", 3.0);
MapB.put("E", 4.0);
MapB.put("F", 6.0);
MapB.put("G", 6.0);
MapB.put("H", 10.0);
MapB.put("I", 14.0);
Map<String, Double> MapC = new HashMap<String,Double>();
MapC.put("A", 3.0);
MapC.put("B", 5.0);
MapC.put("C", 0.0);
MapC.put("D", 4.0);
MapC.put("E", 7.0);
MapC.put("F", 2.0);
MapC.put("G", 10.0);
MapC.put("H", 7.0);
MapC.put("I", 15.0);
Map<String, Double> MapD = new HashMap<String,Double>();
MapD.put("A", 5.0);
MapD.put("B", 5.0);
MapD.put("C", 4.0);
MapD.put("D", 0.0);
MapD.put("E", 3.0);
MapD.put("F", 3.0);
MapD.put("G", 7.0);
MapD.put("H", 9.0);
MapD.put("I", 11.0);
Map<String, Double> MapE = new HashMap<String,Double>();
MapE.put("A", 7.0);
MapE.put("B", 4.0);
MapE.put("C", 7.0);
MapE.put("D", 3.0);
MapE.put("E", 0.0);
MapE.put("F", 9.0);
MapE.put("G", 2.0);
MapE.put("H", 11.0);
MapE.put("I", 9.0);
Map<String, Double> MapF = new HashMap<String,Double>();
MapF.put("A", 4.0);
MapF.put("B", 6.0);
MapF.put("C", 2.0);
MapF.put("D", 3.0);
MapF.put("E", 9.0);
MapF.put("F", 0.0);
MapF.put("G", 7.0);
MapF.put("H", 3.0);
MapF.put("I", 7.0);
Map<String, Double> MapG = new HashMap<String,Double>();
MapG.put("A", 10.0);
MapG.put("B", 6.0);
MapG.put("C", 10.0);
MapG.put("D", 7.0);
MapG.put("E", 2.0);
MapG.put("F", 7.0);
MapG.put("G", 0.0);
MapG.put("H", 5.0);
MapG.put("I", 2.0);
Map<String, Double> MapH = new HashMap<String,Double>();
MapH.put("A", 13.0);
MapH.put("B", 10.0);
MapH.put("C", 7.0);
MapH.put("D", 9.0);
MapH.put("E", 11.0);
MapH.put("F", 3.0);
MapH.put("G", 5.0);
MapH.put("H", 0.0);
MapH.put("I", 4.0);
Map<String, Double> MapI = new HashMap<String,Double>();
MapI.put("A", 15.0);
MapI.put("B", 14.0);
MapI.put("C", 15.0);
MapI.put("D", 11.0);
MapI.put("E", 9.0);
MapI.put("F", 7.0);
MapI.put("G", 2.0);
MapI.put("H", 4.0);
MapI.put("I", 0.0);
heuristic.put("A", MapA);
heuristic.put("B", MapB);
heuristic.put("C", MapC);
heuristic.put("D", MapD);
heuristic.put("E", MapE);
heuristic.put("F", MapF);
heuristic.put("G", MapG);
heuristic.put("H", MapH);
heuristic.put("I", MapI);
GraphAStar<String> graph = new GraphAStar<String>(heuristic);
graph.addNode("A");
graph.addNode("B");
graph.addNode("C");
graph.addNode("D");
graph.addNode("E");
graph.addNode("F");
graph.addNode("G");
graph.addNode("H");
graph.addNode("I");
graph.addEdge("A", "B", 2);
graph.addEdge("A", "C", 3);
graph.addEdge("A", "D", 5);
graph.addEdge("B", "E", 4);
graph.addEdge("C", "F", 2);
graph.addEdge("D", "E", 3);
graph.addEdge("D", "F", 3);
graph.addEdge("E", "G", 2);
graph.addEdge("F", "H", 3);
graph.addEdge("G", "H", 5);
graph.addEdge("G", "I", 2);
AStar<String> aStar = new AStar<String>(graph);
for(String path : aStar.Astar("A", "I")){
System.out.println(path);
}
}
}
So your problem is that you have Node class and you are trying to cast it to Map. Then you have to implement Map interface for you Node class.
public class Node <T> implements Map { ....
Keep on mind this rule:
Only classes or interfaces (collectively known as Type) from the same type hierarchy can be cast or converted into each other.