yog - v2.2.0

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

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
✨ Search Document