edu.uci.ics.jung.algorithms.shortestpath

Class BFSDistanceLabeler<V,E>

java.lang.Object

edu.uci.ics.jung.algorithms.shortestpath.BFSDistanceLabeler<V,E>

public class BFSDistanceLabeler<V,E>
extends java.lang.Object

Labels each node in the graph according to the BFS distance from the start node(s). If nodes are unreachable, then they are assigned a distance of -1. All nodes traversed at step k are marked as predecessors of their successors traversed at step k+1.

Running time is: O(m)

Constructor Summary

Constructors

Constructor and Description
BFSDistanceLabeler() Creates a new BFS labeler for the specified graph and root set The distances are stored in the corresponding Vertex objects and are of type MutableInteger

Method Summary

Modifier and Type	Method and Description
int	getDistance(Hypergraph<V,E> g, V v) Given a vertex, returns the shortest distance from any node in the root set to v
java.util.Map<V,java.lang.Number>	getDistanceDecorator() Must be called after labelDistances in order to contain valid data.
java.util.Set<V>	getPredecessors(V v) Returns set of predecessors of the given vertex
java.util.Set<V>	getUnvisitedVertices() Returns the set of all vertices that were not visited
java.util.List<V>	getVerticesInOrderVisited() Returns the list of vertices visited in order of traversal
void	labelDistances(Hypergraph<V,E> graph, java.util.Set<V> rootSet) Computes the distances of all the node from the starting root nodes.
void	labelDistances(Hypergraph<V,E> graph, V root) Computes the distances of all the node from the specified root node.

Methods inherited from class java.lang.Object

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

Constructor Detail

BFSDistanceLabeler

public BFSDistanceLabeler()

Creates a new BFS labeler for the specified graph and root set The distances are stored in the corresponding Vertex objects and are of type MutableInteger

Method Detail

getVerticesInOrderVisited

public java.util.List<V> getVerticesInOrderVisited()

Returns the list of vertices visited in order of traversal

Returns:

the list of vertices

getUnvisitedVertices

public java.util.Set<V> getUnvisitedVertices()

Returns the set of all vertices that were not visited

Returns:

the list of unvisited vertices

getDistance

public int getDistance(Hypergraph<V,E> g,
                       V v)

Given a vertex, returns the shortest distance from any node in the root set to v

Parameters:

g - the graph in which the distances are to be measured

v - the vertex whose distance is to be retrieved

Returns:

the shortest distance from any node in the root set to v

getPredecessors

public java.util.Set<V> getPredecessors(V v)

Returns set of predecessors of the given vertex

Parameters:

v - the vertex whose predecessors are to be retrieved

Returns:

the set of predecessors

labelDistances

public void labelDistances(Hypergraph<V,E> graph,
                           java.util.Set<V> rootSet)

Computes the distances of all the node from the starting root nodes. If there is more than one root node the minimum distance from each root node is used as the designated distance to a given node. Also keeps track of the predecessors of each node traversed as well as the order of nodes traversed.

Parameters:

graph - the graph to label

rootSet - the set of starting vertices to traverse from

labelDistances

public void labelDistances(Hypergraph<V,E> graph,
                           V root)

Computes the distances of all the node from the specified root node. Also keeps track of the predecessors of each node traversed as well as the order of nodes traversed.

Parameters:

graph - the graph to label

root - the single starting vertex to traverse from

getDistanceDecorator

public java.util.Map<V,java.lang.Number> getDistanceDecorator()

Must be called after labelDistances in order to contain valid data.

Returns:

a map from vertices to minimum distances from the original source(s)