public class AStar extends java.lang.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 

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.

Constructor and Description 

AStar()
New A* algorithm.

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

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

Modifier and Type  Method and Description 

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

void 
compute()
Run the algorithm.

void 
compute(java.lang.String source,
java.lang.String target)

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

void 
init(org.graphstream.graph.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(java.lang.String nodeName)
Change the source node.

void 
setTarget(java.lang.String nodeName)
Change the target node.

public AStar()
public AStar(org.graphstream.graph.Graph graph)
graph
 The graph where the algorithm will compute paths.public AStar(org.graphstream.graph.Graph graph, java.lang.String src, java.lang.String trg)
graph
 The graph where the algorithm will compute paths.src
 The start node.trg
 The destination node.public void setSource(java.lang.String nodeName)
nodeName
 Identifier of the source node.public void setTarget(java.lang.String nodeName)
nodeName
 Identifier of the target node.public void setCosts(AStar.Costs costs)
costs
 The cost method to use.public void init(org.graphstream.graph.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 org.graphstream.graph.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 org.graphstream.graph.Path buildPath(org.graphstream.algorithm.AStar.AStarNode target)
target
 The destination node.public void compute(java.lang.String source, java.lang.String target)
source
 Identifier of the source node.target
 Identifier of the target node.