Package org.jgrapht.alg

Class KShortestPathsIterator<V,E>

java.lang.Object

org.jgrapht.alg.KShortestPathsIterator<V,E>

All Implemented Interfaces:

java.util.Iterator<java.util.Set<V>>

@Deprecated
class KShortestPathsIterator<V,E>
extends java.lang.Object
implements java.util.Iterator<java.util.Set<V>>

Deprecated.

Moved in shortest path package

Helper class for KShortestPaths.

Since:

July 5, 2007

Field Summary

Fields

Modifier and Type	Field	Description
private V	endVertex	Deprecated. End vertex.
private Graph<V,E>	graph	Deprecated. Graph on which shortest paths are searched.
private int	k	Deprecated. Number of paths stored at each end vertex.
private int	passNumber	Deprecated. Stores the number of the path.
private PathValidator<V,E>	pathValidator	Deprecated. Performs path validations in addition to the basics (source and target are connected w/o loops)
private java.util.Set<V>	prevImprovedVertices	Deprecated. Vertices whose ranking shortest paths have been modified during the previous pass.
private java.util.Map<V,RankingPathElementList<V,E>>	prevSeenDataContainer	Deprecated. Stores the paths that improved the vertex in the previous pass.
private java.util.Map<V,RankingPathElementList<V,E>>	seenDataContainer	Deprecated. Stores the vertices that have been seen during iteration and (optionally) some additional traversal info regarding each vertex.
private V	startVertex	Deprecated. Start vertex.
private boolean	startVertexEncountered	Deprecated.

Constructor Summary

Constructors

Constructor	Description
KShortestPathsIterator(Graph<V,E> graph, V startVertex, V endVertex, int maxSize)	Deprecated.
KShortestPathsIterator(Graph<V,E> graph, V startVertex, V endVertex, int maxSize, PathValidator<V,E> pathValidator)	Deprecated.

Method Summary

Modifier and Type	Method	Description
private void	assertKShortestPathsIterator(Graph<V,E> graph, V startVertex)	Deprecated.
private RankingPathElementList<V,E>	createSeenData(V vertex, E edge)	Deprecated. The first time we see a vertex, make up a new entry for it.
private java.util.Iterator<E>	edgesOfIterator(V vertex)	Deprecated. Returns an iterator to loop over outgoing edges Edge of the vertex.
private void	encounterStartVertex()	Deprecated. Initializes the list of paths at the start vertex and adds an empty path.
(package private) RankingPathElementList<V,E>	getPathElements(V endVertex)	Deprecated. Returns the path elements of the ranking shortest paths with less than nMaxHops edges between the start vertex and the end vertex.
boolean	hasNext()	Deprecated.
java.util.Set<V>	next()	Deprecated. Returns the list of vertices whose path has been improved during the current pass.
void	remove()	Deprecated. Unsupported.
private void	savePassData(java.util.Set<V> improvedVertices)	Deprecated.
private boolean	tryToAddFirstPaths(V vertex, E edge)	Deprecated. Try to add the first paths to the specified vertex.
private boolean	tryToAddNewPaths(V vertex, E edge)	Deprecated. Try to add new paths for the vertex.
private void	updateOutgoingVertices(V vertex, java.util.Set<V> improvedVertices)	Deprecated. Updates outgoing vertices of the vertex.

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

Field Detail

endVertex

private V endVertex

Deprecated.

End vertex.

graph

private Graph<V,E> graph

Deprecated.

Graph on which shortest paths are searched.

k

private int k

Deprecated.

Number of paths stored at each end vertex.

prevImprovedVertices

private java.util.Set<V> prevImprovedVertices

Deprecated.

Vertices whose ranking shortest paths have been modified during the previous pass.

prevSeenDataContainer

private java.util.Map<V,RankingPathElementList<V,E>> prevSeenDataContainer

Deprecated.

Stores the paths that improved the vertex in the previous pass.

seenDataContainer

private java.util.Map<V,RankingPathElementList<V,E>> seenDataContainer

Deprecated.

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

Deprecated.

Performs path validations in addition to the basics (source and target are connected w/o loops)

startVertex

private V startVertex

Deprecated.

Start vertex.

startVertexEncountered

private boolean startVertexEncountered

Deprecated.

passNumber

private int passNumber

Deprecated.

Stores the number of the path.

Constructor Detail

KShortestPathsIterator

public KShortestPathsIterator(Graph<V,E> graph,
                              V startVertex,
                              V endVertex,
                              int maxSize)

Deprecated.

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)

Deprecated.

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()

Deprecated.

Specified by:

hasNext in interface java.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()

Deprecated.

Returns the list of vertices whose path has been improved during the current pass. Complexity =

• O(m*k*(m+n)) where k is the maximum number of shortest paths to compute, m is the number of edges of the graph and n is the number of vertices of the graph

Specified by:

next in interface java.util.Iterator<V>

See Also:

Iterator.next()

remove

public void remove()

Deprecated.

Unsupported.

Specified by:

remove in interface java.util.Iterator<V>

See Also:

Iterator.remove()

getPathElements

RankingPathElementList<V,E> getPathElements(V endVertex)

Deprecated.

Returns the path elements of the ranking shortest paths with less than nMaxHops edges between the start vertex and the end vertex.

Parameters:

endVertex - end vertex.

Returns:

list of RankingPathElement, or null of no path exists between the start vertex and the end vertex.

assertKShortestPathsIterator

private void assertKShortestPathsIterator(Graph<V,E> graph,
                                          V startVertex)

Deprecated.

createSeenData

private RankingPathElementList<V,E> createSeenData(V vertex,
                                                         E edge)

Deprecated.

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)

Deprecated.

Returns an iterator to loop over outgoing edges Edge of the vertex.

Parameters:

vertex -

Returns:

.

encounterStartVertex

private void encounterStartVertex()

Deprecated.

Initializes the list of paths at the start vertex and adds an empty path.

savePassData

private void savePassData(java.util.Set<V> improvedVertices)

Deprecated.

tryToAddFirstPaths

private boolean tryToAddFirstPaths(V vertex,
                                   E edge)

Deprecated.

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)

Deprecated.

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)

Deprecated.

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)) where d(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 and n is the number of vertices of the graph

Parameters:

vertex -

improvedVertices -