Class AllDirectedPaths<V,​E>

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

    public class AllDirectedPaths<V,​E>
    extends 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
    • Constructor Detail

      • AllDirectedPaths

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

      • getAllPaths

        public List<GraphPath<V,​E>> getAllPaths​(V sourceVertex,
                                                      V targetVertex,
                                                      boolean simplePathsOnly,
                                                      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 List<GraphPath<V,​E>> getAllPaths​(Set<V> sourceVertices,
                                                      Set<V> targetVertices,
                                                      boolean simplePathsOnly,
                                                      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