org.jgrapht.alg.shortestpath

Class EppsteinShortestPathIterator<V,E>

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:

Iterator<GraphPath<V,E>>

public class EppsteinShortestPathIterator<V,E>
extends Object
implements 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.

Author:

Semen Chudakov

Constructor Summary

Constructors

Constructor and 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

Modifier and Type	Method and Description
boolean	hasNext()
GraphPath<V,E>	next()

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

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 Iterator<GraphPath<V,E>>

next

public GraphPath<V,E> next()

Specified by:

next in interface Iterator<GraphPath<V,E>>