boostorg / boostorg/graph

Improve disjoint_set data structure

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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.