request: toposort into levels

Open
#240 2 comments 3 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Assessment

Difficulty
4/5
Estimated time
3-5 days
Newbie friendliness
48/100
Issue type
Feature
Clarity
Mostly clear
Activity status
Quiet
Tech stack
cpp
Domain
data

Research direction

Start at the topological_sort entry point and inspect the existing implementation and tests to understand how ordering results are represented. Define how levels should be exposed, then add coverage for the example dependency graph so the output is [z], [b, c], [a].

Written by the indexing model from the issue text.

Description

algorithm

I don't think it's currently possible to get each "level" fromtopological_sort (where a level contains the set of vertices with no unfinished dependencies e.g. if a depends on b, b depends on z, and c depends on z, then the levels are [z], [b, c], [a]).

I think this would be a helpful feature. I'd be happy to write a PR if others are interested.

Dominant language
C++
Stars
395
Forks
239
Avg merge
18h 50m
Merged PRs (30d)
20

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

More from boostorg/graph

All issues in boostorg/graph

Similar issues

More C++ issues

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.