Add articulation points implementation #681

daehiff · 2024-11-24T12:56:58Z

Motivation

This pull request adds a function to compute articulation points in a graph using Tarjan's algorithm, implemented with an iterative approach. Articulation points are nodes whose removal increases the number of connected components in the graph.
Currently, petgraph lacks an implementation for this functionality. This makes it impossible to for instance determine if a vertex of a graph is cutting with petgraph.

Note: This approach is not a direct replication of existing implementations (e.g., [here](https://www.geeksforgeeks.org/tarjan-algorithm-find-strongly-connected-components/)), as it avoids recursion entirely.

Runtime

Tarjan's algorithm is an efficient solution to this problem, with a time complexity of (O(V + E)), making it well-suited for large graphs.

src/algo/articulation_points.rs

starovoid · 2024-11-24T20:42:52Z

Hi, great job!

But I think it will be better the implementation using stack instead of recursion. Just like it was with the bridge edges search algorithm in PR #590.

Practice has shown that a recursive implementation can face the problem of stack overflow.

daehiff · 2024-11-25T00:03:23Z

Hey, thanks for the quick reply!

That is a good suggestion! I'll update the PR.
Do you have any other requirements (testing concepts ect.), we should be aware of?

starovoid · 2024-11-25T07:20:04Z

Yes, I have two thoughts

Picky testing

I think it would be a good idea to write some randomized tests.

In general, the algorithm may look like this:

Creating a random graph on a random number of vertices;
Find the articulation points;
We remove the found vertices from the graph one by one and check that each time the number of connectivity components increases;

Later, when version 0.7.0 is released, I plan to open a PR with the addition of a randomized test for bridges implementation too.

Add bench

petgraph has a good tradition of adding performance tests for new algorithms.
I think it would be logical to add a benchmark identical to #590, since the algorithms are similar.

daehiff · 2024-12-02T23:46:30Z

Alright, sorry the late reply.

I have added:

A benchmark similar to bridges
A few more tests and some other graph structures
A quickcheck test for random graphs

Anything further or do you have other comments on the implementation?

starovoid · 2024-12-03T08:43:46Z

I think all is top class now.
It remains to wait for the maintainers' review.

XVilka · 2024-12-23T12:41:45Z

@daehiff please update the PR description to describe the reasons for this implementation, etc.

daehiff · 2024-12-23T15:58:49Z

@XVilka all checks have been passed and there has been some review comments.

Is there a timeline or a ways how we can get in touch? It is kind of hard todo a contribution without knowing contribution guidelines ect.

I asked @ABorgna via discord, but no response on that end.

XVilka · 2024-12-23T16:10:41Z

@XVilka all checks have been passed and there has been some review comments.

Is there a timeline or a ways how we can get in touch? It is kind of hard todo a contribution without knowing contribution guidelines ect.

I asked @ABorgna via discord, but no response on that end.

I forgot we have a DIscord. Just joined it.

ABorgna

Nice! I mostly only have nitpicks.

src/algo/articulation_points.rs

tests/articulation_points.rs

src/algo/articulation_points.rs

ABorgna · 2025-02-01T12:49:35Z

src/algo/articulation_points.rs

+fn _dfs<G>(
+    g: &G,
+    target_node: usize,
+    visited: &mut Vec<bool>,


Vec<bool> uses one byte per element, since it needs to support arbitrary references.

Use a FixedBitSet instead.

ABorgna · 2025-02-01T12:51:38Z

src/algo/articulation_points.rs

+            _dfs(
+                &g,
+                node_id,
+                &mut visited,


nitpick: This could be an auxiliary state struct.

Added a struct ArticulationPointTracker, I am kindof unhappy with the naming tho.

I'd normally call it "Context", but it's private so it doesn't really matter.

Signed-off-by: David Winderl <winderl13@gmail.com>

Co-authored-by: Agustín Borgna <agustinborgna@gmail.com>

Signed-off-by: daehiff <winderl13@gmail.com>

daehiff changed the title ~~Art points~~ Add articulation points implementation Nov 24, 2024

daehiff force-pushed the art-points branch from 5af3f44 to d5bca3e Compare November 24, 2024 13:34

daehiff commented Nov 24, 2024

View reviewed changes

src/algo/articulation_points.rs Outdated Show resolved Hide resolved

daehiff force-pushed the art-points branch 2 times, most recently from 47cc1cd to 3fbc423 Compare December 2, 2024 23:44

daehiff force-pushed the art-points branch from 32ba9f9 to 820ef2a Compare December 20, 2024 13:46

ABorgna reviewed Feb 1, 2025

View reviewed changes

y-richie-y and others added 5 commits February 1, 2025 14:09

Implement algorithm for articulation points

ecc1132

Add benchmark for articulation point

3f3fdf9

Update to stack based implementation

1963580

Signed-off-by: David Winderl <winderl13@gmail.com>

Fx cargo fmt issues

dea936f

Signed-off-by: David Winderl <winderl13@gmail.com>

Add more tests for articulation points

00593f5

Signed-off-by: David Winderl <winderl13@gmail.com>

daehiff force-pushed the art-points branch from 4a8ccb3 to 00593f5 Compare February 1, 2025 13:14

daehiff and others added 5 commits February 1, 2025 14:14

Update src/algo/articulation_points.rs

3298a6f

Co-authored-by: Agustín Borgna <agustinborgna@gmail.com>

Update src/algo/articulation_points.rs

6e99927

Co-authored-by: Agustín Borgna <agustinborgna@gmail.com>

Update tests/articulation_points.rs

bdfc413

Co-authored-by: Agustín Borgna <agustinborgna@gmail.com>

Update tests/articulation_points.rs

417f5ae

Co-authored-by: Agustín Borgna <agustinborgna@gmail.com>

Fix PR: Add auxiliary constant for dfs

e964756

Signed-off-by: daehiff <winderl13@gmail.com>

daehiff force-pushed the art-points branch from e98b661 to e964756 Compare February 1, 2025 13:37

daehiff added 3 commits February 1, 2025 14:38

Fix PR: fix formattig issue

2bafa31

Signed-off-by: daehiff <winderl13@gmail.com>

Fix PR: Replace vec<bool> with FixedBitSet

34a2437

Signed-off-by: daehiff <winderl13@gmail.com>

Fix PR: Smaller other fixes

fe3e644

Signed-off-by: daehiff <winderl13@gmail.com>

Fix fmt

031e2da

Signed-off-by: daehiff <winderl13@gmail.com>

ABorgna approved these changes Feb 1, 2025

View reviewed changes

ABorgna merged commit ee68efc into petgraph:master Feb 1, 2025
7 checks passed

This was referenced Apr 5, 2025

chore: release v0.8.1 #762

Merged

chore: release v0.8.2 starovoid/petgraph#1

Draft

Add articulation points implementation #681

Add articulation points implementation #681

Uh oh!

Conversation

daehiff commented Nov 24, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Motivation

Runtime

Uh oh!

Uh oh!

starovoid commented Nov 24, 2024

Uh oh!

daehiff commented Nov 25, 2024

Uh oh!

starovoid commented Nov 25, 2024

Picky testing

Add bench

Uh oh!

daehiff commented Dec 2, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

starovoid commented Dec 3, 2024

Uh oh!

XVilka commented Dec 23, 2024

Uh oh!

daehiff commented Dec 23, 2024

Uh oh!

XVilka commented Dec 23, 2024

Uh oh!

ABorgna left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

ABorgna Feb 1, 2025

Choose a reason for hiding this comment

Uh oh!

ABorgna Feb 1, 2025

Choose a reason for hiding this comment

Uh oh!

daehiff Feb 1, 2025

Choose a reason for hiding this comment

Uh oh!

ABorgna Feb 1, 2025

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

5 participants

daehiff commented Nov 24, 2024 •

edited

Loading

daehiff commented Dec 2, 2024 •

edited

Loading