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 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 Map<V,Number>	distances
private Map<V, Map<V,Number>>	mDistanceMap
private Hypergraph<V,E>	mGraph
private Map<V,Map<V,E>>	mIncomingEdgeMap

Constructor Summary

Constructors

Constructor	Description
UnweightedShortestPath(Hypergraph<V,E> g)	Constructs and initializes algorithm

Method Summary

Modifier and Type	Method	Description
private void	computeShortestPathsFromSource(V source)	Computes the shortest path distances from a given node to all other nodes.
Number	getDistance(V source, V target)	Returns the distance from the source vertex to the target vertex.
Map<V,Number>	getDistanceMap(V 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<V,E>	getIncomingEdgeMap(V source)	Returns a map from vertices to the last edge on the shortest path to that vertex starting from source.
void	reset()	Clears all stored distances for this instance.
void	reset(V v)	Clears all stored distances for the specified source vertex source.

Methods inherited from class Object

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

Field Details

mDistanceMap

private Map<V, Map<V,Number>> mDistanceMap

mIncomingEdgeMap

private Map<V,Map<V,E>> mIncomingEdgeMap

mGraph

private Hypergraph<V,E> mGraph

distances

private Map<V,Number> distances

Constructor Details

UnweightedShortestPath

public UnweightedShortestPath(Hypergraph<V,E> g)

Constructs and initializes algorithm

Parameters:

g - the graph

Method Details

getDistance

public Number getDistance(V source,
 V 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<V>

Parameters:

source - the vertex from which distance is to be measured

target - the vertex to which distance is to be measured

Returns:

the distance from source to target

See Also:

• Distance.getDistance(Object, Object)

getDistanceMap

public Map<V,Number> getDistanceMap(V 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<V>

Parameters:

source - the vertex from which distances are to be measured

Returns:

a Map of the distances from source to other vertices in the graph

See Also:

• Distance.getDistanceMap(Object)

getIncomingEdgeMap

public 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 from source.

Specified by:

getIncomingEdgeMap in interface ShortestPath<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)

reset

public void reset(V 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.

Parameters:

v - the vertex for which distances should be cleared

See Also:

• reset()