bobluppes / bobluppes/graaf

Add articulation points and bridges detection

Open
#332 0 comments 0 reactions 0 assignees View on GitHub
enhancement good first issue help wanted
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.