[ALGO] Kosaraju's Algorithm

[bobluppes]

Kosaraju's Algorithm

Kosaraju's algorithm identifies the strongly connected components (SCCs) in a directed graph. A strongly connected component is a subgraph in which there is a path from every vertex to every other vertex. The algorithm uses two depth-first searches to identify these components.

When possible, it would be nice to see if we can reuse the existing DFS functionality in algorithm/graph_traversal/depth_first_search.h.

For more details, see the wikipedia entry.

Syntax

The algorithm should have the following syntax:

/**
 * @brief Finds strongly connected components in a directed graph using Kosaraju's algorithm.
 *
 * Kosaraju's algorithm identifies strongly connected components (SCCs) in a directed graph.
 * The algorithm uses two depth-first searches to discover these components. 
 *
 * @tparam V The vertex type of the graph.
 * @tparam E The edge type of the graph.
 * @param graph The input directed graph.
 * 
 * @return A std::vector of vectors, each of which contains the vertex IDs forming
 *         a strongly connected component.
 */
template <typename V, typename E>
std::vector<std::vector<vertex_id_t>> kosarajus_strongly_connected_components(
    const graph<V, E, graph_type::DIRECTED>& graph
);

This should live in the graaf::algorithm namespace under include/graaflib/algorithm/strongly_connected_components/kosarajus.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/strongly_connected_components/kosarajus_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

[toadkarter]

Hi there - happy to take a look at this one if it's still available. If this issue could be assigned to me that would be great.

[bobluppes]

Hi there - happy to take a look at this one if it's still available. If this issue could be assigned to me that would be great.

Hi, of course! Looking forward to your contribution!

[toadkarter]

Thanks! If I recall correctly Kosaraju's uses a transposed version of the graph for the second DFS traversal.

Do you think it makes sense to add a get_transposed or something along those lines to the graph class? That functionality might be of use outside of just the Kosaraju's algorithm. I will of course write tests for the new function if that's something you think we might like to go ahead with.

[bobluppes]

Thanks! If I recall correctly Kosaraju's uses a transposed version of the graph for the second DFS traversal.

Do you think it makes sense to add a get_transposed or something along those lines to the graph class? That functionality might be of use outside of just the Kosaraju's algorithm. I will of course write tests for the new function if that's something you think we might like to go ahead with.

Hi, great idea! Maybe we can add it as a free function as one of our design goals is to keep the graph interface as clean as possible

[toadkarter]

That sounds great, will do!