Class BFSDistanceLabeler<V,E>
java.lang.Object
edu.uci.ics.jung.algorithms.shortestpath.BFSDistanceLabeler<V,E>
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)
-
Field Summary
FieldsModifier and TypeFieldDescription -
Constructor Summary
ConstructorsConstructorDescriptionCreates 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
Modifier and TypeMethodDescriptionprivate void
addPredecessor
(V predecessor, V sucessor) int
getDistance
(Hypergraph<V, E> g, V v) Given a vertex, returns the shortest distance from any node in the root set to vMust be called afterlabelDistances
in order to contain valid data.getPredecessors
(V v) Returns set of predecessors of the given vertexReturns the set of all vertices that were not visitedReturns the list of vertices visited in order of traversalprotected 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.private void
visitNewVertex
(V predecessor, V neighbor, int distance, List<V> newList)
-
Field Details
-
distanceDecorator
-
mCurrentList
-
mUnvisitedVertices
-
mVerticesInOrderVisited
-
mPredecessorMap
-
-
Constructor Details
-
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 Details
-
getVerticesInOrderVisited
Returns the list of vertices visited in order of traversal- Returns:
- the list of vertices
-
getUnvisitedVertices
Returns the set of all vertices that were not visited- Returns:
- the list of unvisited vertices
-
getDistance
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
Returns set of predecessors of the given vertex- Parameters:
v
- the vertex whose predecessors are to be retrieved- Returns:
- the set of predecessors
-
initialize
-
addPredecessor
-
labelDistances
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
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
-
visitNewVertex
-
getDistanceDecorator
Must be called afterlabelDistances
in order to contain valid data.- Returns:
- a map from vertices to minimum distances from the original source(s)
-