weavatrix_graph/algo/
cliques.rs

1use crate::IndexUndirectedGraphView;
2use crate::Vec;
3
4#[derive(Debug, Clone, PartialEq, Eq)]
5pub struct CliqueEnumeration<Node> {
6    cliques: Vec<Vec<Node>>,
7    truncated: bool,
8}
9
10impl<Node> CliqueEnumeration<Node> {
11    #[must_use]
12    pub fn cliques(&self) -> &[Vec<Node>] {
13        &self.cliques
14    }
15
16    #[must_use]
17    pub const fn truncated(&self) -> bool {
18        self.truncated
19    }
20}
21
22pub fn maximal_cliques<G>(graph: &G, max_cliques: usize) -> CliqueEnumeration<G::Node>
23where
24    G: IndexUndirectedGraphView,
25{
26    if max_cliques == 0 {
27        return CliqueEnumeration {
28            cliques: Vec::new(),
29            truncated: false,
30        };
31    }
32    let (nodes, adjacency) = matrix(graph);
33    let candidates = nodes
34        .iter()
35        .enumerate()
36        .filter_map(|(slot, node)| node.is_some().then_some(slot))
37        .collect();
38    let mut state = CliqueState {
39        current: Vec::new(),
40        cliques: Vec::new(),
41        limit: max_cliques,
42        truncated: false,
43    };
44    bron_kerbosch(&adjacency, candidates, Vec::new(), &nodes, &mut state);
45    CliqueEnumeration {
46        cliques: state.cliques,
47        truncated: state.truncated,
48    }
49}
50
51fn matrix<G: IndexUndirectedGraphView>(graph: &G) -> (Vec<Option<G::Node>>, Vec<Vec<bool>>) {
52    let mut nodes = vec![None; graph.node_bound()];
53    let mut adjacency = vec![vec![false; graph.node_bound()]; graph.node_bound()];
54    for node in graph.node_indices() {
55        let source = G::node_slot(node);
56        nodes[source] = Some(node);
57        for edge in graph.incident_edges(node) {
58            if let Some(target) = graph.opposite(edge, node) {
59                let target = G::node_slot(target);
60                if source != target {
61                    adjacency[source][target] = true;
62                }
63            }
64        }
65    }
66    (nodes, adjacency)
67}
68
69struct CliqueState<Node> {
70    current: Vec<usize>,
71    cliques: Vec<Vec<Node>>,
72    limit: usize,
73    truncated: bool,
74}
75
76fn bron_kerbosch<Node: Copy>(
77    adjacency: &[Vec<bool>],
78    mut candidates: Vec<usize>,
79    mut excluded: Vec<usize>,
80    nodes: &[Option<Node>],
81    state: &mut CliqueState<Node>,
82) {
83    if candidates.is_empty() && excluded.is_empty() {
84        if state.cliques.len() == state.limit {
85            state.truncated = true;
86            return;
87        }
88        let mut clique = state
89            .current
90            .iter()
91            .filter_map(|slot| nodes[*slot].map(|node| (*slot, node)))
92            .collect::<Vec<_>>();
93        clique.sort_unstable_by_key(|(slot, _)| *slot);
94        state
95            .cliques
96            .push(clique.into_iter().map(|(_, node)| node).collect());
97        return;
98    }
99    let pivot = candidates
100        .iter()
101        .chain(&excluded)
102        .copied()
103        .max_by_key(|pivot| {
104            candidates
105                .iter()
106                .filter(|candidate| adjacency[*pivot][**candidate])
107                .count()
108        });
109    let branch = candidates
110        .iter()
111        .copied()
112        .filter(|candidate| pivot.is_none_or(|pivot| !adjacency[pivot][*candidate]))
113        .collect::<Vec<_>>();
114    for node in branch {
115        state.current.push(node);
116        bron_kerbosch(
117            adjacency,
118            candidates
119                .iter()
120                .copied()
121                .filter(|candidate| adjacency[node][*candidate])
122                .collect(),
123            excluded
124                .iter()
125                .copied()
126                .filter(|candidate| adjacency[node][*candidate])
127                .collect(),
128            nodes,
129            state,
130        );
131        state.current.pop();
132        if state.truncated {
133            return;
134        }
135        candidates.retain(|candidate| *candidate != node);
136        excluded.push(node);
137    }
138}
weavatrix_graph/algo/cliques.rs

weavatrix_graph/algo/
cliques.rs
