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.

Author:

Andrew Gainer-Dewar, Google LLC

Constructor Summary

Constructors

Constructor	Description
AllDirectedPaths(Graph<V,E> graph)	Create a new instance.
AllDirectedPaths(Graph<V,E> graph, PathValidator<V,E> pathValidator)	Create a new instance with given pathValidator.

Method Summary

Modifier and Type	Method	Description
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.
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.

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:

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