Package org.jgrapht.alg
Class BellmanFordIterator<V,E>
- java.lang.Object
-
- org.jgrapht.alg.BellmanFordIterator<V,E>
-
- All Implemented Interfaces:
java.util.Iterator<java.util.List<V>>
@Deprecated class BellmanFordIterator<V,E> extends java.lang.Object implements java.util.Iterator<java.util.List<V>>
Deprecated.moved into shortest path packageHelper class forBellmanFordShortestPath
; not intended for general use.
-
-
Field Summary
Fields Modifier and Type Field Description private double
epsilon
Deprecated.protected Graph<V,E>
graph
Deprecated.Graph on which shortest paths are searched.protected static java.lang.String
NEGATIVE_UNDIRECTED_EDGE
Deprecated.Error message.private java.util.List<V>
prevImprovedVertices
Deprecated.Vertices whose shortest path cost have been improved during the previous pass.private java.util.Map<V,BellmanFordPathElement<V,E>>
prevVertexData
Deprecated.protected V
startVertex
Deprecated.Start vertex.private boolean
startVertexEncountered
Deprecated.private java.util.Map<V,BellmanFordPathElement<V,E>>
vertexData
Deprecated.Stores the vertices that have been seen during iteration and (optionally) some additional traversal info regarding each vertex.
-
Constructor Summary
Constructors Modifier Constructor Description protected
BellmanFordIterator(Graph<V,E> graph, V startVertex, double epsilon)
Deprecated.
-
Method Summary
All Methods Instance Methods Concrete Methods Deprecated Methods Modifier and Type Method Description private void
assertBellmanFordIterator(Graph<V,E> graph, V startVertex)
Deprecated.protected void
assertValidEdge(E edge)
Deprecated.protected double
calculatePathCost(V vertex, E edge)
Deprecated.Costs taken into account are the weights stored inEdge
objects.private BellmanFordPathElement<V,E>
createSeenData(V vertex, E edge, double cost)
Deprecated.The first time we see a vertex, make up a new entry for it.protected java.util.Iterator<E>
edgesOfIterator(V vertex)
Deprecated.Returns an iterator to loop over outgoing edgesEdge
of the vertex.private void
encounterStartVertex()
Deprecated.BellmanFordPathElement<V,E>
getPathElement(V endVertex)
Deprecated.Returns the path element of the shortest path with less thannMaxHops
edges between the start vertex and the end vertex.protected BellmanFordPathElement<V,E>
getPrevSeenData(V vertex)
Deprecated.Access the data stored for a seen vertex in the previous pass.protected BellmanFordPathElement<V,E>
getSeenData(V vertex)
Deprecated.Access the data stored for a seen vertex in the current pass.boolean
hasNext()
Deprecated.protected boolean
isSeenVertex(V vertex)
Deprecated.Determines whether a vertex has been seen yet by this traversal.java.util.List<V>
next()
Deprecated.Returns the listCollection
of vertices whose path has been improved during the current pass.protected BellmanFordPathElement<V,E>
putPrevSeenData(V vertex, BellmanFordPathElement<V,E> data)
Deprecated.protected BellmanFordPathElement<V,E>
putSeenData(V vertex, BellmanFordPathElement<V,E> data)
Deprecated.Stores iterator-dependent data for a vertex that has been seen during the current pass.private void
relaxVertex(V vertex, E edge)
Deprecated.Upates data first time a vertex is reached by a path.private boolean
relaxVertexAgain(V vertex, E edge)
Deprecated.Check if the cost of the best path so far reaching the specified vertex could be improved if the vertex is reached through the specified edge.void
remove()
Deprecated.Unsupportedprivate void
savePassData(java.util.List<V> improvedVertices)
Deprecated.
-
-
-
Field Detail
-
NEGATIVE_UNDIRECTED_EDGE
protected static final java.lang.String NEGATIVE_UNDIRECTED_EDGE
Deprecated.Error message.- See Also:
- Constant Field Values
-
startVertex
protected V startVertex
Deprecated.Start vertex.
-
prevImprovedVertices
private java.util.List<V> prevImprovedVertices
Deprecated.Vertices whose shortest path cost have been improved during the previous pass.
-
prevVertexData
private java.util.Map<V,BellmanFordPathElement<V,E>> prevVertexData
Deprecated.
-
startVertexEncountered
private boolean startVertexEncountered
Deprecated.
-
vertexData
private java.util.Map<V,BellmanFordPathElement<V,E>> vertexData
Deprecated.Stores the vertices that have been seen during iteration and (optionally) some additional traversal info regarding each vertex.
-
epsilon
private double epsilon
Deprecated.
-
-
Method Detail
-
getPathElement
public BellmanFordPathElement<V,E> getPathElement(V endVertex)
Deprecated.Returns the path element of the shortest path with less thannMaxHops
edges between the start vertex and the end vertex.- Parameters:
endVertex
- end vertex.- Returns:
- .
-
hasNext
public boolean hasNext()
Deprecated.- 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.List<V> next()
Deprecated.Returns the listCollection
of vertices whose path has been improved during the current pass.- Specified by:
next
in interfacejava.util.Iterator<V>
- See Also:
Iterator.next()
-
remove
public void remove()
Deprecated.Unsupported- Specified by:
remove
in interfacejava.util.Iterator<V>
- See Also:
Iterator.remove()
-
assertValidEdge
protected void assertValidEdge(E edge)
Deprecated.- Parameters:
edge
-- Throws:
java.lang.IllegalArgumentException
- if the graph is undirected and the edge-weight is negative.
-
calculatePathCost
protected double calculatePathCost(V vertex, E edge)
Deprecated.Costs taken into account are the weights stored inEdge
objects.- Parameters:
vertex
- a vertex which has just been encountered.edge
- the edge via which the vertex was encountered.- Returns:
- the cost obtained by concatenation.
- See Also:
Graph#getEdgeWeight(E)
-
edgesOfIterator
protected java.util.Iterator<E> edgesOfIterator(V vertex)
Deprecated.Returns an iterator to loop over outgoing edgesEdge
of the vertex.- Parameters:
vertex
-- Returns:
- .
-
getPrevSeenData
protected BellmanFordPathElement<V,E> getPrevSeenData(V vertex)
Deprecated.Access the data stored for a seen vertex in the previous pass.- Parameters:
vertex
- a vertex which has already been seen.- Returns:
- data associated with the seen vertex or
null
if no data was associated with the vertex.
-
getSeenData
protected BellmanFordPathElement<V,E> getSeenData(V vertex)
Deprecated.Access the data stored for a seen vertex in the current pass.- Parameters:
vertex
- a vertex which has already been seen.- Returns:
- data associated with the seen vertex or
null
if no data was associated with the vertex.
-
isSeenVertex
protected boolean isSeenVertex(V vertex)
Deprecated.Determines whether a vertex has been seen yet by this traversal.- Parameters:
vertex
- vertex in question.- Returns:
- true if vertex has already been seen.
-
putPrevSeenData
protected BellmanFordPathElement<V,E> putPrevSeenData(V vertex, BellmanFordPathElement<V,E> data)
Deprecated.- Parameters:
vertex
-data
-- Returns:
- .
-
putSeenData
protected BellmanFordPathElement<V,E> putSeenData(V vertex, BellmanFordPathElement<V,E> data)
Deprecated.Stores iterator-dependent data for a vertex that has been seen during the current pass.- Parameters:
vertex
- a vertex which has been seen.data
- data to be associated with the seen vertex.- Returns:
- previous value associated with specified vertex or
null
if no data was associated with the vertex.
-
assertBellmanFordIterator
private void assertBellmanFordIterator(Graph<V,E> graph, V startVertex)
Deprecated.
-
createSeenData
private BellmanFordPathElement<V,E> createSeenData(V vertex, E edge, double cost)
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.cost
- cost of the created path element.- Returns:
- the new entry.
-
encounterStartVertex
private void encounterStartVertex()
Deprecated.
-
relaxVertex
private void relaxVertex(V vertex, E edge)
Deprecated.Upates data first time a vertex is reached by a path.- Parameters:
vertex
- a vertex which has just been encountered.edge
- the edge via which the vertex was encountered.
-
relaxVertexAgain
private boolean relaxVertexAgain(V vertex, E edge)
Deprecated.Check if the cost of the best path so far reaching the specified vertex could be improved if the vertex is reached through the specified edge.- Parameters:
vertex
- a vertex which has just been encountered.edge
- the edge via which the vertex was encountered.- Returns:
true
if the cost has been improved,false
otherwise.
-
savePassData
private void savePassData(java.util.List<V> improvedVertices)
Deprecated.
-
-