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

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

All Implemented Interfaces:

Distance

public class UnweightedShortestPath

extends ShortestPath

implements 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

java.lang.Number	getDistance(Vertex source, Vertex target) Returns the distance from the source vertex to the target vertex.
java.util.Map	getDistanceMap(Vertex source) Returns a Map which maps each vertex in the graph (including the source vertex) to its distance (represented as a Number) from source.
java.util.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

Methods inherited from class edu.uci.ics.jung.algorithms.shortestpath.ShortestPath

getPath

Methods inherited from class java.lang.Object

equals, 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 java.lang.Number getDistance(Vertex source,
                                    Vertex 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.Vertex, edu.uci.ics.jung.graph.Vertex)

getDistanceMap

public java.util.Map getDistanceMap(Vertex 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.Vertex)

getIncomingEdgeMap

public java.util.Map getIncomingEdgeMap(Vertex source)

Description copied from class: 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 class 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)