- java.lang.Object
-
- org.jgrapht.alg.shortestpath.YenShortestPathIterator<V,E>
-
- Type Parameters:
V
- the graph vertex typeE
- 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 thesink
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 thesink
, which is put into the candidates heap. Thesource
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 incandidatePaths
.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 thenext()
method.private boolean
shortestPathComputed
Indicates if thelazyInitializePathHeap
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 givengraph
,source
andsink
.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 givengraph
,source
,sink
andheapSupplier
.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 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
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 thegraph
.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 theindex
(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 givenpath
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 thesource
and thesink
and building a necessary amount of paths until at least one valid path is found.GraphPath<V,E>
next()
-
-
-
Field Detail
-
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 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
private java.util.List<GraphPath<V,E>> resultList
List of the paths returned so far via thenext()
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 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
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 thesink
), 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$. Storesnull
, if there is no such vertex.
-
numberOfValidPathInQueue
private int numberOfValidPathInQueue
Stores number of valid candidates incandidatePaths
.
-
shortestPathComputed
private boolean shortestPathComputed
Indicates if thelazyInitializePathHeap
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 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, 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 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, 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 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 Detail
-
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
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 pathfirstDeviation
- vertex at whichpath
deviates from its parent path- Returns:
- vertex which is last valid deviation for
path
-
hasNext
public boolean hasNext()
- Specified by:
hasNext
in interfacejava.util.Iterator<V>
-
addDeviations
private int addDeviations(GraphPath<V,E> path)
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<java.util.Set<V>,java.util.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
private boolean equalLists(java.util.List<V> first, java.util.List<V> second, int index)
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
-
-