Add Kahn's algorithm for topological sorting
- Dominant language
- C++
- Stars
- 413
- Forks
- 67
- Avg merge
- 7h 24m
- Merged PRs (30d)
- 53
Description
## Summary
Graaf only implements DFS-based topological sorting. Kahn's algorithm (the BFS/in-degree-based alternative) is not implemented.
## Current state
`include/graaflib/algorithm/topological_sorting/` contains only `dfs_topological_sorting.h`/`.tpp`. There is a related historical request, [#114 "[ALGO] Kahn's Algorithm"](../issues/114), which was closed without being implemented (closed due to inactivity, not as "won't do").
## Why this matters
Kahn's algorithm is the standard alternative to DFS-based topological sorting, and it has properties the DFS version doesn't: it naturally detects cycles as a side effect (if not all vertices are output, the graph has a cycle), it processes vertices in in-degree order rather than via recursion (avoiding recursion-depth concerns on very large or deep graphs), and it more naturally supports "level" or "layer" based processing where all vertices at the same dependency depth are grouped together. Offering only one of the two standard approaches leaves a well-known, commonly requested gap for anyone whose use case wants those specific properties (e.g. build-system dependency ordering, layered scheduling).
## Suggested resolution
- Implement Kahn's algorithm (in-degree-based, using a queue) alongside the existing DFS-based version under `include/graaflib/algorithm/topological_sorting/`.
- Reuse existing `vertex_properties::vertex_indegree` where convenient.
- Add corresponding documentation under `docs/docs/algorithms/topological-sort/`, including complexity and how it compares to the existing DFS-based approach.
## Acceptance criteria
- [ ] Kahn's algorithm is implemented for directed graphs.
- [ ] It detects and reports cycles (e.g. via the same mechanism/exception used elsewhere in the library, such as in `bellman_ford`'s negative-cycle detection).
- [ ] Documentation added, including complexity and a comparison with the existing DFS-based approach.
- [ ] Unit tests cover DAGs, cyclic graphs, and disconnected graphs.
Contributor guide
Research direction
Start by reading the existing DFS topological sort in include/graaflib/algorithm/topological_sorting/dfs_topological_sorting.h and .tpp. Understand the graph representation and vertex_properties::vertex_indegree. Implement Kahn's algorithm in a new file in the same directory, using a queue and indegree tracking. Write unit tests for DAGs, cycles, and disconnected graphs. Check docs/docs/algorithms/topological-sort/ for documentation structure and add a section comparing both algorithms.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- cpp
- Issue type
- Feature
- Difficulty
- 3/5
- Estimated time
- 1-2 days
- Activity status
- Active
- Clarity
- Clearly specified
- Newbie friendliness
- 65/100