[Proposal] Opt-in sandwich prune for AllDirectedPaths preprocessing

[Shai Eilat]

Hi all,

Posting before opening a PR on AllDirectedPaths because this one adds a new constructor argument and is worth getting feedback on before the API surface lands.

Summary

Adds an opt-in preprocessing step to AllDirectedPaths that drops edges that cannot lie on any feasible source-to-target walk within the budget, before the path-enumeration phase.

A new constructor argument useSandwichPrune (default false) controls the behaviour:

• false (default) — behave identically to current releases. The existing backward-only edge-decoration sweep runs unchanged. Default constructors AllDirectedPaths(graph) and AllDirectedPaths(graph, pathValidator) continue to take this path.

• true — first run a forward BFS from the source set bounded by maxPathLength, then in the backward sweep drop any edge (u, v) whose source u is not forward-reachable, or whose total forward + backward length exceeds maxPathLength. The condition is exact: any edge dropped cannot appear on a feasible source-to-target walk in either simplePathsOnly = true or simplePathsOnly = false mode.

Motivation

On workloads where many vertices are backward-reachable from the targets but not forward-reachable from the sources within maxPathLength, the existing backward-only sweep marks every such vertex even though the forward enumeration in generatePaths cannot reach any of them. Skipping the source-disconnected portion of the backward sweep is a clean local win when it fires.

On graphs where the sandwich condition never fires (e.g. small dense strongly-connected digraphs), enabling the prune adds the cost of one extra O(V + E) BFS per getAllPaths call. Hence the opt-in: callers who know their graph shape can pick the right path; the default is unchanged.

Design

A new private method vertexMinDistancesForwards(sourceVertices, maxPathLength) does a bounded forward BFS. Its result is threaded into the existing edgeMinDistancesBackwards as a nullable parameter. When the parameter is null (the useSandwichPrune = false path), edgeMinDistancesBackwards recovers the historical behaviour exactly. When non-null, the sandwich condition is applied per edge.

The sandwich inequality is written as forwardOfSource > maxPathLength - childDistance rather than the additive form to avoid integer overflow at extreme maxPathLength values; the BFS bounds guarantee childDistance <= maxPathLength, so the right-hand side stays non-negative.

Benchmark

JMH bench at jgrapht-core/src/test/java/org/jgrapht/perf/shortestpath/AllDirectedPathsSandwichPrunePerformance.java, parameterised over useSandwichPrune so both modes are exercised in the same JVM. JDK 21, @Fork 1, @Warmup 5×2s, @Measurement 8×2s.

Win case — forward chain of 20 vertices 0 → 1 → … → 19 = T plus a gardenSize-vertex source-disconnected garden, every garden vertex with an edge into T. Simple-paths mode, maxPathLength = 25.

Loss case — small dense strongly-connected digraph (V=20, maxLen=3) where every vertex is both forward-reachable from source and backward-reachable from target; the sandwich never fires.

Tests

AllDirectedPathsTest (15 tests, all pass). Each new case runs with both useSandwichPrune = false and useSandwichPrune = true and asserts the two modes produce the same path set. New cases:

• Single dead source-side branch on a small hand-built graph.

• Multiple sources with one isolated source and a source-disconnected garden.

• Unbounded simple paths (maxPathLength = null) with an unreachable garden behind the target.

• Source-equals-target where a second disconnected vertex feeds into the source.

• Small dense strongly-connected digraph (loss-case shape) where the prune cannot help, asserting both modes still produce the same paths.

• Seeded fuzz against an in-test brute-force enumeration oracle on 8 random digraphs with a source-unreachable pocket — covers both simple-paths and walks (non-simple) modes.

Full mvn -pl jgrapht-core test is green (6881 pass, 15 unrelated upstream skips). mvn -pl jgrapht-core checkstyle:check -P checkstyle and mvn -pl jgrapht-core javadoc:javadoc clean.

Open questions for the list

1. API placement. The new parameter ships as a third constructor argument: AllDirectedPaths(graph, pathValidator, useSandwichPrune). The two-arg and one-arg forms remain and call through to it with useSandwichPrune = false. Is that the right shape, or would the project prefer a setter / builder?

2. Default. useSandwichPrune defaults to false so callers in the wild see no behaviour or performance change. I can flip it to true if the project would rather make the more-often-better-on-typical-workloads behaviour the default, given the loss case is bounded to one extra O(V + E) BFS. I'd prefer to keep false as the default for the initial release and revisit in a follow-up after one release cycle.

3. Naming. useSandwichPrune is descriptive but project-internal terminology. Other options: useReachabilityPrune, useForwardReachabilityFilter, or something else. Open to suggestions.

If the design is broadly OK I'll open the PR; if any of the open questions need a different answer I'll fold the changes in first.

Thanks for reading.

— Shai Eilat

[John Sichi]

Makes sense, and here are my answers:

1) I think a setter would be best in this case

2) It seems beneficial to have this enabled by default, but if there's a reason for your preference, then I'm ok with defaulting to false for now

3) How about forwardPruning, so the setter would be setForwardPruning(boolean)?

--
You received this message because you are subscribed to the Google Groups "jgrapht-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to jgrapht-dev...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/jgrapht-dev/63198221-152e-4cdd-825d-e88636fadf99n%40googlegroups.com.

[Shai Eilat]

Hi,

Thanks for the answers.

Applied and opened pull request https://github.com/jgrapht/jgrapht/pull/1342 - Optimize AllDirectedPaths preprocessing with forward pruning