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 multi-graphs 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.