Class YenShortestPathIterator<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 YenShortestPathIterator<V,​E>
    extends java.lang.Object
    implements java.util.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:
    PathValidator
    • Nested Class Summary

      Nested Classes 
      Modifier and Type Class Description
      (package private) class  YenShortestPathIterator.YenShortestPathsTree
      Helper class which represents the shortest paths tree using which the spur parts are computed and appended to the candidate paths
    • Field Summary

      Fields 
      Modifier and Type Field Description
      private org.jheaps.AddressableHeap<java.lang.Double,​Pair<GraphPath<V,​E>,​java.lang.Boolean>> candidatePaths
      Heap of the candidate path generated so far and sorted my their weights.
      private java.util.Map<GraphPath<V,​E>,​V> firstDeviations
      For each path $P$, stores its deviation point.
      private Graph<V,​E> graph
      Underlying graph.
      private java.util.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$.
      private int numberOfValidPathInQueue
      Stores number of valid candidates in candidatePaths.
      private PathValidator<V,​E> pathValidator
      Provides possibility to validate computed paths and exclude invalid ones.
      private java.util.List<GraphPath<V,​E>> resultList
      List of the paths returned so far via the next() method.
      private boolean shortestPathComputed
      Indicates if the lazyInitializePathHeap procedure has already been executed.
      private V sink
      Sink vertex.
      private V source
      Source vertex.
    • Constructor Summary

      Constructors 
      Constructor Description
      YenShortestPathIterator​(Graph<V,​E> graph, V source, V sink)
      Constructs an instance of the algorithm for given graph, source and sink.
      YenShortestPathIterator​(Graph<V,​E> graph, V source, V sink, java.util.function.Supplier<org.jheaps.AddressableHeap<java.lang.Double,​Pair<GraphPath<V,​E>,​java.lang.Boolean>>> heapSupplier)
      Constructs an instance of the algorithm for given graph, source, sink and heapSupplier.
      YenShortestPathIterator​(Graph<V,​E> graph, V source, V sink, java.util.function.Supplier<org.jheaps.AddressableHeap<java.lang.Double,​Pair<GraphPath<V,​E>,​java.lang.Boolean>>> heapSupplier, PathValidator<V,​E> pathValidator)
      Constructs an instance of the algorithm for given graph, source, sink, heapSupplier and pathValidator.
      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.
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      private int addDeviations​(GraphPath<V,​E> path)
      Builds unique loopless deviations from the given path in the graph.
      private void ensureAtLeastOneValidPathInQueue()
      This method is used to make sure that there exist at least one valid path on the queue.
      private boolean equalLists​(java.util.List<V> first, java.util.List<V> second, int index)
      Checks if the lists have the same content until the index (inclusive).
      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.
      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$.
      private Pair<java.util.Set<V>,​java.util.Set<E>> getMaskedVerticesAndEdges​(GraphPath<V,​E> path, V pathDeviation, int pathDeviationIndex)
      For the given path builds sets of vertices and edges to be masked.
      boolean hasNext()
      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.
      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
    • 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.
      • 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 java.util.List<GraphPath<V,​E>> resultList
        List of the paths returned so far via the next() method.
      • candidatePaths

        private org.jheaps.AddressableHeap<java.lang.Double,​Pair<GraphPath<V,​E>,​java.lang.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 java.util.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 java.util.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 Detail

      • 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,
                                       java.util.function.Supplier<org.jheaps.AddressableHeap<java.lang.Double,​Pair<GraphPath<V,​E>,​java.lang.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,
                                       java.util.function.Supplier<org.jheaps.AddressableHeap<java.lang.Double,​Pair<GraphPath<V,​E>,​java.lang.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 Detail

      • 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 java.util.Iterator<V>
      • next

        public GraphPath<V,​E> next()
        Specified by:
        next in interface java.util.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<java.util.Set<V>,​java.util.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​(java.util.List<V> first,
                                   java.util.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