public class AStar extends Object implements Algorithm
A* computes the shortest path from a node to another in a graph. It guarantees that the path found is the shortest one, given its heuristic is admissible, and a path exists between the two nodes. It will fail if the two nodes are in two distinct connected components.
In this A* implementation, the various costs (often called g, h and f) are
given by a AStar.Costs
class. This class
must provide a way to compute:
By default the AStar.Costs
implementation
used uses a heuristic that always returns 0. This makes A* an * equivalent of
the Dijkstra algorithm, but also makes it less efficient.
If there are several equivalent shortest paths between the two nodes, the returned one is arbitrary. Therefore this AStar algorithm works with multigraphs but if two edges between two nodes have the same properties, the one that will be chosen will be arbitrary.
The basic usage is to create an instance of A* (optionally specify a AStar.Costs
object), then to ask it to compute from a shortest path from one target to one
destination, and finally to ask for that path:
AStart astar = new AStar(graph); astar.compute("A", "Z"); // with A and Z node identifiers in the graph. Path path = astar.getShortestPath();
The advantage of A* is that it can consider any cost function to drive the
search. You can (and should) create your own cost functions implementing the
AStar.Costs
interface.
You can also test the default euclidean "distance" cost function on a graph that has
"x" and "y" values. You specify the AStar.Costs
function before calling the
compute(String,String)
method:
AStart astar = new AStar(graph); astar.setCosts(new DistanceCosts()); astar.compute("A", "Z"); Path path = astar.getShortestPath();
import java.io.IOException; import java.io.StringReader; import org.graphstream.algorithm.AStar; import org.graphstream.algorithm.AStar.DistanceCosts; import org.graphstream.graph.Graph; import org.graphstream.graph.implementations.DefaultGraph; import org.graphstream.stream.file.FileSourceDGS; public class AStarTest { // B(1)C // / \ // (1) (10) // / \ // A F // \ / // (1) (1) // \ / // D(1)E static String my_graph = "DGS004\n" + "my 0 0\n" + "an A xy: 0,1\n" + "an B xy: 1,2\n" + "an C xy: 2,2\n" + "an D xy: 1,0\n" + "an E xy: 2,0\n" + "an F xy: 3,1\n" + "ae AB A B weight:1 \n" + "ae AD A D weight:1 \n" + "ae BC B C weight:1 \n" + "ae CF C F weight:10 \n" + "ae DE D E weight:1 \n" + "ae EF E F weight:1 \n" ; public static void main(String[] args) throws IOException { Graph graph = new DefaultGraph("A* Test"); StringReader reader = new StringReader(my_graph); FileSourceDGS source = new FileSourceDGS(); source.addSink(graph); source.readAll(reader); AStar astar = new AStar(graph); //astar.setCosts(new DistanceCosts()); astar.compute("C", "F"); System.out.println(astar.getShortestPath()); } }
Modifier and Type  Class and Description 

protected class 
AStar.AStarNode
Representation of a node in the A* algorithm.

static interface 
AStar.Costs
the distance between the current position and the target.

static class 
AStar.DefaultCosts
An implementation of the Costs interface that provides a default
heuristic.

static class 
AStar.DistanceCosts
An implementation of the Costs interface that assume that the weight of
edges is an Euclidean distance in 2D or 3D.

Modifier and Type  Field and Description 

protected HashMap<Node,AStar.AStarNode> 
closed
The closed set.

protected AStar.Costs 
costs
How to compute the path cost, the cost between two nodes and the
heuristic.

protected Graph 
graph
The graph.

protected HashMap<Node,AStar.AStarNode> 
open
The open set.

protected boolean 
pathFound
Set to false if the algorithm ran, but did not found any path from the
source to the target, or if the algorithm did not run yet.

protected Path 
result
If found the shortest path is stored here.

protected String 
source
The source node id.

protected String 
target
The target node id.

Constructor and Description 

AStar()
New A* algorithm.

AStar(Graph graph)
New A* algorithm on a given graph.

AStar(Graph graph,
String src,
String trg)
New A* algorithm on the given graph.

Modifier and Type  Method and Description 

protected void 
aStar(Node sourceNode,
Node targetNode)
The A* algorithm proper.

Path 
buildPath(AStar.AStarNode target)
Build the shortest path from the target/destination node, following the
parent links.

protected void 
clearAll()
Clear the already computed path.

void 
compute()
Run the algorithm.

void 
compute(String source,
String target)

protected AStar.AStarNode 
getNextBetterNode()
Find the node with the lowest rank in the open list.

Path 
getShortestPath()
The computed path, or null if nor result was found.

void 
init(Graph graph)
Initialization of the algorithm.

boolean 
noPathFound()
After having called
compute() or
compute(String, String) , if the getShortestPath()
returns null, or this method return true, there is no path from the given
source node to the given target node. 
void 
setCosts(AStar.Costs costs)
Specify how various costs are computed.

void 
setSource(String nodeName)
Change the source node.

void 
setTarget(String nodeName)
Change the target node.

protected AStar.Costs costs
protected HashMap<Node,AStar.AStarNode> open
protected HashMap<Node,AStar.AStarNode> closed
protected boolean pathFound
public AStar()
public AStar(Graph graph)
graph
 The graph where the algorithm will compute paths.public void setSource(String nodeName)
nodeName
 Identifier of the source node.public void setTarget(String nodeName)
nodeName
 Identifier of the target node.public void setCosts(AStar.Costs costs)
costs
 The cost method to use.public void init(Graph graph)
Algorithm
Algorithm.compute()
method to initialize or reset the algorithm according
to the new given graph.public void compute()
Algorithm
Algorithm.init(Graph)
method has to be called
before computing.compute
in interface Algorithm
Algorithm.init(Graph)
public Path getShortestPath()
public boolean noPathFound()
compute()
or
compute(String, String)
, if the getShortestPath()
returns null, or this method return true, there is no path from the given
source node to the given target node. In other words, the graph has
several connected components. It also return true if the algorithm did
not run.public Path buildPath(AStar.AStarNode target)
target
 The destination node.public void compute(String source, String target)
source
 Identifier of the source node.target
 Identifier of the target node.protected void clearAll()
protected void aStar(Node sourceNode, Node targetNode)
sourceNode
 The source node.targetNode
 The target node.protected AStar.AStarNode getNextBetterNode()
WebARTS Library Licensed Under the GNU  General Public License. Other Libraries licensed under their respective Open Source Licenses