[ALGO] Tarjan's Strongly Connected Components

[bobluppes]

Tarjan's Strongly Connected Components

Tarjan's algorithm can be used to find the Strongly Connected Components (SCCs) of a directed graph. An SCC is a subset of vertices in the graph for which every vertex is reachable from every other vertex in the subset. See the wikipedia entry for more details on Tarjan's algorithm.

Syntax

The algorithm should have the following syntax:

/**
 * Computes the Strongly Connected Components (SCCs) of a graph using Tarjan's algorithm.
 *
 * This function takes a graph and returns a vector of vectors representing the SCCs.
 * Each inner vector contains the vertices of a strongly connected component, and the outer vector
 * contains all the strongly connected components in the graph.
 *
 * @tparam V Vertex type.
 * @tparam E Edge type.
 * @param graph The graph for which to compute SCCs.
 * @return std::vector<std::vector<vertex_id_t>> A vector of vectors representing SCCs.
 */
template <typename V, typename E>
[[nodiscard]] std::vector<std::vector<vertex_id_t>> tarjans_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.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_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

[ndcroos]

Hi, I'd like to work on this after doing Bellman-Ford.

[bobluppes]

Hi @ndcroos, awesome, I will assign it to you :)