edu.uci.ics.jung.algorithms.shortestpath
Class UnweightedShortestPath

java.lang.Object
  edu.uci.ics.jung.algorithms.shortestpath.UnweightedShortestPath

All Implemented Interfaces:

Distance, ShortestPath

public class UnweightedShortestPath
extends Object
implements ShortestPath, Distance

Computes the shortest path distances for graphs whose edges are not weighted (using BFS).

Author:

Scott White

Constructor Summary

UnweightedShortestPath(Graph g)
Constructs and initializes algorithm

Method Summary

Number	getDistance(ArchetypeVertex source, ArchetypeVertex target) Returns the distance from the source vertex to the target vertex.
Map	getDistanceMap(ArchetypeVertex source) Returns a Map which maps each vertex in the graph (including the source vertex) to its distance (represented as a Number) from source.
Map	getIncomingEdgeMap(Vertex source) Returns a LinkedHashMap which maps each vertex in the graph (including the source vertex) to the last edge on the shortest path from the source vertex.
int	getShortestPath(Vertex source, Vertex target) Deprecated. use getDistance
void	reset() Clears all stored distances for this instance.
void	reset(Vertex v) Clears all stored distances for the specified source vertex source.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

UnweightedShortestPath

public UnweightedShortestPath(Graph g)

Constructs and initializes algorithm

Parameters:

g - the graph

Method Detail

getDistance

public Number getDistance(ArchetypeVertex source,
                          ArchetypeVertex target)

Description copied from interface: Distance

Returns the distance from the source vertex to the target vertex. If target is not reachable from source, returns null.

Specified by:

getDistance in interface Distance

See Also:

Distance.getDistance(edu.uci.ics.jung.graph.ArchetypeVertex, edu.uci.ics.jung.graph.ArchetypeVertex)

getDistanceMap

public Map getDistanceMap(ArchetypeVertex source)

Description copied from interface: Distance

Returns a Map which maps each vertex in the graph (including the source vertex) to its distance (represented as a Number) from source. If any vertex is not reachable from source, no distance is stored for that vertex.

Specified by:

getDistanceMap in interface Distance

See Also:

Distance.getDistanceMap(edu.uci.ics.jung.graph.ArchetypeVertex)

getIncomingEdgeMap

public Map getIncomingEdgeMap(Vertex source)

Description copied from interface: ShortestPath

Returns a LinkedHashMap which maps each vertex in the graph (including the source vertex) to the last edge on the shortest path from the source vertex.

Specified by:

getIncomingEdgeMap in interface ShortestPath

See Also:

ShortestPath.getIncomingEdgeMap(edu.uci.ics.jung.graph.Vertex)

getShortestPath

public int getShortestPath(Vertex source,
                           Vertex target)

Deprecated. use getDistance

Computes the shortest path distance from the source to target. If the shortest path distance has not already been computed, then all pairs shortest paths will be computed.

Parameters:

source - the source node

target - the target node

Returns:

the shortest path value (if the target is unreachable, NPE is thrown)

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(Vertex) may be appropriate instead.

See Also:

reset(Vertex)

reset

public void reset(Vertex v)

Clears all stored distances for the specified source vertex source. Should be called whenever the stored distances from this vertex are invalidated by changes to the graph.

See Also:

reset()