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.

  • Field Details

    • graph

      private final Graph<V,E> graph

    • pathValidator

      private final PathValidator<V,E> pathValidator
      Provides validation for the paths which will be computed. If the validator is null, this means that all paths are valid.

  • 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

    • 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

    • edgeMinDistancesBackwards

      private Map<E,Integer> edgeMinDistancesBackwards(Set<V> targetVertices, Integer maxPathLength)
      Compute the minimum number of edges in a path to the targets through each edge, so long as it is not greater than a bound.
      Parameters:
      targetVertices - the target vertices
      maxPathLength - maximum number of edges to allow in a path (if null, all edges will be considered, which may be expensive)
      Returns:
      the minimum number of edges in a path from each edge to the targets, encoded in a Map

    • generatePaths

      private List<GraphPath<V,E>> generatePaths(Set<V> sourceVertices, Set<V> targetVertices, boolean simplePathsOnly, Integer maxPathLength, Map<E,Integer> edgeMinDistancesFromTargets)
      Generate all paths from the sources to the targets, using pre-computed minimum distances.
      Parameters:
      sourceVertices - the source vertices
      targetVertices - the target vertices
      simplePathsOnly - if true, only search simple (non-self-intersecting) paths (if null, all edges will be considered, which may be expensive)
      maxPathLength - maximum number of edges to allow in a path
      edgeMinDistancesFromTargets - the minimum number of edges in a path to a target through each edge, as computed by edgeMinDistancesBackwards.
      Returns:
      a List of all GraphPaths from the sources to the targets satisfying the given constraints

    • makePath

      private GraphPath<V,E> makePath(List<E> edges)
      Transform an ordered list of edges into a GraphPath. The weight of the generated GraphPath is set to the sum of the weights of the edges.
      Parameters:
      edges - the edges
      Returns:
      the corresponding GraphPath