petgraph/algo/
maximal_cliques.rs

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.
9///
10/// By default, only works on undirected graphs. It can be used on directed graphs
11/// if the graph is symmetric. I.e., if an edge (u, v) exists, then (v, u) also exists.
12///
13/// Uses the [Bron–Kerbosch algorithm][1] with pivoting.
14///
15/// [1]: https://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm
16fn bron_kerbosch_pivot<G>(
17    g: G,
18    adj_mat: &G::AdjMatrix,
19    r: HashSet<G::NodeId>,
20    mut p: HashSet<G::NodeId>,
21    mut x: HashSet<G::NodeId>,
22) -> Vec<HashSet<G::NodeId>>
23where
24    G: GetAdjacencyMatrix + IntoNeighbors,
25    G::NodeId: Eq + Hash,
26{
27    let mut cliques = Vec::with_capacity(1);
28    if p.is_empty() {
29        if x.is_empty() {
30            cliques.push(r);
31        }
32        return cliques;
33    }
34    // pick the pivot u to be the vertex with max degree
35    let u = p.iter().max_by_key(|&v| g.neighbors(*v).count()).unwrap();
36    let mut todo = p
37        .iter()
38        .filter(|&v| *u == *v || !g.is_adjacent(adj_mat, *u, *v) || !g.is_adjacent(adj_mat, *v, *u)) //skip neighbors of pivot
39        .cloned()
40        .collect::<Vec<G::NodeId>>();
41    while let Some(v) = todo.pop() {
42        let neighbors = HashSet::from_iter(g.neighbors(v));
43        p.remove(&v);
44        let mut next_r = r.clone();
45        next_r.insert(v);
46
47        let next_p = p
48            .intersection(&neighbors)
49            .cloned()
50            .collect::<HashSet<G::NodeId>>();
51        let next_x = x
52            .intersection(&neighbors)
53            .cloned()
54            .collect::<HashSet<G::NodeId>>();
55
56        cliques.extend(bron_kerbosch_pivot(g, adj_mat, next_r, next_p, next_x));
57
58        x.insert(v);
59    }
60
61    cliques
62}
63
64/// Find all maximal cliques in an undirected graph using [Bron–Kerbosch algorithm][1]
65/// with pivoting. Also works on symmetric directed graphs, see the note below.
66///
67/// A clique is a set of nodes such that every node connects to
68/// every other. A maximal clique is a clique that cannot be extended
69/// by including one more adjacent vertex. A graph may have multiple
70/// maximal cliques.
71///
72/// This method may also be called on directed graphs, but one needs to ensure that
73/// if an edge (u, v) exists, then (v, u) also exists.
74///
75/// # Arguments
76/// * `g`: The graph to find maximal cliques in.
77///
78/// # Returns
79/// * `Vec<HashSet>`: A vector of [`struct@hashbrown::HashSet`] making up the maximal cliques in the graph.
80///
81/// # Complexity
82/// * Time complexity: **O(3^(|V|/3))**
83/// * Auxiliary space: **O(|V|² + |V|k)**.
84///
85/// where **|V|** is the number of nodes and k is the number of maximal cliques in the graph
86/// (possibly up to *3^(|V|/3)** many).
87///
88/// [1]: https://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm
89///
90/// # Example
91///
92/// ```
93/// use petgraph::algo::maximal_cliques;
94/// use petgraph::graph::UnGraph;
95///
96/// let mut g = UnGraph::<i32, ()>::from_edges([(0, 1), (0, 2), (1, 2), (2, 3)]);
97/// g.add_node(4);
98/// // The example graph:
99/// //
100/// // 0 --- 2 -- 3
101/// //  \   /
102/// //   \ /
103/// //    1       4
104/// //
105/// // maximal cliques: {4}, {2, 3}, {0, 1, 2}
106/// // Output the result
107/// let cliques = maximal_cliques(&g);
108/// println!("{:?}", cliques);
109/// // [
110/// //   {NodeIndex(4)},
111/// //   {NodeIndex(0), NodeIndex(1), NodeIndex(2)},
112/// //   {NodeIndex(2), NodeIndex(3)}
113/// // ]
114/// ```
115pub fn maximal_cliques<G>(g: G) -> Vec<HashSet<G::NodeId>>
116where
117    G: GetAdjacencyMatrix + IntoNodeIdentifiers + IntoNeighbors,
118    G::NodeId: Eq + Hash,
119{
120    let adj_mat = g.adjacency_matrix();
121    let r = HashSet::new();
122    let p = g.node_identifiers().collect::<HashSet<G::NodeId>>();
123    let x = HashSet::new();
124    bron_kerbosch_pivot(g, &adj_mat, r, p, x)
125}
petgraph/algo/maximal_cliques.rs

petgraph/algo/
maximal_cliques.rs
