Expose union-find (disjoint-set) as a reusable public data structure
- Dominant language
- C++
- Stars
- 413
- Forks
- 67
- Avg merge
- 7h 24m
- Merged PRs (30d)
- 53
Description
## Summary
Graaf has a working path-compressed union-find (disjoint-set) implementation, but it's private to Kruskal's algorithm and unavailable for reuse elsewhere.
## Current state
The union-find logic lives in the `graaf::detail` namespace inside [include/graaflib/algorithm/minimum_spanning_tree/kruskal.tpp](../blob/main/include/graaflib/algorithm/minimum_spanning_tree/kruskal.tpp) (`do_find_set()` / `do_union()`, operating on a plain `std::unordered_map` parent map with path compression). It is not declared in any public header, and there is no standalone `union_find`/`disjoint_set` class anywhere in `include/graaflib/`.
## Why this matters
Union-find is a general-purpose, reusable data structure with applications well beyond Kruskal's MST: fast connectivity queries on undirected graphs, cycle detection in undirected graphs, incremental connectivity as edges are added, and it would also be the natural building block for implementing Kruskal-style variants (see the related Borůvka's algorithm gap). Right now, anyone who wants this functionality either has to reimplement it themselves or reach past the library's public API into `detail::do_find_set`, which isn't a supported entry point.
## Suggested resolution
- Extract the existing logic into a standalone `graaf::union_find` (or `disjoint_set`) class under `include/graaflib/`, with a small public API (`find(x)`, `union_sets(x, y)`, `connected(x, y)`), keeping path compression and union by rank/size.
- Refactor `kruskal.tpp` to use the new public class instead of its private `detail` helpers.
- Add unit tests and a documentation page for the new data structure, following the existing `core-class-template.md` issue conventions.
## Acceptance criteria
- [ ] A public, reusable `union_find`/`disjoint_set` class exists under `include/graaflib/`.
- [ ] Kruskal's algorithm is refactored to use it instead of its private duplicate implementation.
- [ ] The class has its own unit tests and documentation.
Contributor guide
Research direction
The existing union-find logic is in include/graaflib/algorithm/minimum_spanning_tree/kruskal.tpp, in the detail namespace. Start by examining the do_find_set and do_union functions. Create a new public header file under include/graaflib/ for the union_find class, implementing find, union_sets, and connected methods. Refactor kruskal.tpp to use this new class. Write unit tests following the project's existing test patterns and update documentation.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- cpp
- Domain
- backend-api-design
- Issue type
- Feature
- Difficulty
- 3/5
- Estimated time
- 1-2 days
- Activity status
- Active
- Clarity
- Clearly specified
- Newbie friendliness
- 65/100