[ALGO] Bron-Kerbosch Clique Detection

[bobluppes]

Bron-Kerbosch

The Bron-Kerbosch algorithm is a backtrack algorithm to find all cliques in an undirected graph. It serves as an essential tool for identifying densely connected subgraphs within a graph and has applications ranging from social network analysis to bioinformatics.

Implementing this would introduce a new category of algorithms (clique detection) to our library, enhancing its functionality.

See the wikipedia entry for more details.

Syntax

The algorithm should have the following syntax:

/**
 * @brief Finds all cliques in an undirected graph using the Bron-Kerbosch algorithm.
 * 
 * The Bron-Kerbosch algorithm is used for finding all cliques in an undirected graph.
 * A clique is a subset of vertices such that every two distinct vertices are adjacent.
 * This function returns a list of all cliques, each represented as a vector of vertex identifiers.
 * 
 * @tparam V The vertex type of the graph.
 * @tparam E The edge type of the graph.
 * @param graph The graph in which we want to find the cliques.
 * @return A vector of cliques, each represented as a vector of vertex identifiers.
 */
template <typename V, typename E>
std::vector<std::vector<vertex_id_t>> bron_kerbosch(const graph<V, E, graph_type::UNDIRECTED>& graph);

This should live in the graaf::algorithm namespace under include/graaflib/algorithm/clique/bron_kerbosch.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/clique/bron_kerbosch_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 can i do that after Floyd-Warshall?

[bobluppes]

Hey @bobluppes can i do that after Floyd-Warshall?

Hi @Hromzm, of course! Looking forward to your contribution :)

[Hromz]

Hey @bobluppes, i made PR #139.