Class YenShortestPathIterator<V,E>

java.lang.Object
org.jgrapht.alg.shortestpath.YenShortestPathIterator<V,E>
Type Parameters:
V - the graph vertex type
E - the graph edge type
All Implemented Interfaces:
Iterator<GraphPath<V,E>>
public class YenShortestPathIterator<V,E> extends Object implements Iterator<GraphPath<V,E>>
Iterator over the shortest loopless paths between two vertices in a graph sorted by weight.

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.

The main idea of this algorithm is to divide each path between the source and the sink into the root part - the part that coincides within some of the paths computed so far, and the spur part, the part that deviates from all other paths computed so far. Therefore, for each path the algorithm maintains a vertex, at which the path deviates from its "parent" path (the candidate path using which it was computed).

First the algorithm finds the shortest path between the source and the sink, which is put into the candidates heap. The source is assigned to be its deviation vertex. Then on each iteration the algorithm takes a candidate from the heap with minimum weight, puts it into the result list and builds all possible deviations from it wrt. other paths, that are in the result list. By generating spur paths starting only from the vertices that are after the deviation vertex of current path (including the deviation vertex) it is possible to avoid building duplicated candidates.

Additionally, the algorithm supports path validation by means of PathValidator.

See Also:

  • Field Details

    • graph

      private final Graph<V,E> graph
      Underlying graph.

    • source

      private final V source
      Source vertex.

    • sink

      private final V sink
      Sink vertex.

    • pathValidator

      private PathValidator<V,E> pathValidator
      Provides possibility to validate computed paths and exclude invalid ones. Whenever a candidate path $P$ first deviation vertex $u$ is produces by this algorithm, it is passed to getLastValidDeviation() to find the last valid deviation vertex $v$ for it. The algorithm puts obtained vertex in lastDeviations map. If vertex $v$ is null, the candidate is considered correct. Otherwise for the path $P$ deviation are built only from vertices between $u$ and $v$ inclusive.

    • resultList

      private List<GraphPath<V,E>> resultList
      List of the paths returned so far via the next() method.

    • candidatePaths

      private org.jheaps.AddressableHeap<Double, Pair<GraphPath<V,E>, Boolean>> candidatePaths
      Heap of the candidate path generated so far and sorted my their weights. There is a boolean flag for every candidate in the queue, which indicates, if the path is valid ot not. An invalid path is a path which contains an edge which fails the pathValidator check. Invalid paths are kept in the queue, because it is possible to build a valid path by deviating from an invalid one.

    • firstDeviations

      private Map<GraphPath<V,E>, V> firstDeviations
      For each path $P$, stores its deviation point.

      A path deviation point is a first node in the path that doesn't belong to the parent path. If the path doesn't have a parent (which is only possible for one shortest path between the source and the sink), this map stores its first node.

    • lastDeviations

      private Map<GraphPath<V,E>, V> lastDeviations
      For each path $P$ stores the vertex $u$ such that $pathValidator#isValidPath([start_vertex, u], (u,v)) = false$, where $[start_vertex, u]$ denotes the subpath of $P$ from its start to vertex $u$ and $v$ is the next vertex in $P$ after $u$. Stores null, if there is no such vertex.

    • numberOfValidPathInQueue

      private int numberOfValidPathInQueue
      Stores number of valid candidates in candidatePaths.

    • shortestPathComputed

      private boolean shortestPathComputed
      Indicates if the lazyInitializePathHeap procedure has already been executed.

  • Constructor Details

    • YenShortestPathIterator

      public YenShortestPathIterator(Graph<V,E> graph, V source, V sink)
      Constructs an instance of the algorithm for given graph, source and sink.
      Parameters:
      graph - graph
      source - source vertex
      sink - sink vertex

    • YenShortestPathIterator

      public YenShortestPathIterator(Graph<V,E> graph, V source, V sink, PathValidator<V,E> pathValidator)
      Constructs an instance of the algorithm for given graph, source, sink and pathValidator. The pathValidator can be null, which will indicate that all paths are valid.
      Parameters:
      graph - graph
      source - source vertex
      sink - sink vertex
      pathValidator - validator to computed paths

    • YenShortestPathIterator

      public YenShortestPathIterator(Graph<V,E> graph, V source, V sink, Supplier<org.jheaps.AddressableHeap<Double, Pair<GraphPath<V,E>, Boolean>>> heapSupplier)
      Constructs an instance of the algorithm for given graph, source, sink and heapSupplier.
      Parameters:
      graph - graph
      source - source vertex
      sink - sink vertex
      heapSupplier - supplier of the preferable heap implementation

    • YenShortestPathIterator

      public YenShortestPathIterator(Graph<V,E> graph, V source, V sink, Supplier<org.jheaps.AddressableHeap<Double, Pair<GraphPath<V,E>, Boolean>>> heapSupplier, PathValidator<V,E> pathValidator)
      Constructs an instance of the algorithm for given graph, source, sink, heapSupplier and pathValidator. The pathValidator can be null, which will indicate that all paths are valid.
      Parameters:
      graph - graph
      source - source vertex
      sink - sink vertex
      heapSupplier - supplier of the preferable heap implementation
      pathValidator - validator for computed paths

  • Method Details

    • lazyInitializePathHeap

      private void lazyInitializePathHeap()
      Lazily initializes the path heap by computing the shortest path between the source and the sink and building a necessary amount of paths until at least one valid path is found. Note: this computation is done only once during the first call to either hasNext() or next().

    • ensureAtLeastOneValidPathInQueue

      private void ensureAtLeastOneValidPathInQueue()
      This method is used to make sure that there exist at least one valid path on the queue. During the iteration if the candidates queue is not empty then the iterator has next value. Otherwise is does not.

    • getLastValidDeviation

      private V getLastValidDeviation(GraphPath<V,E> path, V firstDeviation)
      Computes vertex $u$ such that $pathValidator#isValidPath([start_vertex, u], (u,v)) = false$, where $[start_vertex, u]$ denotes the subpath of $P$ from its start to vertex $u$ and $v$ is the next vertex in $P$ after $u$. Returns null if there is no such vertex.
      Parameters:
      path - graph path
      firstDeviation - vertex at which path deviates from its parent path
      Returns:
      vertex which is last valid deviation for path

    • hasNext

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

    • next

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

    • addDeviations

      private int addDeviations(GraphPath<V,E> path)
      Builds unique loopless deviations from the given path in the graph. First receives the deviation vertex of the current path as well as sets of vertices and edges to be masked during the computations. Then creates an instance of the MaskSubgraph and builds a reversed shortest paths tree starting at sink in it. Finally builds new candidate paths by deviating from the vertices of the provided path. Puts only those candidates in the candidatesList, which deviate from path between $firstDeviation$ and $lastDeviation$. $firstDeviation$ and $lastDeviation$ are obtainer from firstDeviations and lastDeviations correspondingly.

      For more information on this step refer to the article with the original description of the algorithm.

      Parameters:
      path - path to build deviations of
      Returns:
      number of computed valid deviations

    • getMaskedVerticesAndEdges

      private Pair<Set<V>,Set<E>> getMaskedVerticesAndEdges(GraphPath<V,E> path, V pathDeviation, int pathDeviationIndex)
      For the given path builds sets of vertices and edges to be masked. First masks all edges and vertices of the provided path except for the sink. Then for each path in the resultList that coincides in the path until the pathDeviation masks the edge between the pathDeviation and its successor in this path.
      Parameters:
      path - path to mask vertices and edges of
      pathDeviation - deviation vertex of the path
      pathDeviationIndex - index of the deviation vertex in the vertices list of the path
      Returns:
      pair of sets of masked vertices and edges

    • getCandidatePath

      private GraphPath<V,E> getCandidatePath(GraphPath<V,E> path, int recoverVertexIndex, GraphPath<V,E> spurPath)
      Builds a candidate path based on the information provided in the methods parameters. First adds the root part of the candidate by traversing the vertices and edges of the path until the recoverVertexIndex. Then adds vertices and edges of the spurPath.
      Parameters:
      path - path the candidate path deviates from
      recoverVertexIndex - vertex that is being recovered
      spurPath - spur path of the candidate
      Returns:
      candidate path

    • equalLists

      private boolean equalLists(List<V> first, List<V> second, int index)
      Checks if the lists have the same content until the index (inclusive).
      Parameters:
      first - first list
      second - second list
      index - position in the lists
      Returns:
      true iff the contents of the list are equal until the index