[ALGO] Topological Sorting (DFS-Based)

[bobluppes]

Topological Sorting (DFS-Based)

A topological sort is a linear ordering of all vertices in a directed graph such that a vertex is only visited after its dependencies are visited. The goal of this issue is to implement topological sorting based on DFS.

The existing DFS functionality (depth_first_traverse) should be re-used, rather than implementing a new DFS traversal.

See the wikipedia entry for more details.

Syntax

The algorithm should have the following syntax:

template <typename V, typename E, graph_type T>
[[nodiscard]] return_type your_algorithm_name(const graph<V, E, T>& graph);

This should live in the graaf::algorithm namespace under include/graaflib/algorithm/topological_sorting.h.

Definition of Done

This issue is done when:

• The algorithm is implemented
• The new function has a javadoc-style comment explaining the interface
• Appropriate tests are added under test/graaflib/algorithm/topological_sorting_test.cpp
• A test coverage of at least 95% is reached
• A documentation entry is added under docs/docs/algorithms under the appropriate category
  • Just adding a short description and the algorithm syntax here is fine
  • See the wiki on how to build the documentation locally
• The algorithm is added to the list of algorithms in README.md

[Hromz]

Hey @bobluppes ! Assign to me please. I wanna work on this after MST.

[bobluppes]

Hi @Hromz, of course, would be happy to! Assigning this to you

[Hromz]

Hey @bobluppes, You have mentioned using existing DFS functionality. Right now, the solution I can propose is to store edges and process them after. It would be simple if we had a post-order callback.
Another approach is to add a new DFS (12 lines of code) and use the existing cycle detection algorithm.
Correct me if I'm wrong or missed something.
I'm looking forward to your answer! :)

[bobluppes]

Hi @Hromz, looking at the pseudo algorithm on wikipedia, do you mean a callback to add the node to the list of sorted nodes?

I would also be fine with adding a separate DFS implementation for this functionality.

[Hromz]

Correct, callback to the list. Alright, i'll add separate DFS implementation and change it in the future if needed.

[bobluppes]

Correct, callback to the list. Alright, i'll add separate DFS implementation and change it in the future if needed.

Thanks! For now we can keep it in the anonymous namespace of the topological sorting algorithm. We can see if it makes sense to expose it later