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

Class DFSDiscoverTimeIterator<T>

  • All Implemented Interfaces:
    java.io.Serializable, java.lang.Cloneable, java.lang.Iterable<T>, java.util.Collection<T>, java.util.Iterator<T>, java.util.List<T>, java.util.RandomAccess
    Direct Known Subclasses:
    NumberedDFSDiscoverTimeIterator, SlowDFSDiscoverTimeIterator
    public abstract class DFSDiscoverTimeIterator<T>
extends java.util.ArrayList<T>
implements java.util.Iterator<T>
    This class implements depth-first search over a NumberedGraph, return an enumeration of the nodes of the graph in order of increasing discover time. This class follows the outNodes of the graph nodes to define the graph, but this behavior can be changed by overriding the getConnected method.
    See Also:
    Serialized Form

    • Field Summary

      • Fields inherited from class java.util.AbstractList

        modCount

    • Method Summary

      All Methods Instance Methods Abstract Methods Concrete Methods 
      Modifier and Type Method Description
      protected abstract java.util.Iterator<? extends T> getConnected​(T n)
      get the out edges of a given node
      protected abstract java.util.Iterator<? extends T> getPendingChildren​(T n)  
      boolean hasNext()
      Return whether there are any more nodes left to enumerate.
      protected void init​(java.util.Iterator<? extends T> nodes)
      subclass constructors must call this!
      protected void init​(T N)
      subclass constructors must call this!
      T next()
      Find the next graph node in discover time order.
      void remove()  
      protected abstract void setPendingChildren​(T v, java.util.Iterator<? extends T> iterator)  
      protected void visitEdge​(T from, T to)  

      • Methods inherited from class java.util.ArrayList

        add, add, addAll, addAll, clear, clone, contains, ensureCapacity, equals, forEach, get, hashCode, indexOf, isEmpty, iterator, lastIndexOf, listIterator, listIterator, remove, remove, removeAll, removeIf, removeRange, replaceAll, retainAll, set, size, sort, spliterator, subList, toArray, toArray, trimToSize

      • Methods inherited from class java.util.AbstractCollection

        containsAll, toString

      • Methods inherited from class java.lang.Object

        finalize, getClass, notify, notifyAll, wait, wait, wait

      • Methods inherited from interface java.util.Collection

        parallelStream, stream, toArray

      • Methods inherited from interface java.util.Iterator

        forEachRemaining

      • Methods inherited from interface java.util.List

        containsAll

    • Constructor Detail

      • DFSDiscoverTimeIterator

        public DFSDiscoverTimeIterator()

    • Method Detail

      • init

        protected void init​(java.util.Iterator<? extends T> nodes)
        subclass constructors must call this!

      • init

        protected void init​(T N)
        subclass constructors must call this!

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

      • getPendingChildren

        protected abstract java.util.Iterator<? extends T> getPendingChildren​(T n)

      • setPendingChildren

        protected abstract void setPendingChildren​(T v,
                                           java.util.Iterator<? extends T> iterator)

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

      • visitEdge

        protected void visitEdge​(T from,
                         T to)
        Parameters:
        from - source of the edge to visit
        to - target of the edge to visit