 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 failfast. 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
.
 Author:
 Semen Chudakov
 See Also:

Constructor Summary
ConstructorDescriptionConstructs 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
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

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