Package org.jgrapht.alg.shortestpath

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

    • Constructor Summary

      Constructors 
      Constructor Description
      AllDirectedPaths​(Graph<V,​E> graph)
      Create a new instance.

    • 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

    • 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