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 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 |
---|---|
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