[Docs] Replace stale `visualizations.html` with an interactive K-shortest / AllDirectedPaths visualization — heads-up before opening a PR

[Shai Eilat]

Hi all,

Heads-up on a documentation contribution before opening anything upstream. I've built a self-contained interactive web visualization that animates and compares the K-shortest-path family and the recent `AllDirectedPaths` forward-pruning preprocessing step, and I'd like to propose using it to replace the existing `docs/visualizations.html`. Looking for sign-off from the dev list (and any pushback on the scope change) before I open the PR.

## Live demo

https://seilat.github.io/jgrapht/visualizations/

One HTML file, no build step, no external CSS or JS, ~85 KB. Three modes:

1. **K-shortest paths.** Per-pane algorithm dropdown picks any two of:
   - classical `YenKShortestPath`
   - `BoundedPrunedYenKShortestPath` with `AStarSpurEngine` and `setBoundedPruning(false)` (= Yen + A* spur, no bounded layer)
   - `BoundedPrunedYenKShortestPath` with `DijkstraSpurEngine`
   - `BoundedPrunedYenKShortestPath` with `AStarSpurEngine` (= full)
   - `EppsteinKShortestPath`

2. **Single shortest path.** `DijkstraShortestPath` vs `AStarShortestPath` with a reverse-Dijkstra admissible heuristic.

3. **AllDirectedPaths forward pruning.** Baseline `edgeMinDistancesBackwards` vs the forward+backward gate added in PR #1341. Pane B's forward-BFS prelude plays alone first; pane A's backward BFS catches up once the prelude finishes, mirroring the runtime story.

Each step is animated with per-event explanations (e.g. "Spur task starts at `1,1` — lower bound is `prefixCost (3) + h[spurNode] = 7`; the bounded driver only ran it because no cheaper candidate is known yet"), and a glossary covers expansion, relaxation, admissibility, the sandwich / forward-pruning gate, Eppstein tree edges, and the sidetrack `δ(u,v)` labels.

Algorithm fidelity to the Java code — reverse-Dijkstra used as both A*'s admissible heuristic and the lower-bound oracle for the bounded-prune task queue, impossible-spur skip (the chain pathology collapses to zero spur calls), forward-BFS-gated edge decoration with the same `dF(u) + 1 + dB(v) ≤ budget` rule, Eppstein's SPT construction and per-edge sidetrack labelling.

## Why this is a scope change, not just a refresh

`docs/visualizations.html` is the original 2003 JGraph-applet page authored by Barak Naveh. Its promise is *"see a JGraphT graph rendered in your browser, drag the vertices"* — i.e. a live view of a `ListenableGraph` via the now-defunct `JGraphAdapterDemo` applet. The page itself flags this as broken: it carries an explicit "THIS PAGE IS OUT OF DATE" banner and points to the closed issues #522 / #523 about dropping the JGraph integration.

Restoring the original contract for modern browsers is a non-trivial gap. The applet host is gone, the `JGraph` library it depended on is dead, its successor `JGraphX` is Swing-only, and `mxGraph` (the JS library) is a separate codebase that was itself deprecated in 2020. The realistic paths are (a) CheerpJ to run the 2003 bytecode in a WASM JVM, (b) a JGraphT-to-Cytoscape.js JSON bridge for static display, or (c) a server-side JVM with WebSocket to keep editing round-trips alive — none of which are zero-cost, and (a)/(b) restore only the "display" half of the original, not the "live JGraphT model" half.

What I'm proposing is a different contract: instead of *"see a JGraphT graph rendered"*, the page becomes *"see a JGraphT algorithm animated step-by-step"*. That's the use case that actually motivates clicking "Visualizations" on the docs site in 2026 — explaining what `YenKShortestPath`, `BoundedPrunedYenKShortestPath`, `AllDirectedPaths`'s preprocessing, etc. do and how they differ. The other Java demo modules (`JGraphXAdapterDemo`, `KnightTour`, etc.) remain as static graph-rendering examples in the source distribution; they're orthogonal to this page.

## Concrete proposal

- Replace `docs/visualizations.html` with the new page (renamed under the same path, or under `docs/visualizations/index.html` if a subdirectory is preferable).
- Keep a one-line note linking to the new page from the `docs/wiki/Demos-ShortestPathDemo.md` refresh that's already queued (the K-shortest bench grid update mentions the five algorithm variants — a "see live algorithm animation" pointer would help readers).
- Pure docs change: no Maven changes, no source-module changes, no algorithm code touched.
- The HTML is fully self-contained; no Jekyll dependency (uses a `.nojekyll` sentinel on the fork's Pages site).
- I will fix any image-path / link-relative issues that come up when the page is reparented under `docs/` instead of the fork's `visualizations/` subdirectory.

## Branch & numbers

Branch: `seilat/jgrapht:visualizations` — https://github.com/seilat/jgrapht/tree/visualizations

Algorithmic numbers reproduced in the visualization (matches the JMH grid from `KShortestPathBench`):

Grid 6×5 K=3:
| Variant                | Spur tasks ran | Node expansions |
|------------------------|---------------:|----------------:|
| Yen + Dijkstra         |             18 |             280 |
| Yen + A* (no BP)       |             18 |             146 |
| BPYen + Dijkstra       |             17 |             295 |
| BPYen + A* (full)      |              9 |             141 |

Path chain K=2 (the bounded-prune pathology):
| Variant                | Spur searches ran | Tasks skipped |
|------------------------|------------------:|--------------:|
| Yen + Dijkstra         | 8 (all dead-end)  |             0 |
| BPYen + A* (full)      |             **0** |             8 |

Layered DAG, budget=3, forward pruning (12 nodes, 18 edges):
| Variant                | Retained | Considered | Vertices marked | Dropped |
|------------------------|---------:|-----------:|----------------:|--------:|
| Backward BFS only      |       16 |         16 | 11 (backward)   |       0 |
| Forward + backward gate|       13 |         14 |  9 (forward)    |       1 |

Eppstein on Wiki 6-node K=3: 5 tree edges, 18 sidetrack `δ` labels, three walks `C → E → F → H` (cost 5), `C → D → E → F → H` (7), `C → E → D → E → F → H` (7 — with the `E → D → E` loop, demonstrating the walks-vs-simple-paths distinction).

## Questions for the dev list

1. Sign-off on the scope change — replacing the "render a JGraphT graph" page with an "animate a JGraphT algorithm" page?
2. Path preference — `docs/visualizations.html` (single file) vs `docs/visualizations/index.html` (subdirectory, easier to add assets later)?
3. Should the fork's optional self-host artefacts (`Dockerfile`, `nginx.conf`, `docker-compose.yml`, `vercel.json`) come along upstream, or stay on the fork? They're useful for anyone wanting to run the page offline, but they're not strictly needed for the gh-pages workflow that already serves `docs/`.
4. Other algorithms worth adding before merging? Easy candidates with interesting step-by-step animations: `BellmanFordShortestPath` relaxation rounds, `BidirectionalDijkstraShortestPath` meet-in-the-middle, `FloydWarshallShortestPaths` matrix updates. Happy to add any that the dev list thinks would help readers — or to land the current four (Yen / A* / forward pruning / Eppstein) first and follow up.

Thanks,
Shai

[John Sichi]

This is a very clear way to see how the algorithms work...nice!

However, given that JGraphT code is not actually being used for the visualization code, I'm thinking it might make more sense for these to be published separately from the main JGraphT repo, e.g. a jgrapht-algorithms-visualization on its own gh-pages site.  If you want to do that under the jgrapht org rather than under your own user, I can make you administrator for a corresponding repository.  Once that's published, we can link to it from the main JGraphT docs.  What do you think?

Then you can directly add new algos yourself over time, and accept contributions from others (including your pal Claude--seems like a very good fit for this kind of work, both for the initial creation and for the maintenance).  I suspect that eventually some refactoring will be required to take it beyond the initial self-contained dependency-free HTML+JS one-pager, although I certainly understand the reason for starting it off that way, given the dependabot purgatory we all suffer in.

--
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/82b0a01c-c37f-4919-a03a-1b1d07b71876n%40googlegroups.com.

[Shai Eilat]

Hi John,

Thanks for the feedback! I agree with your suggestion to host this as a separate repository under the jgrapht org. Setting up jgrapht-algorithms-visualization sounds like a great plan, and I’m happy to take on the administrator role for it.

Claude has indeed been very helpful with the execution and rapid testing of these ideas. Regarding the structure, I prefer keeping it as a single HTML file for now. It ensures simplicity and security, and as long as no external dependencies are needed, I’d like to keep the implementation as straightforward as possible.

Let me know once the repository is ready, and I’ll get started on the migration.

Thanks,

Shai

[John Sichi]

OK, I've created the repository (jgrapht-algo-visualization) and sent you an invite to be maintainer.  (If it turns out you need administrator access for some step, let me know.)  Once you get a github.io draft published, we can update DNS to make algo-visualization.jgrapht.org.

To view this discussion visit https://groups.google.com/d/msgid/jgrapht-dev/ca8ab782-958e-4db0-a7bf-f727c390e230n%40googlegroups.com.

[Shai Eilat]

Hi John,

Thanks for setting up Pages — the repo is now serving (build status
"built"), and I've added a `CNAME` file at the repo root claiming
`algo-visualization.jgrapht.org` so the site no longer inherits the
org-wide redirect to `old.jgrapht.org` (which I noticed isn't
resolving in DNS anymore — might be worth a separate look at the org
level, since every repo without its own CNAME is currently caught by
that stale redirect).

To finish the migration we just need the DNS record. The standard
GitHub Pages subdomain recipe is a CNAME:

  algo-visualization.jgrapht.org.   CNAME   jgrapht.github.io.

Once that record is in place, GitHub will validate the domain and
auto-issue an HTTPS cert (I can flip "Enforce HTTPS" in repo Settings
afterward). I'll then post a quick follow-up to jgrapht-dev pointing
at the live URL.

Thanks,
Shai

[John Sichi]

OK, I've updated DNS.

(The only reference I can find to old.jgrapht.org is the CNAME in https://github.com/jgrapht/jgrapht.github.com, which we set to archived back in 2018 when we set up the latest website.)

To view this discussion visit https://groups.google.com/d/msgid/jgrapht-dev/b0f25315-a84f-41ce-8d86-47b8887abd26n%40googlegroups.com.