Module org.jgrapht.core

Package org.jgrapht.alg.shortestpath

Class YenShortestPathIterator<V,E>

java.lang.Object

org.jgrapht.alg.shortestpath.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

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