bobluppes / bobluppes/graaf

Expose union-find (disjoint-set) as a reusable public data structure

Open
#333 0 comments 0 reactions 0 assignees View on GitHub
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

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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.