petgraph/algo/
maximal_cliques.rs

Help
1use crate::visit::{GetAdjacencyMatrix, IntoNeighbors, IntoNodeIdentifiers};
2use alloc::vec::Vec;
3use core::hash::Hash;
4use core::iter::FromIterator;
5use hashbrown::HashSet;
6
7/// Finds maximal cliques containing all the vertices in r, some of the
8/// vertices in p, and none of the vertices in x.
9fn bron_kerbosch_pivot<G>(
10    g: G,
11    adj_mat: &G::AdjMatrix,
12    r: HashSet<G::NodeId>,
13    mut p: HashSet<G::NodeId>,
14    mut x: HashSet<G::NodeId>,
15) -> Vec<HashSet<G::NodeId>>
16where
17    G: GetAdjacencyMatrix + IntoNeighbors,
18    G::NodeId: Eq + Hash,
19{
20    let mut cliques = Vec::with_capacity(1);
21    if p.is_empty() {
22        if x.is_empty() {
23            cliques.push(r);
24        }
25        return cliques;
26    }
27    // pick the pivot u to be the vertex with max degree
28    let u = p.iter().max_by_key(|&v| g.neighbors(*v).count()).unwrap();
29    let mut todo = p
30        .iter()
31        .filter(|&v| *u == *v || !g.is_adjacent(adj_mat, *u, *v) || !g.is_adjacent(adj_mat, *v, *u)) //skip neighbors of pivot
32        .cloned()
33        .collect::<Vec<G::NodeId>>();
34    while let Some(v) = todo.pop() {
35        let neighbors = HashSet::from_iter(g.neighbors(v));
36        p.remove(&v);
37        let mut next_r = r.clone();
38        next_r.insert(v);
39
40        let next_p = p
41            .intersection(&neighbors)
42            .cloned()
43            .collect::<HashSet<G::NodeId>>();
44        let next_x = x
45            .intersection(&neighbors)
46            .cloned()
47            .collect::<HashSet<G::NodeId>>();
48
49        cliques.extend(bron_kerbosch_pivot(g, adj_mat, next_r, next_p, next_x));
50
51        x.insert(v);
52    }
53
54    cliques
55}
56
57/// Find all maximal cliques in a graph using Bron–Kerbosch algorithm
58/// with pivoting.
59///
60/// A clique is a set of nodes such that every node connects to
61/// every other. A maximal clique is a clique that cannot be extended
62/// by including one more adjacent vertex. A graph may have multiple
63/// maximal cliques.
64///
65/// Example
66/// ```
67/// use petgraph::algo::maximal_cliques;
68/// use petgraph::graph::UnGraph;
69///
70/// let mut g = UnGraph::<i32, ()>::from_edges([(0, 1), (0, 2), (1, 2), (2, 3)]);
71/// g.add_node(4);
72/// // The example graph:
73/// //
74/// // 0 --- 2 -- 3
75/// //  \   /
76/// //   \ /
77/// //    1       4
78/// //
79/// // maximal cliques: {4}, {2, 3}, {0, 1, 2}
80/// // Output the result
81/// let cliques = maximal_cliques(&g);
82/// println!("{:?}", cliques);
83/// // [
84/// //   {NodeIndex(4)},
85/// //   {NodeIndex(0), NodeIndex(1), NodeIndex(2)},
86/// //   {NodeIndex(2), NodeIndex(3)}
87/// // ]
88/// ```
89pub fn maximal_cliques<G>(g: G) -> Vec<HashSet<G::NodeId>>
90where
91    G: GetAdjacencyMatrix + IntoNodeIdentifiers + IntoNeighbors,
92    G::NodeId: Eq + Hash,
93{
94    let adj_mat = g.adjacency_matrix();
95    let r = HashSet::new();
96    let p = g.node_identifiers().collect::<HashSet<G::NodeId>>();
97    let x = HashSet::new();
98    bron_kerbosch_pivot(g, &adj_mat, r, p, x)
99}
petgraph/algo/maximal_cliques.rs

petgraph/algo/
maximal_cliques.rs
