Improve disjoint_set data structure
Nobody has claimed this yet.
Assessment
- Difficulty
- 5/5
- Estimated time
- Over a week
- Newbie friendliness
- 30/100
- Issue type
- Feature
- Clarity
- Needs clarification
- Activity status
- Quiet
- Tech stack
- cpp
- Domain
- performance
Research direction
Start by inspecting the disjoint-set implementation in the pending directory and compare it with the modern implementations referenced by the proposal. Review the linked Wikipedia description and identify a concrete performance change, API, and evaluation plan; the work is complete when the proposal is specific enough to implement and review.
Written by the indexing model from the issue text.
Description
Before filing
- I searched the existing issues 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
- 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?
- 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.
- Dominant language
- C++
- Stars
- 395
- Forks
- 239
- Avg merge
- 18h 50m
- Merged PRs (30d)
- 20
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
More from boostorg/graph
-
beginner friendly
Difficulty 2/5 1-3 hours Newbie friendliness 76/100
-
algorithm beginner friendly priority: high
Difficulty 2/5 1-3 hours Newbie friendliness 68/100
-
priority: high warning
-
algorithm
boostorg/graph#493 · 22 comments · 1 reaction · 2 assignees ·
-
api
Difficulty 4/5 3-5 days Newbie friendliness 48/100
Similar issues
-
Difficulty 1/5 Under an hour Newbie friendliness 90/100
AXERA-TECH/ax-llm#77 ·
-
Difficulty 1/5 Under an hour Newbie friendliness 90/100
games-on-whales/wolf#509 ·
-
Difficulty 2/5 1-3 hours Newbie friendliness 74/100
-
bug-unconfirmed
Difficulty 2/5 1-3 hours Newbie friendliness 76/100
-
Difficulty 2/5 1-3 hours Newbie friendliness 74/100
NVIDIA/cuda-samples#453 ·