public class BFSDistanceLabeler<V,E> extends Object
Running time is: O(m)
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
|
Modifier and Type | Method and Description |
---|---|
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()
Must be called after
labelDistances in order to contain valid data. |
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.
|
public BFSDistanceLabeler()
public List<V> getVerticesInOrderVisited()
public Set<V> getUnvisitedVertices()
public int getDistance(Hypergraph<V,E> g, V v)
g
- the graph in which the distances are to be measuredv
- the vertex whose distance is to be retrievedpublic Set<V> getPredecessors(V v)
v
- the vertex whose predecessors are to be retrievedprotected void initialize(Hypergraph<V,E> g, Set<V> rootSet)
public void labelDistances(Hypergraph<V,E> graph, Set<V> rootSet)
graph
- the graph to labelrootSet
- the set of starting vertices to traverse frompublic void labelDistances(Hypergraph<V,E> graph, V root)
graph
- the graph to labelroot
- the single starting vertex to traverse fromCopyright © 2015. All rights reserved.