Package org.jgrapht.alg.shortestpath
Class KShortestPathsIterator<V,E>
- java.lang.Object
-
- org.jgrapht.alg.shortestpath.KShortestPathsIterator<V,E>
-
- All Implemented Interfaces:
java.util.Iterator<java.util.Set<V>>
class KShortestPathsIterator<V,E> extends java.lang.Object implements java.util.Iterator<java.util.Set<V>>
Helper class forKShortestPaths
.- Since:
- July 5, 2007
-
-
Field Summary
Fields Modifier and Type Field Description private V
endVertex
End vertex.private Graph<V,E>
graph
Graph on which shortest paths are searched.private int
k
Number of paths stored at each end vertex.private int
passNumber
Stores the number of the path.private PathValidator<V,E>
pathValidator
Performs path validations in addition to the basics (source and target are connected w/o loops)private java.util.Set<V>
prevImprovedVertices
Vertices whose ranking shortest paths have been modified during the previous pass.private java.util.Map<V,RankingPathElementList<V,E>>
prevSeenDataContainer
Stores the paths that improved the vertex in the previous pass.private java.util.Map<V,RankingPathElementList<V,E>>
seenDataContainer
Stores the vertices that have been seen during iteration and (optionally) some additional traversal info regarding each vertex.private V
startVertex
Start vertex.private boolean
startVertexEncountered
-
Constructor Summary
Constructors Constructor Description KShortestPathsIterator(Graph<V,E> graph, V startVertex, V endVertex, int maxSize)
KShortestPathsIterator(Graph<V,E> graph, V startVertex, V endVertex, int maxSize, PathValidator<V,E> pathValidator)
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description private void
assertKShortestPathsIterator(Graph<V,E> graph, V startVertex)
private RankingPathElementList<V,E>
createSeenData(V vertex, E edge)
The first time we see a vertex, make up a new entry for it.private java.util.Iterator<E>
edgesOfIterator(V vertex)
Returns an iterator to loop over outgoing edgesEdge
of the vertex.private void
encounterStartVertex()
Initializes the list of paths at the start vertex and adds an empty path.(package private) RankingPathElementList<V,E>
getPathElements(V endVertex)
Returns the path elements of the ranking shortest paths with less thannMaxHops
edges between the start vertex and the end vertex.boolean
hasNext()
java.util.Set<V>
next()
Returns the list of vertices whose path has been improved during the current pass.void
remove()
Unsupported.private void
savePassData(java.util.Set<V> improvedVertices)
private boolean
tryToAddFirstPaths(V vertex, E edge)
Try to add the first paths to the specified vertex.private boolean
tryToAddNewPaths(V vertex, E edge)
Try to add new paths for the vertex.private void
updateOutgoingVertices(V vertex, java.util.Set<V> improvedVertices)
Updates outgoing vertices of the vertex.
-
-
-
Field Detail
-
endVertex
private V endVertex
End vertex.
-
k
private int k
Number of paths stored at each end vertex.
-
prevImprovedVertices
private java.util.Set<V> prevImprovedVertices
Vertices whose ranking shortest paths have been modified during the previous pass.
-
prevSeenDataContainer
private java.util.Map<V,RankingPathElementList<V,E>> prevSeenDataContainer
Stores the paths that improved the vertex in the previous pass.
-
seenDataContainer
private java.util.Map<V,RankingPathElementList<V,E>> seenDataContainer
Stores the vertices that have been seen during iteration and (optionally) some additional traversal info regarding each vertex. Key = vertex, value =RankingPathElementList
list of calculated paths.
-
pathValidator
private PathValidator<V,E> pathValidator
Performs path validations in addition to the basics (source and target are connected w/o loops)
-
startVertex
private V startVertex
Start vertex.
-
startVertexEncountered
private boolean startVertexEncountered
-
passNumber
private int passNumber
Stores the number of the path.
-
-
Constructor Detail
-
KShortestPathsIterator
public KShortestPathsIterator(Graph<V,E> graph, V startVertex, V endVertex, int maxSize)
- Parameters:
graph
- graph on which shortest paths are searched.startVertex
- start vertex of the calculated paths.endVertex
- end vertex of the calculated paths.maxSize
- number of paths stored at end vertex of the graph.
-
KShortestPathsIterator
public KShortestPathsIterator(Graph<V,E> graph, V startVertex, V endVertex, int maxSize, PathValidator<V,E> pathValidator)
- Parameters:
graph
- graph on which shortest paths are searched.startVertex
- start vertex of the calculated paths.endVertex
- end vertex of the calculated paths.maxSize
- number of paths stored at end vertex of the graph.pathValidator
- the path validator to use
-
-
Method Detail
-
hasNext
public boolean hasNext()
- Specified by:
hasNext
in interfacejava.util.Iterator<V>
- Returns:
true
if at least one path has been improved during the previous pass,false
otherwise.
-
next
public java.util.Set<V> next()
Returns the list of vertices whose path has been improved during the current pass. Complexity =- O(
m*k*(m+n)
) wherek
is the maximum number of shortest paths to compute,m
is the number of edges of the graph andn
is the number of vertices of the graph
- Specified by:
next
in interfacejava.util.Iterator<V>
- See Also:
Iterator.next()
- O(
-
remove
public void remove()
Unsupported.- Specified by:
remove
in interfacejava.util.Iterator<V>
- See Also:
Iterator.remove()
-
getPathElements
RankingPathElementList<V,E> getPathElements(V endVertex)
Returns the path elements of the ranking shortest paths with less thannMaxHops
edges between the start vertex and the end vertex.- Parameters:
endVertex
- end vertex.- Returns:
- list of
RankingPathElement
, ornull
of no path exists between the start vertex and the end vertex.
-
assertKShortestPathsIterator
private void assertKShortestPathsIterator(Graph<V,E> graph, V startVertex)
-
createSeenData
private RankingPathElementList<V,E> createSeenData(V vertex, E edge)
The first time we see a vertex, make up a new entry for it.- Parameters:
vertex
- a vertex which has just been encountered.edge
- the edge via which the vertex was encountered.- Returns:
- the new entry.
-
edgesOfIterator
private java.util.Iterator<E> edgesOfIterator(V vertex)
Returns an iterator to loop over outgoing edgesEdge
of the vertex.- Parameters:
vertex
-- Returns:
- .
-
encounterStartVertex
private void encounterStartVertex()
Initializes the list of paths at the start vertex and adds an empty path.
-
savePassData
private void savePassData(java.util.Set<V> improvedVertices)
-
tryToAddFirstPaths
private boolean tryToAddFirstPaths(V vertex, E edge)
Try to add the first paths to the specified vertex. These paths reached the specified vertex and ended with the specified edge. A new intermediary path is stored in the paths list of the specified vertex provided that the path can be extended to the end-vertex.- Parameters:
vertex
- vertex reached by a path.edge
- edge reaching the vertex.
-
tryToAddNewPaths
private boolean tryToAddNewPaths(V vertex, E edge)
Try to add new paths for the vertex. These new paths reached the specified vertex and ended with the specified edge. A new intermediary path is stored in the paths list of the specified vertex provided that the path can be extended to the end-vertex.- Parameters:
vertex
- a vertex which has just been encountered.edge
- the edge via which the vertex was encountered.
-
updateOutgoingVertices
private void updateOutgoingVertices(V vertex, java.util.Set<V> improvedVertices)
Updates outgoing vertices of the vertex. For each outgoing vertex, the new paths are obtained by concatenating the specified edge to the calculated paths of the specified vertex. If the weight of a new path is greater than the weight of any path stored so far at the outgoing vertex then the path is not added, otherwise it is added to the list of paths in increasing order of weight.
Complexity =- O(
d(v)*k*(m+n)
) whered(v)
is the outgoing degree of the specified vertex,k
is the maximum number of shortest paths to compute,m
is the number of edges of the graph andn
is the number of vertices of the graph
- Parameters:
vertex
-improvedVertices
-
- O(
-
-