[ALGO] Kahn's Algorithm

[bobluppes]

Kahn's Algorithm

Kahn's algorithm is used for finding a topological order in a directed graph that has no cycles. The algorithm works by iteratively removing vertices that have an in-degree of zero and removing all outgoing edges from these vertices. The topological order is the sequence in which the nodes are removed.

We already have a function which computes the in-degree of a vertex in graaflib/properties/vertex_properties.h. It would be nice if we could reuse this.

For more details, see the wikipedia entry.

Syntax

The algorithm should have the following syntax:

/**
 * @brief Finds a topological ordering of a directed graph using Kahn's algorithm.
 *
 * Kahn's algorithm works by iteratively removing nodes with an in-degree of zero
 * and all their outgoing edges. The order in which nodes are removed forms the 
 * topological order. This implementation returns a vector of vertex IDs representing
 * the topological order.
 *
 * @tparam V The vertex type of the graph.
 * @tparam E The edge type of the graph.
 * @param graph The input directed graph.
 * 
 * @return An std::optional containing a std::vector of vertex IDs that make up the 
 *         topological order. Returns an empty std::optional if the graph contains a cycle.
 */
template <typename V, typename E>
std::optional<std::vector<vertex_id_t>> kahns_topological_sort(
    const graph<V, E, graph_type::DIRECTED>& graph
);

This should live in the graaf::algorithm namespace under include/graaflib/algorithm/topological_sorting/kahn.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/kahn_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

[Dhandeep10]

@bobluppes
please assign me to this issue, under hacktober fest

I completed the algorithm as per my knowledge, but when I am compiling the program, it says:
In file included from kahn.cpp:2: ./kahn.h:7:10: fatal error: 'graaflib/graph.h' file not found #include <graaflib/graph.h> ^~~~~~~~~~~~~~~~~~ 1 error generated.

please help me to fix this
and my code is completed

[bobluppes]

@bobluppes please assign me to this issue, under hacktober fest

I completed the algorithm as per my knowledge, but when I am compiling the program, it says: In file included from kahn.cpp:2: ./kahn.h:7:10: fatal error: 'graaflib/graph.h' file not found #include <graaflib/graph.h> ^~~~~~~~~~~~~~~~~~ 1 error generated.

please help me to fix this and my code is completed

Hi, of course, welcome to Graaf!

Regarding your issue, maybe you need to reload your cmake config? If the issue persists feel free to reach out in our discord.

[Dhandeep10]

hey @bobluppes have raised a PR regarding this, but 1 check was not completed "Pull-Request-CI / format (pull_request) Failing after 32s"
Can you please help me what I should do here/

[bobluppes]

hey @bobluppes have raised a PR regarding this, but 1 check was not completed "Pull-Request-CI / format (pull_request) Failing after 32s" Can you please help me what I should do here/

Hi @Dhandeep10, it seems like there are some formatting issues on the PR. You should be able to fix them locally by running clang-format. See this wiki article for more details.

I see there is already some feedback on the PR, let me know if you are still planning on taking this up :)

[github-actions]

Stale issue message