Skip navigation links
WebARTS Design
Java Library

Version 0.10.2
2020-11-11 (Wed), 10:42:54
org.graphstream.algorithm

## Class AStar

• All Implemented Interfaces:
Algorithm

```public class AStar
extends Object
implements Algorithm```
An implementation of the A* 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:

• The cost of moving from a node to another, often called g;
• The estimated cost from a node to the destination, the heuristic, often noted h;
• f is the sum of g and h and is computed automatically.

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.

## Usage

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();
```

## Example

``` 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());
}
}
```
• ### Nested Class Summary

Nested Classes
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.
• ### Field Summary

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

Constructors
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.
• ### Method Summary

All Methods
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.
• ### Methods inherited from class java.lang.Object

`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`
• ### Field Detail

• #### graph

`protected Graph graph`
The graph.
• #### source

`protected String source`
The source node id.
• #### target

`protected String target`
The target node id.
• #### costs

`protected AStar.Costs costs`
How to compute the path cost, the cost between two nodes and the heuristic. The heuristic to estimate the distance from the current position to the target.
• #### open

`protected HashMap<Node,AStar.AStarNode> open`
The open set.
• #### closed

`protected HashMap<Node,AStar.AStarNode> closed`
The closed set.
• #### result

`protected Path result`
If found the shortest path is stored here.
• #### pathFound

`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.
• ### Constructor Detail

• #### AStar

`public AStar()`
New A* algorithm.
• #### AStar

`public AStar(Graph graph)`
New A* algorithm on a given graph.
Parameters:
`graph` - The graph where the algorithm will compute paths.
• #### AStar

```public AStar(Graph graph,
String src,
String trg)```
New A* algorithm on the given graph.
Parameters:
`graph` - The graph where the algorithm will compute paths.
`src` - The start node.
`trg` - The destination node.
• ### Method Detail

• #### setSource

`public void setSource(String nodeName)`
Change the source node. This clears the already computed path, but preserves the target node name.
Parameters:
`nodeName` - Identifier of the source node.
• #### setTarget

`public void setTarget(String nodeName)`
Change the target node. This clears the already computed path, but preserves the source node name.
Parameters:
`nodeName` - Identifier of the target node.
• #### setCosts

`public void setCosts(AStar.Costs costs)`
Specify how various costs are computed. The costs object is in charge of computing the cost of displacement from one node to another (and therefore allows to compute the cost from the source node to any node). It also allows to compute the heuristic to use for evaluating the cost from the current position to the target node. Calling this DOES NOT clear the currently computed paths.
Parameters:
`costs` - The cost method to use.
• #### init

`public void init(Graph graph)`
Description copied from interface: `Algorithm`
Initialization of the algorithm. This method has to be called before the `Algorithm.compute()` method to initialize or reset the algorithm according to the new given graph.
Specified by:
`init` in interface `Algorithm`
Parameters:
`graph` - The graph this algorithm is using.
• #### compute

`public void compute()`
Description copied from interface: `Algorithm`
Run the algorithm. The `Algorithm.init(Graph)` method has to be called before computing.
Specified by:
`compute` in interface `Algorithm`
See Also:
`Algorithm.init(Graph)`
• #### getShortestPath

`public Path getShortestPath()`
The computed path, or null if nor result was found.
Returns:
The computed path, or null if no path was found.
• #### noPathFound

`public 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. In other words, the graph has several connected components. It also return true if the algorithm did not run.
Returns:
True if there is no possible path from the source to the destination or if the algorithm did not run.
• #### buildPath

`public Path buildPath(AStar.AStarNode target)`
Build the shortest path from the target/destination node, following the parent links.
Parameters:
`target` - The destination node.
Returns:
The path.
• #### clearAll

`protected void clearAll()`
Clear the already computed path. This does not clear the source node name, the target node name and the weight attribute name.
• #### aStar

```protected void aStar(Node sourceNode,
Node targetNode)```
The A* algorithm proper.
Parameters:
`sourceNode` - The source node.
`targetNode` - The target node.
• #### getNextBetterNode

`protected AStar.AStarNode getNextBetterNode()`
Find the node with the lowest rank in the open list.
Returns:
The node of open that has the lowest rank.
Skip navigation links
Copyright (C) 2001-2021, Tom B. Gutwin

WebARTS Library Licensed Under the GNU - General Public License. Other Libraries licensed under their respective Open Source Licenses