Skip to content

feat: Connectivity Algorithms #738

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Open
BryanCruz wants to merge 11 commits into
base: master
Choose a base branch
from
Open

feat: Connectivity Algorithms #738

BryanCruz wants to merge 11 commits into from

Conversation

@BryanCruz
Copy link
Contributor

@BryanCruz BryanCruz commented Feb 16, 2025 •
edited
Loading

Add Connectivity Algorithms

Algorithms:

  • Find graph articulation points (also known as cut vertices or separating vertices)
  • Find graph bridges (also known as Cut Edges or Cut Arcs)
  • Find graph biconnected components (also known as 2-connected components)
  • Find graph 2-edge-connected components

References:

The algorithm to find Bridges was inspired by the following Program from the book Algorithms in C, Third Edition, Part 5, by Robert Sedgewick, adapted to Rust and to use Petgraph traits, also transformed into an iterative algorithm instead of a recursive one.

The other connectivity algorithms in the PR are adaptations of it.

@BryanCruz BryanCruz marked this pull request as ready for review February 17, 2025 02:53
@BryanCruz BryanCruz changed the title Connectivity Algorithms feat: Connectivity Algorithms Apr 6, 2025
@starovoid starovoid mentioned this pull request May 17, 2025
Open
@RaoulLuque
Copy link
Member

RaoulLuque commented May 18, 2025

Regarding the bridge finding algorithm, there is another PR, which implemented such an algorithm.

I compared the performance of this implementation to the one suggested in the other PR, and the other implementation seems to be 2-7 times faster.

The benchmark setup can be found here. I just added a benches/bridges.rs file and reused most of the benchmarks you used, while also adding one that the other PR used.

The results from this implementation are:

bridges_bench           ... bench:     517,470.31 ns/iter (+/- 61,815.38)
bridges_search_2000n    ... bench:  44,879,972.10 ns/iter (+/- 3,265,361.30)
bridges_search_full     ... bench:       8,305.99 ns/iter (+/- 443.49)
bridges_search_petersen ... bench:       4,739.99 ns/iter (+/- 212.79)
bridges_search_praust   ... bench:      11,064.40 ns/iter (+/- 677.18)

While the results of the implementation from the other PR are:

bridges_bench           ... bench:      76,177.97 ns/iter (+/- 6,825.55)
bridges_search_2000n    ... bench:  19,864,410.00 ns/iter (+/- 5,565,975.53)
bridges_search_full     ... bench:       1,948.67 ns/iter (+/- 60.93)
bridges_search_petersen ... bench:         964.86 ns/iter (+/- 100.76)
bridges_search_praust   ... bench:       2,047.10 ns/iter (+/- 176.95)

Note that in order to be able to run the benchmarks with the other PR, I had to rebase. The setup of the same benches/bridges.rs file can be found here.

@RaoulLuque RaoulLuque mentioned this pull request Jun 21, 2025
Closed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

No reviews

Assignees

No one assigned

Labels

None yet

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

2 participants

@BryanCruz @RaoulLuque