- 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
.- Author:
- Semen Chudakov
- See Also:
PathValidator
-
-
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 boolean
hasNext()
GraphPath<V,E>
next()
-
-
-
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
-
-