Overview | Package | Class | Use | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

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

Overview | Package | Class | Use | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD