Class UnweightedShortestPath<V,E>
- java.lang.Object
-
- edu.uci.ics.jung.algorithms.shortestpath.UnweightedShortestPath<V,E>
-
- All Implemented Interfaces:
Distance<V>
,ShortestPath<V,E>
public class UnweightedShortestPath<V,E> extends java.lang.Object implements ShortestPath<V,E>, Distance<V>
Computes the shortest path distances for graphs whose edges are not weighted (using BFS).
-
-
Field Summary
Fields Modifier and Type Field Description private java.util.Map<V,java.lang.Number>
distances
private java.util.Map<V,java.util.Map<V,java.lang.Number>>
mDistanceMap
private Hypergraph<V,E>
mGraph
private java.util.Map<V,java.util.Map<V,E>>
mIncomingEdgeMap
-
Constructor Summary
Constructors Constructor Description UnweightedShortestPath(Hypergraph<V,E> g)
Constructs and initializes algorithm
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description private void
computeShortestPathsFromSource(V source)
Computes the shortest path distances from a given node to all other nodes.java.lang.Number
getDistance(V source, V target)
Returns the distance from thesource
vertex to thetarget
vertex.java.util.Map<V,java.lang.Number>
getDistanceMap(V source)
Returns aMap
which maps each vertex in the graph (including thesource
vertex) to its distance (represented as a Number) fromsource
.java.util.Map<V,E>
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
reset(V v)
Clears all stored distances for the specified source vertexsource
.
-
-
-
Constructor Detail
-
UnweightedShortestPath
public UnweightedShortestPath(Hypergraph<V,E> g)
Constructs and initializes algorithm- Parameters:
g
- the graph
-
-
Method Detail
-
getDistance
public java.lang.Number getDistance(V source, V target)
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:
Distance.getDistance(Object, Object)
-
getDistanceMap
public java.util.Map<V,java.lang.Number> getDistanceMap(V source)
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:
Distance.getDistanceMap(Object)
-
getIncomingEdgeMap
public java.util.Map<V,E> getIncomingEdgeMap(V source)
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:
ShortestPath.getIncomingEdgeMap(Object)
-
computeShortestPathsFromSource
private void computeShortestPathsFromSource(V source)
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(Object)
-
-