Algorithms for finding bridges and articulation points. #473
Conversation
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Two algorithms are implemented, each of which expects the argument to be a simple undirected graph. In addition to quickcheck, tests have also been written to verify the correctness of the algorithm with all types of graphs.
|
Hi. Why was the pull request closed? I don't see any conversation about it. |
pragmaticTNT
added a commit
to pragmaticTNT/petgraph
that referenced
this pull request
Oct 7, 2023
Derived from petgraph#473 (written by @starovoid).
milkcask
pushed a commit
to milkcask/petgraph
that referenced
this pull request
Sep 13, 2024
Derived from petgraph#473 (written by @starovoid).
github-merge-queue bot
pushed a commit
that referenced
this pull request
May 23, 2025
Derived from #473 (written by @starovoid). Here's a list of changes that we (@gmorenz and myself) made: - Used iteration instead of recursion; with the original version we hit a stack overflow. - Tried to make variable names self documenting (e.g. `fup` to `earliest-backedge`) - Change the output type from `Vec<G::NodeId, G::NodeId)>` to `impl Iterator<Item = G::EdgeRef>` The original code also had an algorithm to find articulation points (node variant of bridge edges). To keep the pull request small we only added the bridge algorithm. We would be happy to include the other algorithm in another pull request. As a result we named the module `bridges` instead of `bridges_and_ap`, we think this is probably a better (more succinct) name anyways. --------- Co-authored-by: xylqn7 <xylqn7@morel.SafeAI-Guest.local> Co-authored-by: xylqn7 <xylqn7@morel.lan>
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
2 participants
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
Two algorithms are implemented: for finding bridges and for finding points of articulation are implemented, each of which expects the argument to be a simple undirected graph. The algorithms are tested with all types of graphs.