Module org.jgrapht.core
Package 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.

  • Field Details

  • Constructor Details

    • 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 Details

    • hasNext

      public boolean hasNext()
      Specified by:
      hasNext in interface Iterator<V>

    • next

      public GraphPath<V,E> next()
      Specified by:
      next in interface Iterator<V>

    • addOneEdgeExtension

      private void addOneEdgeExtension(EppsteinShortestPathIterator<V,E>.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<V,E>.EppsteinGraphPath path, EppsteinShortestPathIterator<V,E>.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<V,E>.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<V,E>.PathsGraphVertex insertPersistently(EppsteinShortestPathIterator<V,E>.PathsGraphVertex root, EppsteinShortestPathIterator<V,E>.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<V,E>.PathsGraphVertex,EppsteinShortestPathIterator<V,E>.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(List<EppsteinShortestPathIterator<V,E>.PathsGraphVertex> vertices, int size)
      Builds a min-heap out of the vertices list
      Parameters:
      vertices - vertices
      size - size of vertices

    • siftDown

      private void siftDown(List<EppsteinShortestPathIterator<V,E>.PathsGraphVertex> vertices, int i, int size)

    • getRestHeap

      private EppsteinShortestPathIterator<V,E>.PathsGraphVertex getRestHeap(List<EppsteinShortestPathIterator<V,E>.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(List<EppsteinShortestPathIterator<V,E>.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)$