Class BFSPathFinder<T>


  • public class BFSPathFinder<T>
    extends java.lang.Object
    This class searches breadth-first 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. TODO: if finding many paths, use a dynamic programming algorithm instead of calling this repeatedly.
    • Constructor Summary

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

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      java.util.List<T> find()  
      protected java.util.Iterator<? extends T> getConnected​(T n)
      get the out edges of a given node
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Constructor Detail

      • BFSPathFinder

        public BFSPathFinder​(Graph<T> G,
                             T N,
                             java.util.function.Predicate<T> f)
        Construct a breadth-first enumerator starting with a particular node in a directed graph.
        Parameters:
        G - the graph whose nodes to enumerate
      • BFSPathFinder

        public BFSPathFinder​(Graph<T> G,
                             T src,
                             T target)
                      throws java.lang.IllegalArgumentException
        Construct a breadth-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
      • BFSPathFinder

        public BFSPathFinder​(Graph<T> G,
                             T src,
                             java.util.Iterator<T> targets)
        Construct a breadth-first enumerator starting with a particular node in a directed graph.
        Parameters:
        G - the graph whose nodes to enumerate
      • BFSPathFinder

        public BFSPathFinder​(Graph<T> G,
                             java.util.Iterator<T> sources,
                             T target)
        Construct a breadth-first enumerator starting with any of a set of nodes in a directed graph.
        Parameters:
        G - the graph whose nodes to enumerate
      • BFSPathFinder

        public BFSPathFinder​(Graph<T> G,
                             java.util.Iterator<T> nodes,
                             java.util.function.Predicate<T> f)
        Construct a breadth-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.
      • 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