bobluppes / bobluppes/graaf

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

オープン
#333 コメント 0 件 リアクション 0 件 担当者 0 名 GitHub で見る
主要言語
C++
スター
413
フォーク
67
平均マージ
7時間 24分
マージ済み PR(30日)
53

説明

## 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.

コントリビューションガイド

コントリビューションガイドを開く

調査の方向性

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.

索引モデルが issue の本文から書いたものです。

評価

技術スタック
cpp
領域
backend-api-design
issue の種類
機能追加
難易度
3/5
見積もり時間
1〜2日
活発さ
活発
明瞭さ
明確に書かれている
初心者へのやさしさ
65/100

新しい issue をメールで受け取る

初心者向けの GitHub issue を短くまとめたダイジェスト。