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 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

    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 Details

    • 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 Details

    • 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