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 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

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

Method Summary

int	getDistance(Hypergraph<V,E> g, V v) Given a vertex, returns the shortest distance from any node in the root set to v
Map<V,Number>	getDistanceDecorator() Returns a map from vertices to minimum distances from the original source(s).
Set<V>	getPredecessors(V v) Returns set of predecessors of the given vertex
Set<V>	getUnvisitedVertices() Returns the set of all vertices that were not visited
List<V>	getVerticesInOrderVisited() Returns the list of vertices visited in order of traversal
protected void	initialize(Hypergraph<V,E> g, Set<V> rootSet)
void	labelDistances(Hypergraph<V,E> graph, 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

clone, equals, finalize, 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 List<V> getVerticesInOrderVisited()

Returns the list of vertices visited in order of traversal

Returns:

the list of vertices

getUnvisitedVertices

public 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:

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<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

initialize

protected void initialize(Hypergraph<V,E> g,
                          Set<V> rootSet)

labelDistances

public void labelDistances(Hypergraph<V,E> graph,
                           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 Map<V,Number> getDistanceDecorator()

Returns a map from vertices to minimum distances from the original source(s). Must be called after labelDistances in order to contain valid data.