yog/properties/clique
Clique finding algorithms using the Bron-Kerbosch algorithm.
A clique is a subset of nodes where every pair of nodes is connected.
Values
pub fn all_maximal_cliques(
graph: model.Graph(n, e),
) -> List(set.Set(Int))Finds all maximal cliques in an undirected graph.
A maximal clique is a clique that cannot be extended by adding another node.
Time Complexity: O(3^(n/3)) worst case
Example
clique.all_maximal_cliques(graph)
// => [set.from_list([1, 2]), set.from_list([2, 3])]
pub fn k_cliques(
graph: model.Graph(n, e),
k: Int,
) -> List(set.Set(Int))Finds all cliques of exactly size k in an undirected graph.
Uses a modified Bron-Kerbosch algorithm with early pruning.
Time Complexity: O(3^(n/3)) worst case
Example
clique.k_cliques(graph, 3)
// => [set.from_list([1, 2, 3])]
pub fn max_clique(graph: model.Graph(n, e)) -> set.Set(Int)Finds the maximum clique in an undirected graph.
Returns the largest subset of nodes where every pair is connected.
Time Complexity: O(3^(n/3)) worst case
Example
clique.max_clique(graph)
// => set.from_list([1, 2, 3, 4])