Class AllDirectedPaths<V,​E>

  • Type Parameters:
    V - the graph vertex type
    E - the graph edge type

    public class AllDirectedPaths<V,​E>
    extends java.lang.Object
    A Dijkstra-like algorithm to find all paths between two sets of nodes in a directed graph, with options to search only simple paths and to limit the path length.
    Author:
    Andrew Gainer-Dewar, Google LLC
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      java.util.List<GraphPath<V,​E>> getAllPaths​(java.util.Set<V> sourceVertices, java.util.Set<V> targetVertices, boolean simplePathsOnly, java.lang.Integer maxPathLength)
      Calculate (and return) all paths from the source vertices to the target vertices.
      java.util.List<GraphPath<V,​E>> getAllPaths​(V sourceVertex, V targetVertex, boolean simplePathsOnly, java.lang.Integer maxPathLength)
      Calculate (and return) all paths from the source vertex to the target vertex.
      • Methods inherited from class java.lang.Object

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

      • AllDirectedPaths

        public AllDirectedPaths​(Graph<V,​E> graph)
        Create a new instance.
        Parameters:
        graph - the input graph
        Throws:
        java.lang.IllegalArgumentException - if the graph is not directed
      • AllDirectedPaths

        public AllDirectedPaths​(Graph<V,​E> graph,
                                PathValidator<V,​E> pathValidator)
        Create a new instance with given pathValidator. If non-null, the pathValidator will be used while searching for paths, validating the addition of any edge to a partial path. Zero-length paths will therefore not be subject to pathValidator; length-1 paths will.
        Parameters:
        graph - the input graph
        pathValidator - validator for computed paths; may be null
        Throws:
        java.lang.IllegalArgumentException - if the graph is not directed
    • Method Detail

      • getAllPaths

        public java.util.List<GraphPath<V,​E>> getAllPaths​(V sourceVertex,
                                                                V targetVertex,
                                                                boolean simplePathsOnly,
                                                                java.lang.Integer maxPathLength)
        Calculate (and return) all paths from the source vertex to the target vertex.
        Parameters:
        sourceVertex - the source vertex
        targetVertex - the target vertex
        simplePathsOnly - if true, only search simple (non-self-intersecting) paths
        maxPathLength - maximum number of edges to allow in a path (if null, all paths are considered, which may be very slow due to potentially huge output)
        Returns:
        all paths from the source vertex to the target vertex
      • getAllPaths

        public java.util.List<GraphPath<V,​E>> getAllPaths​(java.util.Set<V> sourceVertices,
                                                                java.util.Set<V> targetVertices,
                                                                boolean simplePathsOnly,
                                                                java.lang.Integer maxPathLength)
        Calculate (and return) all paths from the source vertices to the target vertices.
        Parameters:
        sourceVertices - the source vertices
        targetVertices - the target vertices
        simplePathsOnly - if true, only search simple (non-self-intersecting) paths
        maxPathLength - maximum number of edges to allow in a path (if null, all paths are considered, which may be very slow due to potentially huge output)
        Returns:
        list of all paths from the sources to the targets containing no more than maxPathLength edges