DijkstraIterator (Geotools modules 20-SNAPSHOT API)

Object
- AbstractGraphIterator
- - SourceGraphIterator
  - - DijkstraIterator

All Implemented Interfaces:

GraphIterator

Direct Known Subclasses:

DirectedDijkstraIterator
```
public class DijkstraIterator
extends SourceGraphIterator
```
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 iteration
 
```
The following is an illustration of the algorithm. Edge weights are labelled in blue and the final node costs are labelled in red.

The nodes are returned in order of increasing cost which yields the sequence A,C,B,D,E,F,G,H,I.
Author:

Justin Deoliveira, Refractions Research Inc, jdeolive@refractions.net

Nested Class Summary

Nested Classes
Modifier and Type	Class and Description
`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

Fields
Modifier and Type	Field and Description
`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

Constructors
Constructor and Description
`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

All Methods Instance Methods Concrete Methods
Modifier and Type	Method and Description
`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
  - weighter
```
protected DijkstraIterator.EdgeWeighter weighter
```
    provides weights for edges in the graph *
  - nweighter
```
protected DijkstraIterator.NodeWeighter nweighter
```
    provides weights for nodes in the graph *
  - queue
```
protected PriorityQueue queue
```
    priority queue to manage active nodes *
  - nodemap
```
protected HashMap<Graphable,DijkstraIterator.DijkstraNode> nodemap
```
    map of graph node to internal dijkstra node *
- Constructor Detail
  - DijkstraIterator
```
public DijkstraIterator(DijkstraIterator.EdgeWeighter weighter)
```
    Constructs a new Dijkstra iterator which uses the specided EdgeWeighter.
    
    Parameters:
    
    weighter - Calculates weights for edges in the graph being iterated over.
  - DijkstraIterator
```
public DijkstraIterator(DijkstraIterator.EdgeWeighter weighter,
                        DijkstraIterator.NodeWeighter nweighter)
```
    Constructs a new Dijkstra iterator which uses the specided EdgeWeighter and NodeWeighter
    
    Parameters:
    
    weighter - Calculates weights for edges in the graph being iterated over.
    
    nweighter - Calculates weights for nodes in the graph being iterated over.
- Method Detail
  - init
```
public void init(Graph graph,
                 GraphTraversal traversal)
```
    Builds internal priority queue to manage node costs.
    
    Parameters:
    
    graph - The graph being whose components are being iterated over.
    
    See Also:
    
    org.geotools.graph.traverse.GraphIterator#init(Graph)
  - next
```
public Graphable next(GraphTraversal traversal)
```
    Returns the next node in the priority queue. If the next node coming out of the queue has infinite cost, then the node is not adjacent to any nodes in the set of nodes with known costs. This situation will end the traversal every other node will also have infinite cost. This usally is the result of a disconnected graph.
    
    Returns:
    
    The next component in the iteration, or null if iteration is complete.
    
    See Also:
    
    org.geotools.graph.traverse.GraphIterator#next()
  - cont
```
public void cont(Graphable current,
                 GraphTraversal traversal)
```
    Looks for adjacent nodes to the current node which are in the adjacent node and updates costs.
    
    Parameters:
    
    current - The current component of the traversal.
    
    See Also:
    
    org.geotools.graph.traverse.GraphIterator#cont(Graphable)
  - killBranch
```
public void killBranch(Graphable current,
                       GraphTraversal traversal)
```
    Kills the branch of the traversal by not updating the cost of any adjacent nodes.
    
    Parameters:
    
    current - The current component of the traversal.
    
    See Also:
    
    org.geotools.graph.traverse.GraphIterator#killBranch(Graphable)
  - getCost
```
public double getCost(Graphable component)
```
    Returns the internal cost of a node which has been calculated by the iterator.
    
    Parameters:
    
    component - The component whose cost to return.
    
    Returns:
    
    The cost associated with the component.
  - getParent
```
public Graphable getParent(Graphable component)
```
    Returns the last node in the known set to update the node. The iteration operates by nodes in the known set updating the cost of nodes in the unknown set. Each time an update occurs, the known node is set as the parent of the unkown node.
    
    Parameters:
    
    component - The node whose parent to return (child)
    
    Returns:
    
    The parent, or null if the method is supplied the source of the iteration.
  - getQueue
```
protected PriorityQueue getQueue()
```
  - getRelated
```
protected Iterator getRelated(Graphable current)
```

Class DijkstraIterator

Nested Class Summary

Field Summary

Constructor Summary

Method Summary

Methods inherited from class SourceGraphIterator

Methods inherited from class AbstractGraphIterator

Methods inherited from class Object

Field Detail

weighter

nweighter

queue

nodemap

Constructor Detail

DijkstraIterator

DijkstraIterator

Method Detail

init

next

cont

killBranch

getCost

getParent

getQueue

getRelated