|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
ObjectAbstractGraphIterator
SourceGraphIterator
AStarIterator
public class AStarIterator
A path iterator that uses a function (usually denoted f(x)) to determine the order in which the algorithm visits nodes, f(x) is a sum of two functions:
// COST(n,n') : the real cost to go from n to n'
OPEN = [Source]
CLOSE = []
while ( |OPEN| > 0 )
n = a node in OPEN with less f
remove n from OPEN
add n to CLOSE
if ( n == target ) {
return // path find
// if n != target
for each node n' that relates to n do
if n' in OPEN
if (g(n) + COST(n,n')) < g(n')
g(n') = g(n) + COST(n,n')
parent(n') = n
else
g(n') = g(n) + COST(n,n')
parent(n') = n
add n' to OPEN
// end while
For more details see http://en.wikipedia.org/wiki/A_star
Nested Class Summary | |
---|---|
static class |
AStarIterator.AStarFunctions
Defines the functions needed by A Star. |
static class |
AStarIterator.AStarNode
Internal data structure used to track node costs, and parent nodes. |
Constructor Summary | |
---|---|
AStarIterator(Node source,
AStarIterator.AStarFunctions afuncs)
|
Method Summary | |
---|---|
void |
cont(Graphable current,
GraphTraversal traversal)
Makes a step of the A* algorithm. |
Node |
getParent(Node n)
|
void |
init(Graph graph,
GraphTraversal traversal)
Does Nothing. |
void |
killBranch(Graphable current,
GraphTraversal traversal)
Kills the branch of the traversal |
Graphable |
next(GraphTraversal traversal)
Returns the next node in the priority queue. if the queue is empty then there is no path from the source to the destiny in this graph. |
Methods inherited from class SourceGraphIterator |
---|
getSource, setSource |
Methods inherited from class AbstractGraphIterator |
---|
getGraph, getTraversal, getWalker, setTraversal |
Methods inherited from class Object |
---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
Constructor Detail |
---|
public AStarIterator(Node source, AStarIterator.AStarFunctions afuncs)
Method Detail |
---|
public void init(Graph graph, GraphTraversal traversal)
graph
- The graph being whose components are being iterated over.public Graphable next(GraphTraversal traversal)
org.geotools.graph.traverse.GraphIterator#next()
public void cont(Graphable current, GraphTraversal traversal)
current
- The current component of the traversal.org.geotools.graph.traverse.GraphIterator#cont(Graphable)
public void killBranch(Graphable current, GraphTraversal traversal)
current
- The current component of the traversal.org.geotools.graph.traverse.GraphIterator#killBranch(Graphable)
public Node getParent(Node n)
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |