edu.uci.ics.jung.algorithms.connectivity
Class BFSDistanceLabeler

java.lang.Object
  edu.uci.ics.jung.algorithms.connectivity.BFSDistanceLabeler

public class BFSDistanceLabeler
extends 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)

Author:

Scott White

Field Summary

static String

DEFAULT_DISTANCE_KEY

Constructor Summary

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

BFSDistanceLabeler(String distanceKey)
Creates a new BFS labeler for the specified graph and root set.

Method Summary

int	getDistance(Graph g, Vertex v) Given a vertex, returns the shortest distance from any node in the root set to v
Set	getPredecessors(Vertex v) Returns set of predecessors of the given vertex
Set	getUnivistedVertices() Returns the set of all vertices that were not visited
List	getVerticesInOrderVisited() Returns the list of vertices visited in order of traversal
protected void	initialize(Graph g, Set rootSet)
void	labelDistances(Graph graph, Set rootSet) Computes the distances of all the node from the starting root nodes.
void	labelDistances(Graph graph, Vertex root) Computes the distances of all the node from the specified root node.
void	removeDecorations(Graph g)

Methods inherited from class java.lang.Object

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

Field Detail

DEFAULT_DISTANCE_KEY

public static final String DEFAULT_DISTANCE_KEY

See Also:

Constant Field Values

Constructor Detail

BFSDistanceLabeler

public BFSDistanceLabeler(String distanceKey)

Creates a new BFS labeler for the specified graph and root set.

Parameters:

distanceKey - the UserDatum key the algorithm should use to store/decorate the distances from the root set The distances are stored in the corresponding Vertex objects and are of type MutableInteger

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 List getVerticesInOrderVisited()

Returns the list of vertices visited in order of traversal

Returns:

the list of vertices

getUnivistedVertices

public Set getUnivistedVertices()

Returns the set of all vertices that were not visited

Returns:

the list of unvisited vertices

getDistance

public int getDistance(Graph g,
                       Vertex v)

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

Parameters:

v - the vertex whose distance is to be retrieved

Returns:

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

getPredecessors

public Set getPredecessors(Vertex v)

Returns set of predecessors of the given vertex

Parameters:

v - the vertex whose predecessors are to be retrieved

Returns:

the set of predecessors

initialize

protected void initialize(Graph g,
                          Set rootSet)

removeDecorations

public void removeDecorations(Graph g)

labelDistances

public void labelDistances(Graph graph,
                           Set 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(Graph graph,
                           Vertex root)

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

Parameters:

graph - the graph to label

root - the single starting vertex to traverse from