Class DFS

java.lang.Object
com.ibm.wala.util.graph.traverse.DFS

public class DFS extends Object
utilities related to depth-first search.
  • Constructor Details

    • DFS

      public DFS()
  • Method Details

    • getReachableNodes

      public static <T> Collection<T> getReachableNodes(Graph<T> G, Collection<? extends T> C, Predicate<? super T> filter)
      Perform a DFS starting with a particular node and return the set of all nodes visited.
      Parameters:
      C - collection of nodes to start from
      filter - only traverse nodes that need this filter
      Throws:
      IllegalArgumentException - if C is null
    • getReachableNodes

      public static <T> Set<T> getReachableNodes(Graph<T> G, Collection<? extends T> C)
      Perform a DFS starting with a particular node set and return the set of all nodes visited.
      Parameters:
      G - the graph containing n
      Returns:
      Set
      Throws:
      IllegalArgumentException - if C is null
    • getReachableNodes

      public static <T> Set<T> getReachableNodes(Graph<T> G) throws IllegalArgumentException
      Perform a DFS and return the set of all nodes visited.
      Parameters:
      G - the graph containing n
      Returns:
      Set
      Throws:
      IllegalArgumentException - if G == null
    • sortByDepthFirstOrder

      public static <T> SortedSet<T> sortByDepthFirstOrder(Graph<T> G, T n)
      Perform a DFS of a graph starting with a specified node and return a sorted list of nodes. The nodes are sorted by depth first order.
      Parameters:
      G - a graph
      n - the initial node
      Returns:
      a sorted set of nodes in the graph in depth first order
    • iterateDiscoverTime

      public static <T> DFSDiscoverTimeIterator<T> iterateDiscoverTime(Graph<T> G)
      Returns:
      iterator of nodes of G in order of DFS discover time
    • iterateDiscoverTime

      public static <T> Iterator<T> iterateDiscoverTime(Graph<T> G, Iterator<T> roots) throws IllegalArgumentException
      Parameters:
      roots - roots of traversal, in order to visit in outermost loop of DFS
      Returns:
      iterator of nodes of G in order of DFS discover time
      Throws:
      IllegalArgumentException - if roots == null
    • iterateDiscoverTime

      public static <T> DFSDiscoverTimeIterator<T> iterateDiscoverTime(Graph<T> G, T N)
      Parameters:
      N - root of traversal
      Returns:
      iterator of nodes of G in order of DFS discover time
    • iterateFinishTime

      public static <T> DFSFinishTimeIterator<T> iterateFinishTime(Graph<T> G) throws IllegalArgumentException
      Parameters:
      G - a graph
      Returns:
      iterator of nodes of G in order of DFS finish time
      Throws:
      IllegalArgumentException - if G == null
    • iterateFinishTime

      public static <T> DFSFinishTimeIterator<T> iterateFinishTime(Graph<T> G, @Nullable Iterator<? extends T> ie)
      Parameters:
      G - a graph
      ie - roots of traversal, in order to visit in outermost loop of DFS
      Returns:
      iterator of nodes of G in order of DFS finish time