yog/clique

Maximum clique finding using the Bron-Kerbosch algorithm.

A clique is a subset of vertices where every two vertices are adjacent (i.e., a complete subgraph). Finding the maximum clique is NP-complete, but the Bron-Kerbosch algorithm with pivoting is efficient in practice.

Use Cases

Social network analysis: Finding tightly-knit friend groups
Computational biology: Identifying protein complexes
Code analysis: Detecting mutually dependent modules
Graph coloring: Chromatic number lower bounds
AoC 2024 Day 23: Finding largest sets of interconnected computers

Values

all_maximal_cliques

</>

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. Note that there can be many maximal cliques, and they may have different sizes.

Time Complexity: O(3^(n/3)) worst case

Example

import yog
import yog/clique

let graph =
  yog.undirected()
  |> yog.add_node(1, "A")
  |> yog.add_node(2, "B")
  |> yog.add_node(3, "C")
  |> yog.add_edge(from: 1, to: 2, with: 1)
  |> yog.add_edge(from: 2, to: 3, with: 1)

clique.all_maximal_cliques(graph)
// => [set.from_list([1, 2]), set.from_list([2, 3])]

k_cliques

</>

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.

Returns all subsets of k nodes where every pair of nodes is connected. Uses a modified Bron-Kerbosch algorithm with early pruning for efficiency.

Time Complexity: Generally faster than finding all maximal cliques when k is small, as branches are pruned when they cannot reach size k.

Example

import yog
import yog/clique

// Create a graph with triangles (3-cliques)
let graph =
  yog.undirected()
  |> yog.add_node(1, "A")
  |> yog.add_node(2, "B")
  |> yog.add_node(3, "C")
  |> yog.add_node(4, "D")
  |> yog.add_edge(from: 1, to: 2, with: 1)
  |> yog.add_edge(from: 2, to: 3, with: 1)
  |> yog.add_edge(from: 1, to: 3, with: 1)
  |> yog.add_edge(from: 3, to: 4, with: 1)

clique.k_cliques(graph, 3)
// => [set.from_list([1, 2, 3])]  // The single triangle

clique.k_cliques(graph, 2)
// => [set.from_list([1, 2]), set.from_list([1, 3]),
//     set.from_list([2, 3]), set.from_list([3, 4])]  // All edges

Use Cases

Finding triangles (k=3) in social networks
Detecting specific-sized communities
Pattern matching in biological networks
Computational chemistry (finding molecular motifs)

max_clique

</>

pub fn max_clique(graph: model.Graph(n, e)) -> set.Set(Int)

Finds the maximum clique in an undirected graph.

A clique is a subset of nodes where every pair of nodes is connected. This function returns the largest such subset found using the Bron-Kerbosch algorithm with pivoting.

Time Complexity: O(3^(n/3)) worst case, but much faster in practice due to pivoting

Note: This algorithm works on undirected graphs. For directed graphs, consider using the underlying undirected structure.

Example

import yog
import yog/clique

// Create a graph with a 4-clique
let graph =
  yog.undirected()
  |> yog.add_node(1, "A")
  |> yog.add_node(2, "B")
  |> yog.add_node(3, "C")
  |> yog.add_node(4, "D")
  |> yog.add_node(5, "E")
  |> yog.add_edge(from: 1, to: 2, with: 1)
  |> yog.add_edge(from: 1, to: 3, with: 1)
  |> yog.add_edge(from: 1, to: 4, with: 1)
  |> yog.add_edge(from: 2, to: 3, with: 1)
  |> yog.add_edge(from: 2, to: 4, with: 1)
  |> yog.add_edge(from: 3, to: 4, with: 1)
  |> yog.add_edge(from: 4, to: 5, with: 1)

clique.max_clique(graph)
// => set.from_list([1, 2, 3, 4])  // The 4-clique