Class DFSPathFinder<V>

  • Type Parameters:
    V - the node type of the graph
    All Implemented Interfaces:
    IGraphPathFinder<V>

    public class DFSPathFinder<V>
    extends java.lang.Object
    implements IGraphPathFinder<V>
    A depth-first search implementation of the IGraphPathFinder. TODO use ITC to filter nodes that must be traversed, instead of checks
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      java.lang.Iterable<java.util.Deque<V>> getAllPaths​(V sourceNode, V targetNode)
      Returns the collection of paths from the source node to the target node (if such exists).
      java.lang.Iterable<java.util.Deque<V>> getAllPathsToTargets​(V sourceNode, java.util.Set<V> targetNodes)
      Returns the collection of paths from the source node to any of the target nodes (if such exists).
      java.util.Deque<V> getPath​(V sourceNode, V targetNode)
      Returns an arbitrary path from the source node to the target node (if such exists).
      protected java.lang.Iterable<java.util.Deque<V>> getPaths​(java.util.List<java.util.Deque<V>> paths, java.util.Deque<V> visited, java.util.Set<V> targetNodes)  
      java.lang.Iterable<java.util.Deque<V>> getShortestPaths​(V sourceNode, V targetNode)
      Returns the collection of shortest paths from the source node to the target node (if such exists).
      java.lang.String printPaths​(java.util.List<java.util.Deque<V>> paths)  
      • Methods inherited from class java.lang.Object

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

      • getAllPaths

        public java.lang.Iterable<java.util.Deque<V>> getAllPaths​(V sourceNode,
                                                                  V targetNode)
        Description copied from interface: IGraphPathFinder
        Returns the collection of paths from the source node to the target node (if such exists). If there is no path between them, an empty collection is returned.
        Specified by:
        getAllPaths in interface IGraphPathFinder<V>
        Parameters:
        sourceNode - the source node of the path
        targetNode - the target node of the path
        Returns:
        the collection of paths from the source to the target, or empty collection if target is not reachable from source.
      • getAllPathsToTargets

        public java.lang.Iterable<java.util.Deque<V>> getAllPathsToTargets​(V sourceNode,
                                                                           java.util.Set<V> targetNodes)
        Description copied from interface: IGraphPathFinder
        Returns the collection of paths from the source node to any of the target nodes (if such exists). If there is no path between them, an empty collection is returned.
        Specified by:
        getAllPathsToTargets in interface IGraphPathFinder<V>
        Parameters:
        sourceNode - the source node of the path
        targetNodes - the set of target nodes of the paths
        Returns:
        the collection of paths from the source to any of the targets, or empty collection if neither target is reachable from source.
      • getPaths

        protected java.lang.Iterable<java.util.Deque<V>> getPaths​(java.util.List<java.util.Deque<V>> paths,
                                                                  java.util.Deque<V> visited,
                                                                  java.util.Set<V> targetNodes)
      • printPaths

        public java.lang.String printPaths​(java.util.List<java.util.Deque<V>> paths)
      • getPath

        public java.util.Deque<V> getPath​(V sourceNode,
                                          V targetNode)
        Description copied from interface: IGraphPathFinder
        Returns an arbitrary path from the source node to the target node (if such exists). If there is no path between them, an empty collection is returned.
        Specified by:
        getPath in interface IGraphPathFinder<V>
        Parameters:
        sourceNode - the source node of the path
        targetNode - the target node of the path
        Returns:
        the path from the source to the target, or empty collection if target is not reachable from source.
      • getShortestPaths

        public java.lang.Iterable<java.util.Deque<V>> getShortestPaths​(V sourceNode,
                                                                       V targetNode)
        Description copied from interface: IGraphPathFinder
        Returns the collection of shortest paths from the source node to the target node (if such exists). If there is no path between them, an empty collection is returned.
        Specified by:
        getShortestPaths in interface IGraphPathFinder<V>
        Parameters:
        sourceNode - the source node of the path
        targetNode - the target node of the path
        Returns:
        the collection of shortest paths from the source to the target, or empty collection if target is not reachable from source.