Class BFSDistanceLabeler<V,E>

java.lang.Object
edu.uci.ics.jung.algorithms.shortestpath.BFSDistanceLabeler<V,E>
public class BFSDistanceLabeler<V,E> 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)

  • Field Details

    • distanceDecorator

      private Map<V,Number> distanceDecorator

    • mCurrentList

      private List<V> mCurrentList

    • mUnvisitedVertices

      private Set<V> mUnvisitedVertices

    • mVerticesInOrderVisited

      private List<V> mVerticesInOrderVisited

    • mPredecessorMap

      private Map<V, HashSet<V>> 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

      public List<V> getVerticesInOrderVisited()
      Returns the list of vertices visited in order of traversal
      Returns:
      the list of vertices

    • getUnvisitedVertices

      public 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 measured
      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<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, Set<V> rootSet)

    • addPredecessor

      private void addPredecessor(V predecessor, V sucessor)

    • labelDistances

      public void labelDistances(Hypergraph<V,E> graph, 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 label
      rootSet - 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 label
      root - the single starting vertex to traverse from

    • visitNewVertex

      private void visitNewVertex(V predecessor, V neighbor, int distance, List<V> newList)

    • getDistanceDecorator

      public Map<V,Number> getDistanceDecorator()
      Must be called after labelDistances in order to contain valid data.
      Returns:
      a map from vertices to minimum distances from the original source(s)