Class DFS


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

      • DFS

        public DFS()
    • Method Detail

      • getReachableNodes

        public static <T> Collection<T> getReachableNodes​(Graph<T> G,
                                                          Collection<? extends T> C,
                                                          Predicate 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
      • 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)
        Parameters:
        G -
        Returns:
        iterator of nodes of G in order of DFS discover time
      • 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,
                                                                     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