java.lang.Object
- org.jgrapht.alg.shortestpath.EppsteinShortestPathIterator<V,E>

Type Parameters:

V - the graph vertex type

E - the graph edge type

All Implemented Interfaces:

java.util.Iterator<GraphPath<V,E>>
```
public class EppsteinShortestPathIterator<V,E>
extends java.lang.Object
implements java.util.Iterator<GraphPath<V,E>>
```
Iterator over the shortest paths (not required to be simple) between two vertices in a graph sorted by weight.
This implementation can only be used for directed simple graphs. Also for this iterator to work correctly the graph must not be modified during iteration. Currently there are no means to ensure that, nor to fail-fast. The results of such modifications are undefined.
First the shortest paths tree in the edge reversed graph starting at sink is built. Thus we get distances $d(v)$ from every vertex $v$ to sink. We then define a sidetrack edge to be an edge, which is not in the shortest paths tree. The key observation is that every path between the source and the sink can be solely determined by a sub-sequence of its edges which are sidetracks.
Let $d(v)$ be the distance from $v$ to sink and $w()$ be the weight function for edges in graph. If $e$ connects a pair of vertices $(u, w)$, the $\delta(e)$ is defined as $w(e)+d(w)-d(u)$. Intuitively, $\delta(e)$ measures how much distance is lost by being “sidetracked” along $e$ instead of taking a shortest path to sink.
The idea of the algorithm is to build a heap of sidetracks. This heap can be then traversed with breadth-first search in order to retrieve the implicit representations of the paths between source and sink.
This implementation has several improvements in comparison to the original description in the article:
1. An outgoing edge of vertex $v$ is inserted in the paths graph iff it is reachable from the source.
2. The cross edges in the paths graph are added only for those vertices which are reachable from the root vertex.
3. Weights of the edges in the paths graph are mot maintained explicitly, because they are computed during its traversal.

Nested Class Summary

Nested Classes
Modifier and Type	Class	Description
`private class`	`EppsteinShortestPathIterator.EppsteinGraphPath`	Represents a path that is generated during the computations.
`private class`	`EppsteinShortestPathIterator.PathsGraphVertex`	Vertex of the paths graph.

Field Summary

Fields
Modifier and Type	Field	Description
`private java.util.Map<V,Pair<java.lang.Double,E>>`	`distanceAndPredecessorMap`	Shortest paths tree in the edge reversed graph `graph` rooted at `sink`.
`private Graph<V,E>`	`graph`	Underlying graph.
`private java.util.Map<V,EppsteinShortestPathIterator.PathsGraphVertex>`	`hMapping`	For each vertex $v$ in `graph` maintains the root of the balanced heap, which corresponds to it.
`private EppsteinShortestPathIterator.PathsGraphVertex`	`pathsGraphRoot`	Vertex of the paths graph from which the BFS traversal is started.
`private java.util.Queue<EppsteinShortestPathIterator.EppsteinGraphPath>`	`pathsQueue`	Priority queue of the paths generated during the computation.
`private V`	`sink`	Sink vertex.
`private V`	`source`	Source vertex.

Constructor Summary

Constructors
Constructor	Description
`EppsteinShortestPathIterator(Graph<V,E> graph, V source, V sink)`	Constructs an instance of the algorithm for the given `graph`, `source` and `sink`.

Method Summary

All Methods Instance Methods Concrete Methods
Modifier and Type	Method	Description
`private void`	`addCrossEdges()`	Adds cross edges for every vertex $v$ reachable from the root of balanced heap of `source` in the paths graph.
`private void`	`addExtension(EppsteinShortestPathIterator.EppsteinGraphPath path, EppsteinShortestPathIterator.PathsGraphVertex extendingVertex, double weight)`	Adds an extension of `paths` with `extendingVertex` being its last element.
`private void`	`addOneEdgeExtension(EppsteinShortestPathIterator.EppsteinGraphPath path)`	Adds all one-edge extension of the `path` wrt the paths graph.
`private void`	`addPathGraphRoot()`	Creates the root vertex $r$ of the paths graph and connects it to the root of the balanced heap of `source`.
`private void`	`buildDGraph()`	If the `graph` is denoted by $G$, then for every vertex $v$ reachable from `source` in $G$ $D(G)$ contains balanced heaps of all outroots, which corresponds to vertices on the path from $v$ to `sink`.
`private void`	`buildPathsGraph()`	Guides the building process of the paths graph.
`private double`	`delta(E e)`	Calculates the $\delta(e)$ value for a given edge `e`.
`private Pair<EppsteinShortestPathIterator.PathsGraphVertex,EppsteinShortestPathIterator.PathsGraphVertex>`	`getOutrootAndRestHeapRoot(V v)`	Builds outroot and heapification of other sidetracks of `v`.
`private EppsteinShortestPathIterator.PathsGraphVertex`	`getRestHeap(java.util.List<EppsteinShortestPathIterator.PathsGraphVertex> vertices, int i, int size)`	Constructs an explicit tree-like representation of the binary heap contained in `vertices` starting at position `i`.
`boolean`	`hasNext()`
`private void`	`heapify(java.util.List<EppsteinShortestPathIterator.PathsGraphVertex> vertices, int size)`	Builds a min-heap out of the `vertices` list
`private EppsteinShortestPathIterator.PathsGraphVertex`	`insertPersistently(EppsteinShortestPathIterator.PathsGraphVertex root, EppsteinShortestPathIterator.PathsGraphVertex vertex)`	Inserts `vertex` into the balanced heap rooted at `root` in a persistent (non-destructive) way.
`private void`	`insertVertex(V v, EppsteinShortestPathIterator.PathsGraphVertex predecessorHeap)`	Guides the process of adding the sidetracks of `v` to the paths graph.
`GraphPath<V,E>`	`next()`
`private void`	`siftDown(java.util.List<EppsteinShortestPathIterator.PathsGraphVertex> vertices, int i, int size)`
`private void`	`swap(java.util.List<EppsteinShortestPathIterator.PathsGraphVertex> vertices, int i, int j)`

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface java.util.Iterator
forEachRemaining, remove

- Field Detail
  - graph
```
private final Graph<V,E> graph
```
    Underlying graph.
  - source
```
private final V source
```
    Source vertex.
  - sink
```
private final V sink
```
    Sink vertex.
  - pathsGraphRoot
```
private EppsteinShortestPathIterator.PathsGraphVertex pathsGraphRoot
```
    Vertex of the paths graph from which the BFS traversal is started.
  - distanceAndPredecessorMap
```
private java.util.Map<V,Pair<java.lang.Double,E>> distanceAndPredecessorMap
```
    Shortest paths tree in the edge reversed graph graph rooted at sink.
  - pathsQueue
```
private java.util.Queue<EppsteinShortestPathIterator.EppsteinGraphPath> pathsQueue
```
    Priority queue of the paths generated during the computation.
  - hMapping
```
private java.util.Map<V,EppsteinShortestPathIterator.PathsGraphVertex> hMapping
```
    For each vertex $v$ in graph maintains the root of the balanced heap, which corresponds to it.
- Constructor Detail
  - EppsteinShortestPathIterator
```
public EppsteinShortestPathIterator(Graph<V,E> graph,
                                    V source,
                                    V sink)
```
    Constructs an instance of the algorithm for the given graph, source and sink.
    
    Parameters:
    
    graph - graph
    
    source - source vertex
    
    sink - sink vertex
- Method Detail
  - hasNext
```
public boolean hasNext()
```
    Specified by:
    
    hasNext in interface java.util.Iterator<V>
  - next
```
public GraphPath<V,E> next()
```
    Specified by:
    
    next in interface java.util.Iterator<V>
  - addOneEdgeExtension
```
private void addOneEdgeExtension(EppsteinShortestPathIterator.EppsteinGraphPath path)
```
    Adds all one-edge extension of the path wrt the paths graph.
    
    Parameters:
    
    path - path to put extensions of
  - addExtension
```
private void addExtension(EppsteinShortestPathIterator.EppsteinGraphPath path,
                          EppsteinShortestPathIterator.PathsGraphVertex extendingVertex,
                          double weight)
```
    Adds an extension of paths with extendingVertex being its last element.
    
    Parameters:
    
    path - path to put extension of
    
    extendingVertex - vertex to extend path with
    
    weight - weight of the resulting path
  - buildPathsGraph
```
private void buildPathsGraph()
```
    Guides the building process of the paths graph. The process is divided into three stages. First the D(g) is constructed, then cross edges are added and finally the root vertex is created.
  - buildDGraph
```
private void buildDGraph()
```
    If the graph is denoted by $G$, then for every vertex $v$ reachable from source in $G$ $D(G)$ contains balanced heaps of all outroots, which corresponds to vertices on the path from $v$ to sink. If there are no sidetracks on the path from $v$ to sink, the value $null$ is stored. An outroot is connected to its rest heap if the corresponding vertex has more than one sidetrack.
  - addCrossEdges
```
private void addCrossEdges()
```
    Adds cross edges for every vertex $v$ reachable from the root of balanced heap of source in the paths graph. If a sidetrack, which corresponds to $v$ connects some pair of vertices $(u,w)$, a cross edge from $v$ to the root of the balanced heap of $w$ is added.
  - addPathGraphRoot
```
private void addPathGraphRoot()
```
    Creates the root vertex $r$ of the paths graph and connects it to the root of the balanced heap of source.
  - insertVertex
```
private void insertVertex(V v,
                          EppsteinShortestPathIterator.PathsGraphVertex predecessorHeap)
```
    Guides the process of adding the sidetracks of v to the paths graph. First receives the outroot and root of the rest heap of v by calling getOutrootAndRestHeapRoot(Object). If the outroot if $null$ maps $v$ to predecessorHeap in hMapping. Otherwise inserts outroot of $v$ in the balanced heap rooted at predecessorHeap and links it to the received rest heap root.
    
    Parameters:
    
    v - vertex
    
    predecessorHeap - balanced heap root
  - insertPersistently
```
private EppsteinShortestPathIterator.PathsGraphVertex insertPersistently(EppsteinShortestPathIterator.PathsGraphVertex root,
                                                                         EppsteinShortestPathIterator.PathsGraphVertex vertex)
```
    Inserts vertex into the balanced heap rooted at root in a persistent (non-destructive) way. Return root of the modified heap.
    
    Parameters:
    
    root - root of a balanced heap
    
    vertex - vertex to be inserted
    
    Returns:
    
    root of the modified heap
  - getOutrootAndRestHeapRoot
```
private Pair<EppsteinShortestPathIterator.PathsGraphVertex,EppsteinShortestPathIterator.PathsGraphVertex> getOutrootAndRestHeapRoot(V v)
```
    Builds outroot and heapification of other sidetracks of v.
    
    Parameters:
    
    v - vertex
    
    Returns:
    
    outroot and rest heap root
  - heapify
```
private void heapify(java.util.List<EppsteinShortestPathIterator.PathsGraphVertex> vertices,
                     int size)
```
    Builds a min-heap out of the vertices list
    
    Parameters:
    
    vertices - vertices
    
    size - size of vertices
  - siftDown
```
private void siftDown(java.util.List<EppsteinShortestPathIterator.PathsGraphVertex> vertices,
                      int i,
                      int size)
```
  - getRestHeap
```
private EppsteinShortestPathIterator.PathsGraphVertex getRestHeap(java.util.List<EppsteinShortestPathIterator.PathsGraphVertex> vertices,
                                                                  int i,
                                                                  int size)
```
    Constructs an explicit tree-like representation of the binary heap contained in vertices starting at position i.
    
    Parameters:
    
    vertices - heapified vertices
    
    i - heap start position
    
    size - size of vertices
    
    Returns:
    
    root of the built heap
  - swap
```
private void swap(java.util.List<EppsteinShortestPathIterator.PathsGraphVertex> vertices,
                  int i,
                  int j)
```
  - delta
```
private double delta(E e)
```
    Calculates the $\delta(e)$ value for a given edge e.
    
    Parameters:
    
    e - edge
    
    Returns:
    
    value of $\delta(e)$

Class EppsteinShortestPathIterator<V,​E>

Nested Class Summary

Field Summary

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Methods inherited from interface java.util.Iterator

Field Detail

graph

source

sink

pathsGraphRoot

distanceAndPredecessorMap

pathsQueue

hMapping

Constructor Detail

EppsteinShortestPathIterator

Method Detail

hasNext

next

addOneEdgeExtension

addExtension

buildPathsGraph

buildDGraph

addCrossEdges

addPathGraphRoot

insertVertex

insertPersistently

getOutrootAndRestHeapRoot

heapify

siftDown

getRestHeap

swap

delta

Class EppsteinShortestPathIterator<V,E>