Class 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 v
      java.util.Map<V,​java.lang.Number> getDistanceDecorator()
      Must be called after labelDistances in order to contain valid data.
      java.util.Set<V> getPredecessors​(V v)
      Returns set of predecessors of the given vertex
      java.util.Set<V> getUnvisitedVertices()
      Returns the set of all vertices that were not visited
      java.util.List<V> getVerticesInOrderVisited()
      Returns the list of vertices visited in order of traversal
      protected 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.
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Constructor Detail

      • 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 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 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 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 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
      • getDistanceDecorator

        public java.util.Map<V,​java.lang.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)