[Perf] Speed up AllDirectedPaths non-simple-paths mode

[Shai Eilat]

Hi all,

Heads-up before opening a small performance PR on AllDirectedPaths. Pure refactor; no behavioural difference and no API change.

What's in the PR

Two small changes to AllDirectedPaths.generatePaths:

1. Guard the per-pop pathVertices HashSet rebuild behind simplePathsOnly. The set is only consulted by the simple-path self-intersection filter, so building it in simplePathsOnly = false mode was wasted O(path length) work per popped partial path. Java short-circuit evaluation means the field is only dereferenced when populated.

2. Switch the incompletePaths queue from LinkedList to ArrayDeque to remove per-node linked-list overhead. The queue is only used through the Deque interface (poll / addFirst / add / isEmpty), which ArrayDeque supports identically with better allocation behaviour.

Both changes are pure refactors with no behavioural difference. Existing tests (including testCycleBehavior, which exercises both simplePathsOnly = true and simplePathsOnly = false) stay green.

Benchmark

JMH bench at jgrapht-core/src/test/java/org/jgrapht/perf/shortestpath/AllDirectedPathsNonSimplePerformance.java. 5×5 cyclic grid with self-loops on every vertex, source = corner, target = adjacent vertex (1), non-simple-paths mode. JDK 21, @Fork 1, @Warmup 5×2s, @Measurement 8×2s. Run on master and on the branch with the same JMH file:

The relative speedup grows with maxPathLength as the inner loop becomes more amortised over JIT warmup.

Tests

AllDirectedPathsTest (14 tests, all pass). New cases:

• Two-vertex graph with self-loops on both, walks of length ≤ 3 (exact count 6).

• Three-vertex cycle without self-loops, walks of length ≤ 4 (exact count 2).

• pathValidator still consulted in non-simple mode.

• maxLength = 0 and maxLength = 1 boundary cases.

• Seeded fuzz comparing the algorithm's non-simple-mode walk multiset against an in-test brute-force DFS oracle on 5 random small cyclic digraphs.

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

I'll open a PR shortly unless someone wants me to hold for discussion.

Thanks, Shai Eilat