PROGRAMMING Assignment $($Dijkstra and A$*)$

Please implement the A$*$ algorithm $($computeAStar$($int$,$int$)$ in Graph.java$).$

public class Graph $\{$

class Edge implements Comparable $\{$

int fromNode;

int connectsToNode;

double weight;

Edge next;

Edge$($int from,

int to$,$ double weight

$)\{$

fromNode $=$ from;

connectsToNode $=$ to;

this.weight $=$ weight;

next $=$ null;

$\}$

public int compareTo$($Edge e$2)\{$

if $($weight $==$ e$2.$weight$)\{$

return $0$;

$\}$

Double dist $=$ weight $-$ e$2.$weight;

return $($dist $<0)?-1$ : $1$;

$\}$

$\}$

class Node $\{$

int nodeNumber;

String nodeName;

int xCoordinate;

int yCoordinate;

void set$($String name, int x$,$ int y$)\{$

nodeName $=$ name;

xCoordinate $=$ x;

yCoordinate $=$ y;

$\}$

$\}$

List nodes;

List edges;

Boolean directed;

public Graph$($int numberOfNodes, Boolean directed$)\{$

nodes $=$ new ArrayList$()$; $//$ List is an abstract type

edges $=$ new ArrayList$()$;

for $($int i $=0$; i $<$ numberOfNodes; $++$i$)\{$

nodes.add$($i$,$ new Node$())$;

nodes.get$($i$).$nodeNumber $=$ i;

edges.add$($i$,$ null$)$;

$\}$

this.directed $=$ directed;

$\}$

public Boolean setNode$($int number, String name, int x$,$ int y$)\{$

if $($number $>=$ nodes.size$())\{$

return false;

$\}$

nodes.get$($number$).$set$($name$,$ x$,$ y$)$;

return true;

$\}$

public Boolean edgeExists$($int fromNode, int toNode$)\{$

Edge iter $=$ edges.get$($fromNode$)$;

while $($null $!=$ iter$)\{$

if $($iter$.$connectsToNode $==$ toNode$)\{$

return true;

$\}$

iter $=$ iter.next;

$\}$

return false;

$\}$

public int getNode$($int xCoord, int yCoord$)\{$

for $($int i $=0$; i $<$ nodes.size$()$; $++$i$)\{$

Node theNode $=$ nodes.get$($i$)$;

if $($theNode$.$xCoordinate $==$ xCoord

&& theNode.yCoordinate $==$ yCoord$)\{$

return i;

$\}$

$\}$

return $-1$;

$\}$

public Boolean addEdge$($int fromX, int fromY, int toX, int toY$)\{$

int fromNode $=$ getNode$($fromX$,$ fromY$)$;

int toNode $=$ getNode$($toX$,$ toY$)$;

if $(-1==$ fromNode $||-1==$ toNode$)\{$

return false;

$\}$

return addEdge$($fromNode$,$ toNode$)$;

$\}$

double euclideanDistance$($int fromNodeNumber, int toNodeNumber$)\{$

Node fromNode $=$ nodes.get$($fromNodeNumber$)$;

Node toNode $=$ nodes.get$($toNodeNumber$)$;

return Math.sqrt$($Math$.$pow$($fromNode$.$xCoordinate $-$ toNode.xCoordinate, $2)$

$+$ Math.pow$($fromNode$.$yCoordinate $-$ toNode.yCoordinate, $2))$;

$\}$

public Double getEdge$($int fromX, int fromY, int toX, int toY$)\{$

int fromEdge $=$ getNode$($fromX$,$ fromY$)$;

int toEdge $=$ getNode$($toX$,$ toY$)$;

if $(-1==$ fromEdge $||-1==$ toEdge$)\{$

return null;

$\}$

return getEdge$($fromEdge$,$ toEdge$)$;

$\}$

public Double getEdge$($int fromNode, int toNode$)\{$

Edge current $=$ edges.get$($fromNode$)$;

while $($null $!=$ current$)\{$

if $($toNode $==$ current.connectsToNode$)\{$

return current.weight;

$\}$

current $=$ current.next;

$\}$

return null;

$\}$

public Boolean addEdge$($int fromNode, int toNode$)\{$

if $($edgeExists$($fromNode$,$ toNode$)||(!$directed && edgeExists$($toNode$,$ fromNode$)))\{$

return false;

$\}$

Double weight $=$ euclideanDistance$($fromNode$,$ toNode$)$;

Edge newEdge $=$ new Edge$($fromNode$,$ toNode, weight$)$;

newEdge.next $=$ edges.get$($fromNode$)$;

edges.set$($fromNode$,$ newEdge$)$;

if $(!$directed$)\{$

newEdge $=$ new Edge$($toNode$,$ fromNode, weight$)$;

newEdge.next $=$ edges.get$($toNode$)$;

edges.set$($toNode$,$ newEdge$)$;

$\}$

return true;

$\}$

public Graph computeShortestPath$($int fromNode$)\{$

Graph rv $=$ new Graph$($nodes$.$size$(),$ directed$)$;

return rv;

$\}$

public Graph computeAStar$($int fromNode, int toNode$)\{$

Graph rv $=$ new Graph$($nodes$.$size$(),$ directed$)$;

return rv;

$\}$

public Graph computeMST$()\{$

Graph rv $=$ new Graph$($nodes$.$size$(),$ directed$)$;

return rv;

$\}$

public class OutputEdge $\{$

int fromCoordinateX;

int fromCoordinateY;

int toCoordinateX;

int toCoordinateY;

double edgeWeight;

$\}$

public double getTotalWeight$()\{$

Double total $=0\mathrm{.}0$;

Iterator iter $=$ edges.iterator$()$;

while $($iter$.$hasNext$())\{$

Edge current $=$ iter.next$()$;

while $($null $!=$ current$)\{$

total $+=$ current.weight;

current $=$ current.next;

$\}$

$\}$

return $($directed$)?$ tota