Class DFSPathFinder<T>

  • All Implemented Interfaces:
    Serializable, Cloneable, Iterable<T>, Collection<T>, List<T>, RandomAccess
    Direct Known Subclasses:
    DFSAllPathsFinder

    public class DFSPathFinder<T>
    extends Stack<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 Detail

      • 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 Detail

      • 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 Detail

      • find

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

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