Improve disjoint_set data structure
- Dominant language
- C++
- Stars
- 392
- Forks
- 239
- Avg merge
- 1d 11m
- Merged PRs (30d)
- 20
Description
### Before filing
- [x] I searched the [existing issues](https://github.com/boostorg/graph/issues?q=is%3Aissue) and did not find a duplicate.
- [ ] This is a concrete proposal, not an open-ended design question.
### Kind of addition
- [ ] New algorithm
- [ ] New data structure
- [ ] New property map or utility
- [ ] New I/O format reader or writer
- [ ] Extension to an existing component
- [x] Performance improvement
- [ ] Other (specify below)
### Motivation
A user requested it to be more "competitive" and "practical."
### Proposed addition
Not sure yet. Need to compare with existing modern implementations first.
### Relation to existing Boost.Graph components
It's hiding in the `pending` directory.
### Prior art
https://en.wikipedia.org/wiki/Disjoint-set_data_structure?wprov=sfla1
Will add more as they become relevant.
- [ ] Reference paper or textbook (cite below)
- [ ] Implementation in another library (link below)
- [ ] None / original idea
References:
### Are you willing to contribute?
- [x] I'd like to submit the implementation as a pull request.
- [ ] I can help with review or testing, but not the implementation.
- [ ] I'm only proposing the idea.
Contributor guide
Assessment
This issue has not been assessed yet.