Class EppsteinShortestPathIterator<V,E>
- java.lang.Object
-
- org.jgrapht.alg.shortestpath.EppsteinShortestPathIterator<V,E>
-
- Type Parameters:
V
- the graph vertex typeE
- 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$ tosink
. 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 thesource
and thesink
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 ingraph
. 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 tosink
.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
andsink
.This implementation has several improvements in comparison to the original description in the article:
- An outgoing edge of vertex $v$ is inserted in the paths graph iff it is reachable from the
source
. - The cross edges in the paths graph are added only for those vertices which are reachable from the root vertex.
- 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 graphgraph
rooted atsink
.private Graph<V,E>
graph
Underlying graph.private java.util.Map<V,EppsteinShortestPathIterator.PathsGraphVertex>
hMapping
For each vertex $v$ ingraph
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.
-
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 ofsource
in the paths graph.private void
addExtension(EppsteinShortestPathIterator.EppsteinGraphPath path, EppsteinShortestPathIterator.PathsGraphVertex extendingVertex, double weight)
Adds an extension ofpaths
withextendingVertex
being its last element.private void
addOneEdgeExtension(EppsteinShortestPathIterator.EppsteinGraphPath path)
Adds all one-edge extension of thepath
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 ofsource
.private void
buildDGraph()
If thegraph
is denoted by $G$, then for every vertex $v$ reachable fromsource
in $G$ $D(G)$ contains balanced heaps of all outroots, which corresponds to vertices on the path from $v$ tosink
.private void
buildPathsGraph()
Guides the building process of the paths graph.private double
delta(E e)
Calculates the $\delta(e)$ value for a given edgee
.private Pair<EppsteinShortestPathIterator.PathsGraphVertex,EppsteinShortestPathIterator.PathsGraphVertex>
getOutrootAndRestHeapRoot(V v)
Builds outroot and heapification of other sidetracks ofv
.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 invertices
starting at positioni
.boolean
hasNext()
private void
heapify(java.util.List<EppsteinShortestPathIterator.PathsGraphVertex> vertices, int size)
Builds a min-heap out of thevertices
listprivate EppsteinShortestPathIterator.PathsGraphVertex
insertPersistently(EppsteinShortestPathIterator.PathsGraphVertex root, EppsteinShortestPathIterator.PathsGraphVertex vertex)
Insertsvertex
into the balanced heap rooted atroot
in a persistent (non-destructive) way.private void
insertVertex(V v, EppsteinShortestPathIterator.PathsGraphVertex predecessorHeap)
Guides the process of adding the sidetracks ofv
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)
-
-
-
Field Detail
-
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 graphgraph
rooted atsink
.
-
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$ ingraph
maintains the root of the balanced heap, which corresponds to it.
-
-
Method Detail
-
hasNext
public boolean hasNext()
- Specified by:
hasNext
in interfacejava.util.Iterator<V>
-
addOneEdgeExtension
private void addOneEdgeExtension(EppsteinShortestPathIterator.EppsteinGraphPath path)
Adds all one-edge extension of thepath
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 ofpaths
withextendingVertex
being its last element.- Parameters:
path
- path to put extension ofextendingVertex
- vertex to extend path withweight
- 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 thegraph
is denoted by $G$, then for every vertex $v$ reachable fromsource
in $G$ $D(G)$ contains balanced heaps of all outroots, which corresponds to vertices on the path from $v$ tosink
. If there are no sidetracks on the path from $v$ tosink
, 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 ofsource
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 ofsource
.
-
insertVertex
private void insertVertex(V v, EppsteinShortestPathIterator.PathsGraphVertex predecessorHeap)
Guides the process of adding the sidetracks ofv
to the paths graph. First receives the outroot and root of the rest heap ofv
by callinggetOutrootAndRestHeapRoot(Object)
. If the outroot if $null$ maps $v$ topredecessorHeap
inhMapping
. Otherwise inserts outroot of $v$ in the balanced heap rooted atpredecessorHeap
and links it to the received rest heap root.- Parameters:
v
- vertexpredecessorHeap
- balanced heap root
-
insertPersistently
private EppsteinShortestPathIterator.PathsGraphVertex insertPersistently(EppsteinShortestPathIterator.PathsGraphVertex root, EppsteinShortestPathIterator.PathsGraphVertex vertex)
Insertsvertex
into the balanced heap rooted atroot
in a persistent (non-destructive) way. Return root of the modified heap.- Parameters:
root
- root of a balanced heapvertex
- 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 ofv
.- 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 thevertices
list- Parameters:
vertices
- verticessize
- 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 invertices
starting at positioni
.- Parameters:
vertices
- heapified verticesi
- heap start positionsize
- 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 edgee
.- Parameters:
e
- edge- Returns:
- value of $\delta(e)$
-
-