- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
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:
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescription(package private) class
Helper class which represents the shortest paths tree using which the spur parts are computed and appended to the candidate paths -
Field Summary
FieldsModifier and TypeFieldDescriptionHeap of the candidate path generated so far and sorted my their weights.For each path $P$, stores its deviation point.Underlying graph.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
Stores number of valid candidates incandidatePaths
.private PathValidator
<V, E> Provides possibility to validate computed paths and exclude invalid ones.List of the paths returned so far via thenext()
method.private boolean
Indicates if thelazyInitializePathHeap
procedure has already been executed.private final V
Sink vertex.private final V
Source vertex. -
Constructor Summary
ConstructorsConstructorDescriptionConstructs an instance of the algorithm for givengraph
,source
andsink
.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 givengraph
,source
,sink
andheapSupplier
.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 givengraph
,source
,sink
,heapSupplier
andpathValidator
.YenShortestPathIterator
(Graph<V, E> graph, V source, V sink, PathValidator<V, E> pathValidator) Constructs an instance of the algorithm for givengraph
,source
,sink
andpathValidator
. -
Method Summary
Modifier and TypeMethodDescriptionprivate int
addDeviations
(GraphPath<V, E> path) Builds unique loopless deviations from the given path in thegraph
.private void
This method is used to make sure that there exist at least one valid path on the queue.private boolean
equalLists
(List<V> first, List<V> second, int index) Checks if the lists have the same content until theindex
(inclusive).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$.getMaskedVerticesAndEdges
(GraphPath<V, E> path, V pathDeviation, int pathDeviationIndex) For the givenpath
builds sets of vertices and edges to be masked.boolean
hasNext()
private void
Lazily initializes the path heap by computing the shortest path between thesource
and thesink
and building a necessary amount of paths until at least one valid path is found.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 Details
-
graph
Underlying graph. -
source
Source vertex. -
sink
Sink vertex. -
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 togetLastValidDeviation()
to find the last valid deviation vertex $v$ for it. The algorithm puts obtained vertex inlastDeviations
map. If vertex $v$ isnull
, the candidate is considered correct. Otherwise for the path $P$ deviation are built only from vertices between $u$ and $v$ inclusive. -
resultList
List of the paths returned so far via thenext()
method. -
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 thepathValidator
check. Invalid paths are kept in the queue, because it is possible to build a valid path by deviating from an invalid one. -
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 thesink
), this map stores its first node. -
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$. Storesnull
, if there is no such vertex. -
numberOfValidPathInQueue
private int numberOfValidPathInQueueStores number of valid candidates incandidatePaths
. -
shortestPathComputed
private boolean shortestPathComputedIndicates if thelazyInitializePathHeap
procedure has already been executed.
-
-
Constructor Details
-
YenShortestPathIterator
Constructs an instance of the algorithm for givengraph
,source
andsink
.- Parameters:
graph
- graphsource
- source vertexsink
- sink vertex
-
YenShortestPathIterator
public YenShortestPathIterator(Graph<V, E> graph, V source, V sink, PathValidator<V, E> pathValidator) Constructs an instance of the algorithm for givengraph
,source
,sink
andpathValidator
. ThepathValidator
can benull
, which will indicate that all paths are valid.- Parameters:
graph
- graphsource
- source vertexsink
- sink vertexpathValidator
- 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 givengraph
,source
,sink
andheapSupplier
.- Parameters:
graph
- graphsource
- source vertexsink
- sink vertexheapSupplier
- 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 givengraph
,source
,sink
,heapSupplier
andpathValidator
. ThepathValidator
can benull
, which will indicate that all paths are valid.- Parameters:
graph
- graphsource
- source vertexsink
- sink vertexheapSupplier
- supplier of the preferable heap implementationpathValidator
- validator for computed paths
-
-
Method Details
-
lazyInitializePathHeap
private void lazyInitializePathHeap()Lazily initializes the path heap by computing the shortest path between thesource
and thesink
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 eitherhasNext()
ornext()
. -
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
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 pathfirstDeviation
- vertex at whichpath
deviates from its parent path- Returns:
- vertex which is last valid deviation for
path
-
hasNext
public boolean hasNext() -
next
-
addDeviations
Builds unique loopless deviations from the given path in thegraph
. 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 theMaskSubgraph
and builds a reversed shortest paths tree starting atsink
in it. Finally builds new candidate paths by deviating from the vertices of the providedpath
. Puts only those candidates in thecandidatesList
, which deviate frompath
between $firstDeviation$ and $lastDeviation$. $firstDeviation$ and $lastDeviation$ are obtainer fromfirstDeviations
andlastDeviations
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 givenpath
builds sets of vertices and edges to be masked. First masks all edges and vertices of the providedpath
except for thesink
. Then for each path in theresultList
that coincides in thepath
until thepathDeviation
masks the edge between thepathDeviation
and its successor in this path.- Parameters:
path
- path to mask vertices and edges ofpathDeviation
- deviation vertex of the pathpathDeviationIndex
- 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 thepath
until therecoverVertexIndex
. Then adds vertices and edges of thespurPath
.- Parameters:
path
- path the candidate path deviates fromrecoverVertexIndex
- vertex that is being recoveredspurPath
- spur path of the candidate- Returns:
- candidate path
-
equalLists
Checks if the lists have the same content until theindex
(inclusive).- Parameters:
first
- first listsecond
- second listindex
- position in the lists- Returns:
- true iff the contents of the list are equal until the index
-