Class BoundedBFSIterator<T>

  • All Implemented Interfaces:
    java.util.Iterator<T>

    public class BoundedBFSIterator<T>
    extends java.lang.Object
    implements java.util.Iterator<T>
    This class implements breadth-first search over a Graph, returning an Iterator of the nodes of the graph in order of discovery. This class follows the outNodes of the graph nodes to define the graph, but this behavior can be changed by overriding the getConnected method. This traversal only visits nodes within k hops of a root.
    • Field Summary

      Fields 
      Modifier and Type Field Description
      protected Graph<T> G
      Governing Graph
    • Constructor Summary

      Constructors 
      Constructor Description
      BoundedBFSIterator​(Graph<T> G, java.util.Iterator<? extends T> nodes, int k)
      Construct a breadth-first enumerator across the (possibly improper) subset of nodes reachable from the nodes in the given enumeration.
      BoundedBFSIterator​(Graph<T> G, T N, int k)
      Construct a breadth-first iterator starting with a particular node in a directed graph.
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      protected java.util.Iterator<? extends T> getConnected​(T n)
      get the out edges of a given node
      int getCurrentHops()  
      boolean hasNext()
      Return whether there are any more nodes left to enumerate.
      T next()
      Find the next graph node in discover time order.
      void remove()  
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
      • Methods inherited from interface java.util.Iterator

        forEachRemaining
    • Field Detail

      • G

        protected Graph<T> G
        Governing Graph
    • Constructor Detail

      • BoundedBFSIterator

        public BoundedBFSIterator​(Graph<T> G,
                                  T N,
                                  int k)
        Construct a breadth-first iterator starting with a particular node in a directed graph.
        Parameters:
        G - the graph whose nodes to enumerate
        Throws:
        java.lang.IllegalArgumentException - if G is null
      • BoundedBFSIterator

        public BoundedBFSIterator​(Graph<T> G,
                                  java.util.Iterator<? extends T> nodes,
                                  int k)
        Construct a breadth-first enumerator across the (possibly improper) subset of nodes reachable from the nodes in the given enumeration.
        Parameters:
        G - the graph whose nodes to enumerate
        nodes - the set of nodes from which to start searching
        Throws:
        java.lang.IllegalArgumentException - if G is null
    • Method Detail

      • hasNext

        public boolean hasNext()
        Return whether there are any more nodes left to enumerate.
        Specified by:
        hasNext in interface java.util.Iterator<T>
        Returns:
        true if there nodes left to enumerate.
      • next

        public T next()
               throws java.util.NoSuchElementException
        Find the next graph node in discover time order.
        Specified by:
        next in interface java.util.Iterator<T>
        Returns:
        the next graph node in discover time order.
        Throws:
        java.util.NoSuchElementException
      • getConnected

        protected java.util.Iterator<? extends T> getConnected​(T n)
        get the out edges of a given node
        Parameters:
        n - the node of which to get the out edges
        Returns:
        the out edges
      • remove

        public void remove()
                    throws java.lang.UnsupportedOperationException
        Specified by:
        remove in interface java.util.Iterator<T>
        Throws:
        java.lang.UnsupportedOperationException
      • getCurrentHops

        public int getCurrentHops()
        Returns:
        the currentHops