Class DFSPathFinder<T>

  • All Implemented Interfaces:
    java.io.Serializable, java.lang.Cloneable, java.lang.Iterable<T>, java.util.Collection<T>, java.util.List<T>, java.util.RandomAccess
    Direct Known Subclasses:
    DFSAllPathsFinder

    public class DFSPathFinder<T>
    extends java.util.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:
    Serialized Form
    • Field Summary

      Fields 
      Modifier and Type Field Description
      protected Graph<T> G
      The graph to search
      protected java.util.Map<java.lang.Object,​java.util.Iterator<? extends T>> pendingChildren
      An iterator of child nodes for each node being searched
      static long serialVersionUID  
      • Fields inherited from class java.util.AbstractList

        modCount
    • Constructor Summary

      Constructors 
      Constructor Description
      DFSPathFinder​(Graph<T> G, java.util.Iterator<T> nodes, java.util.function.Predicate<T> f)
      Construct a depth-first enumerator across the (possibly improper) subset of nodes reachable from the nodes in the given enumeration.
      DFSPathFinder​(Graph<T> G, T N, java.util.function.Predicate<T> f)
      Construct a depth-first enumerator starting with a particular node in a directed graph.
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      protected java.util.List<T> currentPath()  
      java.util.List<T> find()  
      protected java.util.Iterator<? extends T> getConnected​(T n)
      get the out edges of a given node
      protected java.util.Iterator<? extends T> getPendingChildren​(T n)
      Method getPendingChildren.
      boolean hasNext()
      Return whether there are any more nodes left to enumerate.
      protected void setPendingChildren​(T v, java.util.Iterator<? extends T> iterator)
      Method setPendingChildren.
      • 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.List

        containsAll
    • Field Detail

      • G

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

        protected final java.util.Map<java.lang.Object,​java.util.Iterator<? extends T>> pendingChildren
        An iterator of child nodes for each node being searched
    • Constructor Detail

      • DFSPathFinder

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

        public DFSPathFinder​(Graph<T> G,
                             java.util.Iterator<T> nodes,
                             java.util.function.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 Detail

      • find

        public java.util.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 java.util.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 java.util.Iterator<? extends T> getPendingChildren​(T n)
        Method getPendingChildren.
        Returns:
        Object
      • setPendingChildren

        protected void setPendingChildren​(T v,
                                          java.util.Iterator<? extends T> iterator)
        Method setPendingChildren.
        Parameters:
        v -
        iterator -
      • getConnected

        protected 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