|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
ObjectAbstractGraphIterator
SourceGraphIterator
AStarIterator
public class AStarIterator
A Star : It 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: - The path-cost function (usually denoted g(x), which may or may not be a heuristic) and - An admissible "heuristic estimate" (usually denoted h(x)). the itaration oparates as follows: // 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 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 |