Class BFSDistanceLabeler<V,E>
- java.lang.Object
-
- edu.uci.ics.jung.algorithms.shortestpath.BFSDistanceLabeler<V,E>
-
public class BFSDistanceLabeler<V,E> extends java.lang.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
Constructors Constructor 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
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description int
getDistance(Hypergraph<V,E> g, V v)
Given a vertex, returns the shortest distance from any node in the root set to vjava.util.Map<V,java.lang.Number>
getDistanceDecorator()
Must be called afterlabelDistances
in order to contain valid data.java.util.Set<V>
getPredecessors(V v)
Returns set of predecessors of the given vertexjava.util.Set<V>
getUnvisitedVertices()
Returns the set of all vertices that were not visitedjava.util.List<V>
getVerticesInOrderVisited()
Returns the list of vertices visited in order of traversalprotected void
initialize(Hypergraph<V,E> g, java.util.Set<V> rootSet)
void
labelDistances(Hypergraph<V,E> graph, java.util.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.
-
-
-
Method Detail
-
getVerticesInOrderVisited
public java.util.List<V> getVerticesInOrderVisited()
Returns the list of vertices visited in order of traversal- Returns:
- the list of vertices
-
getUnvisitedVertices
public java.util.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:
g
- the graph in which the distances are to be measuredv
- the vertex whose distance is to be retrieved- Returns:
- the shortest distance from any node in the root set to v
-
getPredecessors
public java.util.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, java.util.Set<V> rootSet)
-
labelDistances
public void labelDistances(Hypergraph<V,E> graph, java.util.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 labelrootSet
- 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 labelroot
- the single starting vertex to traverse from
-
getDistanceDecorator
public java.util.Map<V,java.lang.Number> getDistanceDecorator()
Must be called afterlabelDistances
in order to contain valid data.- Returns:
- a map from vertices to minimum distances from the original source(s)
-
-