Module org.jgrapht.core
Package org.jgrapht.alg.shortestpath

Class AllDirectedPaths<V,E>

java.lang.Object
org.jgrapht.alg.shortestpath.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.

The algorithm runs in two phases. Preprocessing decorates each edge with the minimum number of edges still needed to reach a target. Enumeration then walks the decorated edges from the source set, using the decoration to abandon any partial path that cannot complete within the budget. By default a forward BFS from the source set is also run as part of preprocessing, so that edges whose source endpoint is not reachable from any requested source within the budget are dropped from the decoration up front. This can substantially reduce preprocessing cost on graphs where a non-trivial fraction of the target-reachable subgraph is not reachable from the sources. See setForwardPruning(boolean) for how to disable it.

Author:
Andrew Gainer-Dewar, Google LLC

  • Constructor Details

    • AllDirectedPaths

      public AllDirectedPaths(Graph<V,E> graph)
      Create a new instance.
      Parameters:
      graph - the input graph
      Throws:
      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:
      IllegalArgumentException - if the graph is not directed

  • Method Details

    • setForwardPruning

      public void setForwardPruning(boolean forwardPruning)
      Configure whether the preprocessing step applies the forward-pruning optimisation.

      When forward pruning is enabled (the default), getAllPaths(V, V, boolean, java.lang.Integer) first runs a forward BFS from the source set and uses the result to drop edges whose source endpoint is not reachable from any source within the bound, or whose forward-plus-backward length exceeds the bound. The prune is exact — it never drops an edge that could lie on a feasible source-to-target walk — and can be a large win when a substantial fraction of the graph is backward-reachable from the targets but not forward-reachable from the sources. On graphs where the prune never fires (e.g. small dense strongly-connected digraphs), the optimisation adds the cost of one extra O(V + E) BFS per getAllPaths call.

      Setting forward pruning to false recovers the historical preprocessing behaviour exactly — useful when the cost of the extra BFS is known to dominate.

      Parameters:
      forwardPruning - whether to apply the forward-pruning preprocessing step

    • isForwardPruning

      public boolean isForwardPruning()
      Whether the preprocessing step currently applies the forward-pruning optimisation.
      Returns:
      true if forward pruning is enabled
      See Also:

    • 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