Package com.ibm.wala.util.graph.traverse

Class BFSIterator<T>

java.lang.Object
com.ibm.wala.util.graph.traverse.BFSIterator<T>
All Implemented Interfaces:
Iterator<T>
public class BFSIterator<T> extends Object implements 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.

  • Field Summary

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

  • Constructor Summary

    Constructors
    Constructor
    Description
    BFSIterator(Graph<T> G)
    Constructor DFSFinishTimeIterator.
    BFSIterator(Graph<T> G, @Nullable Iterator<? extends T> nodes)
    Construct a breadth-first enumerator across the (possibly improper) subset of nodes reachable from the nodes in the given enumeration.
    BFSIterator(Graph<T> G, T N)
    Construct a breadth-first iterator starting with a particular node in a directed graph.

  • Method Summary

    Modifier and Type
    Method
    Description
    protected Iterator<? extends T>
    getConnected(T n)
    get the out edges of a given node
    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 Details

    • G

      protected Graph<T> G
      Governing Graph

  • Constructor Details

    • BFSIterator

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

    • BFSIterator

      public BFSIterator(Graph<T> G, @Nullable Iterator<? extends T> nodes)
      Construct a breadth-first enumerator across the (possibly improper) subset of nodes reachable from the nodes in the given enumeration.
      Parameters:
      nodes - the set of nodes from which to start searching
      Throws:
      IllegalArgumentException - if G is null

    • BFSIterator

      public BFSIterator(Graph<T> G) throws NullPointerException
      Constructor DFSFinishTimeIterator.
      Throws:
      NullPointerException - if G is null

  • Method Details

    • hasNext

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

    • next

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

    • getConnected

      protected 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 UnimplementedError
      Specified by:
      remove in interface Iterator<T>
      Throws:
      UnimplementedError