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 mapping = pattern_nodes
161 .iter()
162 .map(|node| {
163 state
164 .mapping
165 .get(P::node_slot(*node))
166 .copied()
167 .flatten()
168 .map(|target| (*node, target))
169 })
170 .collect::<Option<Vec<_>>>();
171 let Some(mut mapping) = mapping else {
172 return;
173 };
174 mapping.sort_unstable_by_key(|(node, _)| P::node_slot(*node));
175 state.results.push(mapping);
176 return;
177 }
178 let pattern_node = pattern_nodes[depth];
179 for &target_node in target_nodes {
180 let target_slot = T::node_slot(target_node);
181 if state.used[target_slot]
182 || !node_match(pattern_node, target_node)
183 || !degree_compatible(pattern, target, pattern_node, target_node, mode)
184 || !edges_compatible::<P, T, E>(
185 pattern_edges,
186 target_edges,
187 pattern_node,
188 target_node,
189 &state.mapping,
190 mode,
191 edge_match,
192 )
193 {
194 continue;
195 }
196 state.mapping[P::node_slot(pattern_node)] = Some(target_node);
197 state.used[target_slot] = true;
198 search(
199 pattern,
200 target,
201 pattern_edges,
202 target_edges,
203 pattern_nodes,
204 target_nodes,
205 mode,
206 node_match,
207 edge_match,
208 depth + 1,
209 state,
210 );
211 state.used[target_slot] = false;
212 state.mapping[P::node_slot(pattern_node)] = None;
213 if state.truncated {
214 return;
215 }
216 }
217}
218
219fn degree_compatible<P, T>(
220 pattern: &P,
221 target: &T,
222 pattern_node: P::Node,
223 target_node: T::Node,
224 _mode: SubgraphMode,
225) -> bool
226where
227 P: IndexGraphView,
228 T: IndexGraphView,
229{
230 let pattern_degree = (
231 pattern.outgoing_edges(pattern_node).count(),
232 pattern.incoming_edges(pattern_node).count(),
233 );
234 let target_degree = (
235 target.outgoing_edges(target_node).count(),
236 target.incoming_edges(target_node).count(),
237 );
238 pattern_degree.0 <= target_degree.0 && pattern_degree.1 <= target_degree.1
239}
240
241#[allow(clippy::too_many_arguments)]
242fn edges_compatible<P, T, E>(
243 pattern: &EdgeMatrix<P::Edge>,
244 target: &EdgeMatrix<T::Edge>,
245 pattern_node: P::Node,
246 target_node: T::Node,
247 mapping: &[Option<T::Node>],
248 mode: SubgraphMode,
249 edge_match: &E,
250) -> bool
251where
252 P: IndexGraphView,
253 T: IndexGraphView,
254 E: Fn(P::Edge, T::Edge) -> bool,
255{
256 let pattern_slot = P::node_slot(pattern_node);
257 let target_slot = T::node_slot(target_node);
258 if !edge_lists_compatible(
259 pattern.get(pattern_slot, pattern_slot),
260 target.get(target_slot, target_slot),
261 mode,
262 edge_match,
263 ) {
264 return false;
265 }
266 mapping.iter().enumerate().all(|(other_pattern, mapped)| {
267 let Some(other_target) = mapped else {
268 return true;
269 };
270 let other_target = T::node_slot(*other_target);
271 edge_lists_compatible(
272 pattern.get(pattern_slot, other_pattern),
273 target.get(target_slot, other_target),
274 mode,
275 edge_match,
276 ) && edge_lists_compatible(
277 pattern.get(other_pattern, pattern_slot),
278 target.get(other_target, target_slot),
279 mode,
280 edge_match,
281 )
282 })
283}