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

java.lang.Object
  extended by 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.



Copyright © 2009. All Rights Reserved.