|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
ObjectAbstractGraphIterator
SourceGraphIterator
DijkstraIterator
public class DijkstraIterator
Iterates over the nodes of a graph in pattern using Dijkstra's
Shortest Path Algorithm. A Dijkstra iteration returns nodes
in an order of increasing cost relative to a specified node
(the source node of the iteration).
In a Dijsktra iteration, a weight is associated with each edge
and a cost with each node. The iteration operates by maintaining
two sets of nodes. The first the set of nodes whose final cost is known, and
the second is the set of nodes whose final cost is unknown.
Initially, every node except for the source node has a cost of infinity, and
resides in the unkown set. The source node has a cost of zero, and is
is a member of the known set.
The iteration operatates as follows:
sn = source node of iteration N = set of all nodes K = set of nodes with known cost = {sn} U = set of nodes with unknown cost = N - K cost(sn) = 0 for each node $un in U cost(un) = infinity while(|U| > 0) for each node n in K find a node un in U that relates to n if cost(n) + weight(n,un) < cost(un) cost(un) = cost(n) + weight(n,un) ln = node with least cost in U remove ln from U add ln to K return ln as next node in iterationThe following is an illustration of the algorithm. Edge weights are labelled in blue and the final node costs are labelled in red.
Nested Class Summary | |
---|---|
protected static class |
DijkstraIterator.DijkstraNode
Internal data structure used to track node costs, and parent nodes. |
static interface |
DijkstraIterator.EdgeWeighter
Supplies a weight for each edge in the graph to be used by the iteration when calculating node costs. |
static interface |
DijkstraIterator.NodeWeighter
Supplies a weight for each pair of adjacent edges. |
Field Summary | |
---|---|
protected HashMap<Graphable,DijkstraIterator.DijkstraNode> |
nodemap
map of graph node to internal dijkstra node |
protected DijkstraIterator.NodeWeighter |
nweighter
provides weights for nodes in the graph |
protected PriorityQueue |
queue
priority queue to manage active nodes |
protected DijkstraIterator.EdgeWeighter |
weighter
provides weights for edges in the graph |
Constructor Summary | |
---|---|
DijkstraIterator(DijkstraIterator.EdgeWeighter weighter)
Constructs a new Dijkstra iterator which uses the specided EdgeWeighter. |
|
DijkstraIterator(DijkstraIterator.EdgeWeighter weighter,
DijkstraIterator.NodeWeighter nweighter)
Constructs a new Dijkstra iterator which uses the specided EdgeWeighter and NodeWeighter |
Method Summary | |
---|---|
void |
cont(Graphable current,
GraphTraversal traversal)
Looks for adjacent nodes to the current node which are in the adjacent node and updates costs. |
double |
getCost(Graphable component)
Returns the internal cost of a node which has been calculated by the iterator. |
Graphable |
getParent(Graphable component)
Returns the last node in the known set to update the node. |
protected PriorityQueue |
getQueue()
|
protected Iterator |
getRelated(Graphable current)
|
void |
init(Graph graph,
GraphTraversal traversal)
Builds internal priority queue to manage node costs. |
void |
killBranch(Graphable current,
GraphTraversal traversal)
Kills the branch of the traversal by not updating the cost of any adjacent nodes. |
Graphable |
next(GraphTraversal traversal)
Returns the next node in the priority queue. |
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 |
Field Detail |
---|
protected DijkstraIterator.EdgeWeighter weighter
protected DijkstraIterator.NodeWeighter nweighter
protected PriorityQueue queue
protected HashMap<Graphable,DijkstraIterator.DijkstraNode> nodemap
Constructor Detail |
---|
public DijkstraIterator(DijkstraIterator.EdgeWeighter weighter)
weighter
- Calculates weights for edges in the graph being iterated
over.public DijkstraIterator(DijkstraIterator.EdgeWeighter weighter, DijkstraIterator.NodeWeighter nweighter)
weighter
- Calculates weights for edges in the graph being iterated
over.nweighter
- Calculates weights for nodes in the graph being iterated
over.Method Detail |
---|
public void init(Graph graph, GraphTraversal traversal)
graph
- The graph being whose components are being iterated over.org.geotools.graph.traverse.GraphIterator#init(Graph)
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 double getCost(Graphable component)
component
- The component whose cost to return.
public Graphable getParent(Graphable component)
component
- The node whose parent to return (child)
protected PriorityQueue getQueue()
protected Iterator getRelated(Graphable current)
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |