Module org.jgrapht.core

Package org.jgrapht.alg.shortestpath

Class DagAllPathsCounter

java.lang.Object

org.jgrapht.alg.shortestpath.DagAllPathsCounter

public final class DagAllPathsCounter
extends Object

Counts the number of simple directed paths in a Directed Acyclic Graph (DAG) between a given source and target using dynamic programming in topological order.

For large graphs the number of paths can be extremely large; values are returned as BigInteger.

Usage constraints: the provided graph must be directed and acyclic. An IllegalArgumentException is thrown otherwise.

Method Summary

Modifier and Type	Method	Description
static <V,E> BigInteger	countAllPaths(Graph<V,E> graph, V source, V target)	Count the number of simple directed paths from source to target in the given directed acyclic graph.

Methods inherited from class java.lang.Object

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

Method Detail

countAllPaths

public static <V,E> BigInteger countAllPaths(Graph<V,E> graph,
                                                   V source,
                                                   V target)

Count the number of simple directed paths from source to target in the given directed acyclic graph.

Edge case semantics:

• If source or target is not contained in the graph, throws IllegalArgumentException.
• If source.equals(target), the empty path (length 0) is counted as one path and paths that leave source and return to it cannot exist in a DAG, thus the result is 1.
• If there is no path from source to target, returns BigInteger.ZERO.

Type Parameters:

V - vertex type

E - edge type

Parameters:

graph - directed acyclic graph

source - source vertex

target - target vertex

Returns:

number of simple directed paths from source to target

Throws:

IllegalArgumentException - if the graph is not directed, not acyclic, or vertices are missing