feat: Add Johnson's algorithm #741

starovoid · 2025-02-17T21:48:28Z

Brief

Add Johnson algorithm for all pairs shortest path problem.

pub fn johnson<G, F, K>(
    graph: G,
    mut edge_cost: F,
) -> Result<HashMap<(G::NodeId, G::NodeId), K>, NegativeCycle>
where
    G: IntoEdges + IntoNodeIdentifiers + NodeIndexable + Visitable,
    G::NodeId: Eq + Hash,
    F: FnMut(G::EdgeRef) -> K,
    K: BoundedMeasure + Copy + Sub<K, Output = K>,

About algorithm & implementation

Johnson's algorithm is based on Dijkstra's algorithm, calling it for each vertex after some preparation using SPFA.
In this way we can find all pair shortest paths in O(VD + VE) time (D is the Dijksta's time complexity).

In the current implementation, we have a time complexity O(VElog(V) + V^2log(V)), which is preferable for non-dense graphs, compared to the Floyd-Warshall algorithm.

Instead of SPFA, it would also be possible to use the existing bellman_ford implementation, but SPFA usage additionally speeds up the algorithm on sparse graphs, and there is an unconfirmed estimate that SPFA works on average in O(E) time.

Becnhmarks

I have conducted small comparative tests that confirm the statement that Johnson's algorithm is preferable on sparse graphs (almost five times faster than floyd_warshall), but it also naturally loses on dense graphs.

test johnson_dense_1000_nodes  ... bench: 1,169,255,997.40 ns/iter (+/- 7,208,144.98)
test johnson_dense_100_nodes   ... bench:   1,777,834.38 ns/iter (+/- 24,188.31)
test johnson_sparse_1000_nodes ... bench:  86,516,820.50 ns/iter (+/- 1,082,174.18)
test johnson_sparse_100_nodes  ... bench:     778,894.19 ns/iter (+/- 14,603.94)

test floyd_warshall_dense_1000_nodes  ... bench: 544,423,954.20 ns/iter (+/- 7,272,191.85)
test floyd_warshall_dense_100_nodes   ... bench:     568,021.70 ns/iter (+/- 12,867.89)
test floyd_warshall_sparse_1000_nodes ... bench: 495,226,815.90 ns/iter (+/- 8,736,234.74)
test floyd_warshall_sparse_100_nodes  ... bench:     529,623.65 ns/iter (+/- 14,083.83)

The benchmark code has also been added to this PR in order to be able to compare the performance of certain algorithms in the future.

`parallel_johnson`

A version of the algorithm that parallels dijkstra calls is available under the rayon feature.

pub fn parallel_johnson<G, F, K>(
    graph: G,
    mut edge_cost: F,
) -> Result<HashMap<(G::NodeId, G::NodeId), K>, NegativeCycle>
where
    G: IntoEdges + IntoNodeIdentifiers + NodeIndexable + Visitable + Sync,
    G::NodeId: Eq + Hash + Send,
    F: Fn(G::EdgeRef) -> K + Sync,
    K: BoundedMeasure + Copy + Sub<K, Output = K> + Send + Sync,

The benchmarks show the following performance on PC with Ryzen 9 7950X:

test johnson_dense_1000_nodes           ... bench: 1,177,432,008.20 ns/iter (+/- 11,077,709.38)
test johnson_dense_100_nodes            ... bench:   1,714,581.45 ns/iter (+/- 31,400.66)
test johnson_sparse_1000_nodes          ... bench:  78,071,539.40 ns/iter (+/- 2,063,005.61)
test johnson_sparse_100_nodes           ... bench:     660,780.69 ns/iter (+/- 15,389.23)
test parallel_johnson_dense_1000_nodes  ... bench:  68,611,940.20 ns/iter (+/- 1,782,308.55)
test parallel_johnson_dense_100_nodes   ... bench:     258,762.17 ns/iter (+/- 16,887.11)
test parallel_johnson_sparse_1000_nodes ... bench:  14,309,925.60 ns/iter (+/- 1,388,024.20)
test parallel_johnson_sparse_100_nodes  ... bench:     259,247.53 ns/iter (+/- 15,763.51)

and

test johnson_dense_1000_nodes           ... bench: 1,931,386,001.60 ns/iter (+/- 30,692,353.78)
test johnson_sparse_1000_nodes          ... bench: 155,685,943.60 ns/iter (+/- 104,165,471.95)
test parallel_johnson_dense_1000_nodes  ... bench: 246,817,415.40 ns/iter (+/- 7,077,236.51)
test parallel_johnson_sparse_1000_nodes ... bench:  34,137,779.80 ns/iter (+/- 4,018,118.69)

on laptop with 12th Intel(R) i7-12700H

RaoulLuque

Seems like a useful addition to Petgraph :)

Was wondering a few things:

I saw that this is similar with Floyd Warshall, but why do we not return the actual paths that are computed in some way? Of course changing this for Floyd Warshall would be an API change, but we could do it from the start with Johnson's?

Probably this would be a performance drawback, but would it maybe be possible to discard the "path map" immediately as a user in which case the compiler might optimize the performance slowdown away?
I.e. something like let (res, _) = johnson(...).unwrap(), where the _ would be throwing away the "path map" returned by johnson. Not sure if this works, especially with the Result return type, but might be worth looking into 🤔

benches/floyd_warshall.rs

benches/johnson.rs

RaoulLuque · 2025-05-20T19:53:39Z

src/algo/floyd_warshall.rs

+/// **Note**: If the graph is sparse (the number of edges is quite small),
+/// consider using the [`johnson`](fn@crate::algo::johnson), which is likely to show better performance.
+///


Judging by the benchmarks, parallel Johnson might be worth considering instead of Floyd Warshall, even on dense graphs. So maybe add a line about that as well?

This would be a pretty bold statement, since in addition to the absolute operating time, resource consumption is often also taken into account, which will be much more economical when using floyd_warshall for dense graphs.

You are definitely right that one has to take into account the resource consumption, but it still might be interesting to users, to know that parallelized johnson might run faster (not necessarily more efficient) than normal floyd warshall, even on general graphs. But I also see your point, so feel free to include a comment about the runtime/resource trade-off or not 👍

src/algo/johnson.rs

starovoid · 2025-05-20T20:33:37Z

but why do we not return the actual paths that are computed in some way? Of course changing this for Floyd Warshall would be an API change, but we could do it from the start with Johnson's?

Because it will also require changing/adding a new version of dijkstra, which is beyond the scope of a single PR.

Secondly, significant refactoring and generalization of shortest path algorithms is expected in the future, and then I hope we will be able to develop a uniform API for both versions of all algorithms without paying extra for unused functionality. Some work has already been done previously in the next branch, and I expect it to resume in the coming months.

RaoulLuque · 2025-05-21T07:16:13Z

Because it will also require changing/adding a new version of dijkstra, which is beyond the scope of a single PR.

Secondly, significant refactoring and generalization of shortest path algorithms is expected in the future, and then I hope we will be able to develop a uniform API for both versions of all algorithms without paying extra for unused functionality. Some work has already been done previously in the next branch, and I expect it to resume in the coming months.

Oh, I didn't see that dijkstra's API didn't support that either. Of course one could change the actual functionality behind the dijkstra API and expose a new one also returning the paths and let the old one simply call the new one throwing away the paths. But I guess in that case it would make sense to wait for these changes for the next branch. Are there any time estimates on when changes from that branch might land in main?

starovoid · 2025-05-21T07:26:11Z

Are there any time estimates on when changes from that branch might land in main?

Work on next is awaiting the author's return (1-2 months), then I plan to join there when petgraph 0.8.3 released. But it's difficult to give any estimates - there are a lot of tasks there.

RaoulLuque · 2025-05-21T16:53:44Z

LGTM now :)

## 🤖 New release * `petgraph`: 0.8.1 -> 0.8.2 (✓ API compatible changes) <details><summary>Changelog</summary> <blockquote> ## [0.8.2](https://github.com/petgraph/petgraph/compare/petgraph@v0.8.1...petgraph@v0.8.2) - 2025-06-06 ### Bug Fixes - Ford Fulkerson sometimes Panics on StableGraphs ([#793](#793)) - Run Maximal Cliques Quickcheck only on Digraphs which are symmetrical ([#800](#800)) - Run Steiner Tree Quickcheck on the connected components to properly support disconnected graphs ([#801](#801)) - Quickcheck random01 function only outputs 0 ([#798](#798)) ### Documentation - Specify that Acyclic::try_udpate_edge may add an edge ([#770](#770)) - Update remove_node doc comment in graphmap.rs ([#663](#663)) - Add examples to minimum spanning tree functions ([#808](#808)) - Minimal typo fix in comments ([#803](#803)) - Update docs.rs ([#807](#807)) - Add note about `StableGraph::edge_indices` behaviour ([#812](#812)) - Clarification of references to nodes and V (refresh #358) ([#814](#814)) - Fix link and mention Dfs and Bfs as special case in examples ([#816](#816)) - Unify algo docs ([#815](#815)) ### New Features - *(parser)* allow parsing graphs from Dot/Graphviz files ([#653](#653)) - Implement `DataMap` for `GraphMap` graphs ([#776](#776)) - Add Johnson's algorithm ([#741](#741)) - Add algorithm to find bridge edges ([#590](#590)) ### Performance - Reuse queue allocation in `maximum_matching` main loop ([#817](#817)) ### Refactor - Fix new clippy warnings ([#791](#791)) </blockquote> </details> --- This PR was generated with [release-plz](https://github.com/release-plz/release-plz/). --------- Co-authored-by: github-actions[bot] <41898282+github-actions[bot]@users.noreply.github.com> Co-authored-by: starovoid <prototyperailgun@gmail.com>

## 🤖 New release * `petgraph`: 0.8.1 -> 0.8.2 (✓ API compatible changes) <details><summary>Changelog</summary> <blockquote> ## [0.8.2](https://github.com/petgraph/petgraph/compare/petgraph@v0.8.1...petgraph@v0.8.2) - 2025-06-06 ### Bug Fixes - Ford Fulkerson sometimes Panics on StableGraphs ([petgraph#793](petgraph#793)) - Run Maximal Cliques Quickcheck only on Digraphs which are symmetrical ([petgraph#800](petgraph#800)) - Run Steiner Tree Quickcheck on the connected components to properly support disconnected graphs ([petgraph#801](petgraph#801)) - Quickcheck random01 function only outputs 0 ([petgraph#798](petgraph#798)) ### Documentation - Specify that Acyclic::try_udpate_edge may add an edge ([petgraph#770](petgraph#770)) - Update remove_node doc comment in graphmap.rs ([petgraph#663](petgraph#663)) - Add examples to minimum spanning tree functions ([petgraph#808](petgraph#808)) - Minimal typo fix in comments ([petgraph#803](petgraph#803)) - Update docs.rs ([petgraph#807](petgraph#807)) - Add note about `StableGraph::edge_indices` behaviour ([petgraph#812](petgraph#812)) - Clarification of references to nodes and V (refresh petgraph#358) ([petgraph#814](petgraph#814)) - Fix link and mention Dfs and Bfs as special case in examples ([petgraph#816](petgraph#816)) - Unify algo docs ([petgraph#815](petgraph#815)) ### New Features - *(parser)* allow parsing graphs from Dot/Graphviz files ([petgraph#653](petgraph#653)) - Implement `DataMap` for `GraphMap` graphs ([petgraph#776](petgraph#776)) - Add Johnson's algorithm ([petgraph#741](petgraph#741)) - Add algorithm to find bridge edges ([petgraph#590](petgraph#590)) ### Performance - Reuse queue allocation in `maximum_matching` main loop ([petgraph#817](petgraph#817)) ### Refactor - Fix new clippy warnings ([petgraph#791](petgraph#791)) </blockquote> </details> --- This PR was generated with [release-plz](https://github.com/release-plz/release-plz/). --------- Co-authored-by: github-actions[bot] <41898282+github-actions[bot]@users.noreply.github.com> Co-authored-by: starovoid <prototyperailgun@gmail.com>

starovoid self-assigned this Mar 20, 2025

starovoid added this to the 0.8.1 milestone Mar 21, 2025

starovoid added the C-new-algorithm Category: A feature request for a new graph algorithm label Mar 28, 2025

starovoid force-pushed the johnson branch from bd248e6 to 0928db4 Compare May 20, 2025 11:55

starovoid marked this pull request as ready for review May 20, 2025 11:58

RaoulLuque reviewed May 20, 2025

View reviewed changes

starovoid added 8 commits May 21, 2025 09:53

Add johnson's algorithm implementation

35e5fd9

johnson benches, compare with floyd_warshall

20ef232

Add johnson quickcheck

e1671ee

Parallel johnson

5f61d86

Fix quickcheck & docs

12d7252

Point to 'johnson' algorithms in docs

1b9b009

Support no_std in johnson impl

42b4bff

Satisfy lints

760b7ea

starovoid force-pushed the johnson branch from 54caca9 to 760b7ea Compare May 21, 2025 06:53

Unify fw & johnson benchmarks code

2b6d97c

Note about alternatives in doc

b8e80f9

starovoid added this pull request to the merge queue May 21, 2025

Merged via the queue into petgraph:master with commit dac1ad3 May 21, 2025
10 checks passed

starovoid deleted the johnson branch May 21, 2025 20:14

github-actions bot mentioned this pull request May 21, 2025

chore: release v0.8.2 #768

Merged

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

feat: Add Johnson's algorithm #741

feat: Add Johnson's algorithm #741

Uh oh!

starovoid commented Feb 17, 2025 •

edited

Loading

Uh oh!

RaoulLuque left a comment

Uh oh!

Uh oh!

Uh oh!

RaoulLuque May 20, 2025

Uh oh!

starovoid May 21, 2025

Uh oh!

RaoulLuque May 21, 2025

Uh oh!

Uh oh!

starovoid commented May 20, 2025

Uh oh!

RaoulLuque commented May 21, 2025 •

edited

Loading

Uh oh!

starovoid commented May 21, 2025

Uh oh!

RaoulLuque commented May 21, 2025 •

edited

Loading

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

2 participants

feat: Add Johnson's algorithm #741

feat: Add Johnson's algorithm #741

Uh oh!

Conversation

starovoid commented Feb 17, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Brief

About algorithm & implementation

Becnhmarks

parallel_johnson

Uh oh!

RaoulLuque left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

RaoulLuque May 20, 2025

Choose a reason for hiding this comment

Uh oh!

starovoid May 21, 2025

Choose a reason for hiding this comment

Uh oh!

RaoulLuque May 21, 2025

Choose a reason for hiding this comment

Uh oh!

Uh oh!

starovoid commented May 20, 2025

Uh oh!

RaoulLuque commented May 21, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

starovoid commented May 21, 2025

Uh oh!

RaoulLuque commented May 21, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

2 participants

starovoid commented Feb 17, 2025 •

edited

Loading

`parallel_johnson`

RaoulLuque commented May 21, 2025 •

edited

Loading

RaoulLuque commented May 21, 2025 •

edited

Loading