Class DFS


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

      • DFS

        public DFS()
    • Method Detail

      • getReachableNodes

        public static <T> java.util.Collection<T> getReachableNodes​(Graph<T> G,
                                                                    java.util.Collection<? extends T> C,
                                                                    java.util.function.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:
        java.lang.IllegalArgumentException - if C is null
      • getReachableNodes

        public static <T> java.util.Set<T> getReachableNodes​(Graph<T> G,
                                                             java.util.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:
        java.lang.IllegalArgumentException - if C is null
      • getReachableNodes

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

        public static <T> java.util.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> java.util.Iterator<T> iterateDiscoverTime​(Graph<T> G,
                                                                    java.util.Iterator<T> roots)
                                                             throws java.lang.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:
        java.lang.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 java.lang.IllegalArgumentException
        Parameters:
        G - a graph
        Returns:
        iterator of nodes of G in order of DFS finish time
        Throws:
        java.lang.IllegalArgumentException - if G == null
      • iterateFinishTime

        public static <T> DFSFinishTimeIterator<T> iterateFinishTime​(Graph<T> G,
                                                                     java.util.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