Add articulation points and bridges detection
- Dominant language
- C++
- Stars
- 413
- Forks
- 67
- Avg merge
- 7h 24m
- Merged PRs (30d)
- 53
Description
## Summary
Graaf has no algorithm to find articulation points (cut vertices) or bridges (cut edges) — the standard DFS low-link algorithms used to determine which vertices/edges are single points of failure for graph connectivity.
## Current state
`include/graaflib/algorithm/` has no dedicated category for this, and a search for "articulation" or "bridge" across the codebase returns no matches (aside from unrelated documentation-link references). Interestingly, Tarjan's SCC implementation ([include/graaflib/algorithm/strongly_connected_components/tarjan.tpp](../blob/main/include/graaflib/algorithm/strongly_connected_components/tarjan.tpp)) already computes low-link values via DFS — articulation points and bridges use a closely related low-link technique, so there's a natural implementation path that reuses that pattern.
## Why this matters
Articulation points and bridges answer a question that comes up constantly in applied graph use cases: "which single node/link, if it fails, disconnects the network?" This is core to network-reliability analysis, infrastructure planning, and dependency-graph analysis (e.g. finding single points of failure in a service dependency graph). It's a standard, well-understood O(V+E) algorithm family that's conspicuously absent given the library already implements the more complex Tarjan's SCC algorithm that uses the same underlying technique.
## Suggested resolution
- Implement a DFS low-link-based algorithm to find all articulation points, and a companion (or combined) algorithm to find all bridges, for undirected graphs.
- Follow the existing `algorithm//.h` + `.tpp` structure (e.g. `algorithm/articulation_points/` and/or `algorithm/bridges/`, or a shared `algorithm/connectivity/` category).
- Add corresponding documentation under `docs/docs/algorithms/`, including complexity.
## Acceptance criteria
- [ ] Articulation point detection is implemented for undirected graphs.
- [ ] Bridge detection is implemented for undirected graphs.
- [ ] Documentation added under `docs/docs/algorithms/`, including time/space complexity.
- [ ] Unit tests cover graphs with no articulation points/bridges (e.g. a cycle), a single point of failure (e.g. a tree), and disconnected graphs.
Contributor guide
Research direction
Review the existing Tarjan's SCC implementation in include/graaflib/algorithm/strongly_connected_components/tarjan.tpp to understand the low-link DFS pattern. The new algorithms should be placed in a new directory like include/graaflib/algorithm/articulation_points/ or include/graaflib/algorithm/connectivity/. Write unit tests for graphs with no articulation points (a cycle), a single point of failure (a tree), and disconnected graphs. Documentation should be added to docs/docs/algorithms/.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- cpp
- Issue type
- Feature
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Active
- Clarity
- Clearly specified
- Newbie friendliness
- 55/100