weavatrix_graph/algo/
isomorphism.rs

1use super::isomorphism_match::edge_lists_compatible;
2use crate::IndexGraphView;
3use crate::Vec;
4
5#[derive(Debug, Clone, Copy, PartialEq, Eq)]
6pub enum SubgraphMode {
7    NonInduced,
8    Induced,
9}
10
11#[derive(Debug, Clone, PartialEq, Eq)]
12pub struct IsomorphismSearch<PatternNode, TargetNode> {
13    mappings: Vec<Vec<(PatternNode, TargetNode)>>,
14    truncated: bool,
15}
16
17impl<PatternNode, TargetNode> IsomorphismSearch<PatternNode, TargetNode> {
18    #[must_use]
19    pub fn mappings(&self) -> &[Vec<(PatternNode, TargetNode)>] {
20        &self.mappings
21    }
22
23    #[must_use]
24    pub const fn truncated(&self) -> bool {
25        self.truncated
26    }
27}
28
29pub fn graph_isomorphic<P, T, N, E>(left: &P, right: &T, node_match: N, edge_match: E) -> bool
30where
31    P: IndexGraphView,
32    T: IndexGraphView,
33    N: Fn(P::Node, T::Node) -> bool,
34    E: Fn(P::Edge, T::Edge) -> bool,
35{
36    if left.node_count() != right.node_count() || left.edge_count() != right.edge_count() {
37        return false;
38    }
39    !subgraph_isomorphisms(
40        left,
41        right,
42        SubgraphMode::Induced,
43        1,
44        node_match,
45        edge_match,
46    )
47    .mappings
48    .is_empty()
49}
50
51pub fn subgraph_isomorphisms<P, T, N, E>(
52    pattern: &P,
53    target: &T,
54    mode: SubgraphMode,
55    max_mappings: usize,
56    node_match: N,
57    edge_match: E,
58) -> IsomorphismSearch<P::Node, T::Node>
59where
60    P: IndexGraphView,
61    T: IndexGraphView,
62    N: Fn(P::Node, T::Node) -> bool,
63    E: Fn(P::Edge, T::Edge) -> bool,
64{
65    if max_mappings == 0 || pattern.node_count() > target.node_count() {
66        return IsomorphismSearch {
67            mappings: Vec::new(),
68            truncated: false,
69        };
70    }
71    let pattern_matrix = EdgeMatrix::new(pattern);
72    let target_matrix = EdgeMatrix::new(target);
73    let mut pattern_nodes = pattern.node_indices().collect::<Vec<_>>();
74    pattern_nodes.sort_unstable_by_key(|node| {
75        let degree = pattern.outgoing_edges(*node).count() + pattern.incoming_edges(*node).count();
76        (usize::MAX - degree, P::node_slot(*node))
77    });
78    let mut target_nodes = target.node_indices().collect::<Vec<_>>();
79    target_nodes.sort_unstable_by_key(|node| T::node_slot(*node));
80    let mut state = SearchState {
81        mapping: vec![None; pattern.node_bound()],
82        used: vec![false; target.node_bound()],
83        results: Vec::new(),
84        limit: max_mappings,
85        truncated: false,
86    };
87    search(
88        pattern,
89        target,
90        &pattern_matrix,
91        &target_matrix,
92        &pattern_nodes,
93        &target_nodes,
94        mode,
95        &node_match,
96        &edge_match,
97        0,
98        &mut state,
99    );
100    IsomorphismSearch {
101        mappings: state.results,
102        truncated: state.truncated,
103    }
104}
105
106struct EdgeMatrix<Edge> {
107    bound: usize,
108    cells: Vec<Vec<Edge>>,
109}
110
111impl<Edge: Copy> EdgeMatrix<Edge> {
112    fn new<G: IndexGraphView<Edge = Edge>>(graph: &G) -> Self {
113        let bound = graph.node_bound();
114        let mut cells = vec![Vec::new(); bound.saturating_mul(bound)];
115        for (edge, endpoints) in graph.edge_references() {
116            let source = G::node_slot(endpoints.source());
117            let target = G::node_slot(endpoints.target());
118            cells[source * bound + target].push(edge);
119        }
120        Self { bound, cells }
121    }
122
123    fn get(&self, source: usize, target: usize) -> &[Edge] {
124        &self.cells[source * self.bound + target]
125    }
126}
127
128struct SearchState<PatternNode, TargetNode> {
129    mapping: Vec<Option<TargetNode>>,
130    used: Vec<bool>,
131    results: Vec<Vec<(PatternNode, TargetNode)>>,
132    limit: usize,
133    truncated: bool,
134}
135
136#[allow(clippy::too_many_arguments)]
137fn search<P, T, N, E>(
138    pattern: &P,
139    target: &T,
140    pattern_edges: &EdgeMatrix<P::Edge>,
141    target_edges: &EdgeMatrix<T::Edge>,
142    pattern_nodes: &[P::Node],
143    target_nodes: &[T::Node],
144    mode: SubgraphMode,
145    node_match: &N,
146    edge_match: &E,
147    depth: usize,
148    state: &mut SearchState<P::Node, T::Node>,
149) where
150    P: IndexGraphView,
151    T: IndexGraphView,
152    N: Fn(P::Node, T::Node) -> bool,
153    E: Fn(P::Edge, T::Edge) -> bool,
154{
155    if state.results.len() == state.limit {
156        state.truncated = true;
157        return;
158    }
159    if depth == pattern_nodes.len() {
160        let mut mapping = pattern_nodes
161            .iter()
162            .map(|node| {
163                (
164                    *node,
165                    state.mapping[P::node_slot(*node)].expect("complete mapping"),
166                )
167            })
168            .collect::<Vec<_>>();
169        mapping.sort_unstable_by_key(|(node, _)| P::node_slot(*node));
170        state.results.push(mapping);
171        return;
172    }
173    let pattern_node = pattern_nodes[depth];
174    for &target_node in target_nodes {
175        let target_slot = T::node_slot(target_node);
176        if state.used[target_slot]
177            || !node_match(pattern_node, target_node)
178            || !degree_compatible(pattern, target, pattern_node, target_node, mode)
179            || !edges_compatible::<P, T, E>(
180                pattern_edges,
181                target_edges,
182                pattern_node,
183                target_node,
184                &state.mapping,
185                mode,
186                edge_match,
187            )
188        {
189            continue;
190        }
191        state.mapping[P::node_slot(pattern_node)] = Some(target_node);
192        state.used[target_slot] = true;
193        search(
194            pattern,
195            target,
196            pattern_edges,
197            target_edges,
198            pattern_nodes,
199            target_nodes,
200            mode,
201            node_match,
202            edge_match,
203            depth + 1,
204            state,
205        );
206        state.used[target_slot] = false;
207        state.mapping[P::node_slot(pattern_node)] = None;
208        if state.truncated {
209            return;
210        }
211    }
212}
213
214fn degree_compatible<P, T>(
215    pattern: &P,
216    target: &T,
217    pattern_node: P::Node,
218    target_node: T::Node,
219    _mode: SubgraphMode,
220) -> bool
221where
222    P: IndexGraphView,
223    T: IndexGraphView,
224{
225    let pattern_degree = (
226        pattern.outgoing_edges(pattern_node).count(),
227        pattern.incoming_edges(pattern_node).count(),
228    );
229    let target_degree = (
230        target.outgoing_edges(target_node).count(),
231        target.incoming_edges(target_node).count(),
232    );
233    pattern_degree.0 <= target_degree.0 && pattern_degree.1 <= target_degree.1
234}
235
236#[allow(clippy::too_many_arguments)]
237fn edges_compatible<P, T, E>(
238    pattern: &EdgeMatrix<P::Edge>,
239    target: &EdgeMatrix<T::Edge>,
240    pattern_node: P::Node,
241    target_node: T::Node,
242    mapping: &[Option<T::Node>],
243    mode: SubgraphMode,
244    edge_match: &E,
245) -> bool
246where
247    P: IndexGraphView,
248    T: IndexGraphView,
249    E: Fn(P::Edge, T::Edge) -> bool,
250{
251    let pattern_slot = P::node_slot(pattern_node);
252    let target_slot = T::node_slot(target_node);
253    if !edge_lists_compatible(
254        pattern.get(pattern_slot, pattern_slot),
255        target.get(target_slot, target_slot),
256        mode,
257        edge_match,
258    ) {
259        return false;
260    }
261    mapping.iter().enumerate().all(|(other_pattern, mapped)| {
262        let Some(other_target) = mapped else {
263            return true;
264        };
265        let other_target = T::node_slot(*other_target);
266        edge_lists_compatible(
267            pattern.get(pattern_slot, other_pattern),
268            target.get(target_slot, other_target),
269            mode,
270            edge_match,
271        ) && edge_lists_compatible(
272            pattern.get(other_pattern, pattern_slot),
273            target.get(other_target, target_slot),
274            mode,
275            edge_match,
276        )
277    })
278}
weavatrix_graph/algo/isomorphism.rs

weavatrix_graph/algo/
isomorphism.rs
