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.

Field Summary

Fields

Modifier and Type	Field	Description
private Graph<V,E>	graph
private PathValidator<V,E>	pathValidator	Provides validation for the paths which will be computed.

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
private java.util.Map<E,java.lang.Integer>	edgeMinDistancesBackwards(java.util.Set<V> targetVertices, java.lang.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.
private java.util.List<GraphPath<V,E>>	generatePaths(java.util.Set<V> sourceVertices, java.util.Set<V> targetVertices, boolean simplePathsOnly, java.lang.Integer maxPathLength, java.util.Map<E,java.lang.Integer> edgeMinDistancesFromTargets)	Generate all paths from the sources to the targets, using pre-computed minimum distances.
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.
private GraphPath<V,E>	makePath(java.util.List<E> edges)	Transform an ordered list of edges into a GraphPath.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

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

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:

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

edgeMinDistancesBackwards

private java.util.Map<E,java.lang.Integer> edgeMinDistancesBackwards(java.util.Set<V> targetVertices,
                                                                           java.lang.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 java.util.List<GraphPath<V,E>> generatePaths(java.util.Set<V> sourceVertices,
                                                           java.util.Set<V> targetVertices,
                                                           boolean simplePathsOnly,
                                                           java.lang.Integer maxPathLength,
                                                           java.util.Map<E,java.lang.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

maxPathLength - maximum number of edges to allow in a path

simplePathsOnly - if true, only search simple (non-self-intersecting) paths (if null, all edges will be considered, which may be expensive)

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(java.util.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