public class BFSDistanceLabeler
extends java.lang.Object
Running time is: O(m)
Modifier and Type | Field and Description |
---|---|
static java.lang.String |
DEFAULT_DISTANCE_KEY |
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
|
BFSDistanceLabeler(java.lang.String distanceKey)
Creates a new BFS labeler for the specified graph and root set.
|
Modifier and Type | Method and Description |
---|---|
int |
getDistance(Graph g,
Vertex v)
Given a vertex, returns the shortest distance from any node in the root set to v
|
java.util.Set |
getPredecessors(Vertex v)
Returns set of predecessors of the given vertex
|
java.util.Set |
getUnivistedVertices()
Returns the set of all vertices that were not visited
|
java.util.List |
getVerticesInOrderVisited()
Returns the list of vertices visited in order of traversal
|
protected void |
initialize(Graph g,
java.util.Set rootSet) |
void |
labelDistances(Graph graph,
java.util.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) |
public static final java.lang.String DEFAULT_DISTANCE_KEY
public BFSDistanceLabeler(java.lang.String distanceKey)
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 MutableIntegerpublic BFSDistanceLabeler()
public java.util.List getVerticesInOrderVisited()
public java.util.Set getUnivistedVertices()
public int getDistance(Graph g, Vertex v)
v
- the vertex whose distance is to be retrievedpublic java.util.Set getPredecessors(Vertex v)
v
- the vertex whose predecessors are to be retrievedprotected void initialize(Graph g, java.util.Set rootSet)
public void removeDecorations(Graph g)
public void labelDistances(Graph graph, java.util.Set rootSet)
graph
- the graph to labelrootSet
- the set of starting vertices to traverse frompublic void labelDistances(Graph graph, Vertex root)
graph
- the graph to labelroot
- the single starting vertex to traverse from