Class UnweightedShortestPath<V,E>
java.lang.Object
edu.uci.ics.jung.algorithms.shortestpath.UnweightedShortestPath<V,E>
- All Implemented Interfaces:
Distance<V>
,ShortestPath<V,
E>
Computes the shortest path distances for graphs whose edges are not weighted (using BFS).
-
Field Summary
Fields -
Constructor Summary
ConstructorsConstructorDescriptionConstructs and initializes algorithm -
Method Summary
Modifier and TypeMethodDescriptionprivate void
computeShortestPathsFromSource
(V source) Computes the shortest path distances from a given node to all other nodes.getDistance
(V source, V target) Returns the distance from thesource
vertex to thetarget
vertex.getDistanceMap
(V source) Returns aMap
which maps each vertex in the graph (including thesource
vertex) to its distance (represented as a Number) fromsource
.getIncomingEdgeMap
(V source) Returns a map from vertices to the last edge on the shortest path to that vertex starting fromsource
.void
reset()
Clears all stored distances for this instance.void
Clears all stored distances for the specified source vertexsource
.
-
Field Details
-
mDistanceMap
-
mIncomingEdgeMap
-
mGraph
-
distances
-
-
Constructor Details
-
UnweightedShortestPath
Constructs and initializes algorithm- Parameters:
g
- the graph
-
-
Method Details
-
getDistance
Description copied from interface:Distance
Returns the distance from thesource
vertex to thetarget
vertex. Iftarget
is not reachable fromsource
, returns null.- Specified by:
getDistance
in interfaceDistance<V>
- Parameters:
source
- the vertex from which distance is to be measuredtarget
- the vertex to which distance is to be measured- Returns:
- the distance from
source
totarget
- See Also:
-
getDistanceMap
Description copied from interface:Distance
Returns aMap
which maps each vertex in the graph (including thesource
vertex) to its distance (represented as a Number) fromsource
. If any vertex is not reachable fromsource
, no distance is stored for that vertex.- Specified by:
getDistanceMap
in interfaceDistance<V>
- Parameters:
source
- the vertex from which distances are to be measured- Returns:
- a
Map
of the distances fromsource
to other vertices in the graph - See Also:
-
getIncomingEdgeMap
Description copied from interface:ShortestPath
Returns a map from vertices to the last edge on the shortest path to that vertex starting fromsource
.- Specified by:
getIncomingEdgeMap
in interfaceShortestPath<V,
E> - Parameters:
source
- the starting point for the shortest paths- Returns:
- a map from vertices to the last edge on the shortest path to that vertex
starting from
source
- See Also:
-
computeShortestPathsFromSource
Computes the shortest path distances from a given node to all other nodes.- Parameters:
source
- the source node
-
reset
public void reset()Clears all stored distances for this instance. Should be called whenever the graph is modified (edge weights changed or edges added/removed). If the user knows that some currently calculated distances are unaffected by a change,reset(V)
may be appropriate instead.- See Also:
-
reset
Clears all stored distances for the specified source vertexsource
. Should be called whenever the stored distances from this vertex are invalidated by changes to the graph.- Parameters:
v
- the vertex for which distances should be cleared- See Also:
-