Class DFSPathFinder<T>

java.lang.Object
java.util.AbstractCollection<T>
java.util.AbstractList<T>
java.util.ArrayList<T>
com.ibm.wala.util.graph.traverse.DFSPathFinder<T>
All Implemented Interfaces:
Serializable, Cloneable, Iterable<T>, Collection<T>, List<T>, RandomAccess, SequencedCollection<T>
Direct Known Subclasses:
DFSAllPathsFinder

public class DFSPathFinder<T> extends ArrayList<T>
This class searches depth-first search for node that matches some criteria. If found, it reports a path to the first node found.

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:
  • Field Details

    • serialVersionUID

      public static final long serialVersionUID
      See Also:
    • G

      protected final Graph<T> G
      The graph to search
    • pendingChildren

      protected final Map<Object,Iterator<? extends T>> pendingChildren
      An iterator of child nodes for each node being searched
  • Constructor Details

    • DFSPathFinder

      public DFSPathFinder(Graph<T> G, T N, Predicate<T> f) throws IllegalArgumentException
      Construct a depth-first enumerator starting with a particular node in a directed graph.
      Parameters:
      G - the graph whose nodes to enumerate
      Throws:
      IllegalArgumentException - if G is null
    • DFSPathFinder

      public DFSPathFinder(Graph<T> G, Iterator<T> nodes, Predicate<T> f)
      Construct a depth-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
  • Method Details

    • find

      public @Nullable List<T> find()
      Returns:
      a List of nodes that specifies the first path found from a root to a node accepted by the filter. Returns null if no path found.
    • currentPath

      protected List<T> currentPath()
    • hasNext

      public boolean hasNext()
      Return whether there are any more nodes left to enumerate.
      Returns:
      true if there nodes left to enumerate.
    • getPendingChildren

      protected @Nullable Iterator<? extends T> getPendingChildren(T n)
      Method getPendingChildren.
      Returns:
      Object
    • setPendingChildren

      protected void setPendingChildren(T v, Iterator<? extends T> iterator)
      Method setPendingChildren.
    • 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