1 use fixedbitset::FixedBitSet;
2 use std::marker;
3
4 use super::graph::{Graph, IndexType, NodeIndex};
5 use super::{EdgeType, Incoming};
6
7 use super::visit::GetAdjacencyMatrix;
8
9 #[derive(Debug)]
10 struct Vf2State<Ty, Ix> {
11 /// The current mapping M(s) of nodes from G0 → G1 and G1 → G0,
12 /// NodeIndex::end() for no mapping.
13 mapping: Vec<NodeIndex<Ix>>,
14 /// out[i] is non-zero if i is in either M_0(s) or Tout_0(s)
15 /// These are all the next vertices that are not mapped yet, but
16 /// have an outgoing edge from the mapping.
17 out: Vec<usize>,
18 /// ins[i] is non-zero if i is in either M_0(s) or Tin_0(s)
19 /// These are all the incoming vertices, those not mapped yet, but
20 /// have an edge from them into the mapping.
21 /// Unused if graph is undirected -- it's identical with out in that case.
22 ins: Vec<usize>,
23 out_size: usize,
24 ins_size: usize,
25 adjacency_matrix: FixedBitSet,
26 generation: usize,
27 _etype: marker::PhantomData<Ty>,
28 }
29
30 impl<Ty, Ix> Vf2State<Ty, Ix>
31 where
32 Ty: EdgeType,
33 Ix: IndexType,
34 {
new<N, E>(g: &Graph<N, E, Ty, Ix>) -> Self35 pub fn new<N, E>(g: &Graph<N, E, Ty, Ix>) -> Self {
36 let c0 = g.node_count();
37 let mut state = Vf2State {
38 mapping: Vec::with_capacity(c0),
39 out: Vec::with_capacity(c0),
40 ins: Vec::with_capacity(c0 * (g.is_directed() as usize)),
41 out_size: 0,
42 ins_size: 0,
43 adjacency_matrix: g.adjacency_matrix(),
44 generation: 0,
45 _etype: marker::PhantomData,
46 };
47 for _ in 0..c0 {
48 state.mapping.push(NodeIndex::end());
49 state.out.push(0);
50 if Ty::is_directed() {
51 state.ins.push(0);
52 }
53 }
54 state
55 }
56
57 /// Return **true** if we have a complete mapping
is_complete(&self) -> bool58 pub fn is_complete(&self) -> bool {
59 self.generation == self.mapping.len()
60 }
61
62 /// Add mapping **from** <-> **to** to the state.
push_mapping<N, E>( &mut self, from: NodeIndex<Ix>, to: NodeIndex<Ix>, g: &Graph<N, E, Ty, Ix>, )63 pub fn push_mapping<N, E>(
64 &mut self,
65 from: NodeIndex<Ix>,
66 to: NodeIndex<Ix>,
67 g: &Graph<N, E, Ty, Ix>,
68 ) {
69 self.generation += 1;
70 let s = self.generation;
71 self.mapping[from.index()] = to;
72 // update T0 & T1 ins/outs
73 // T0out: Node in G0 not in M0 but successor of a node in M0.
74 // st.out[0]: Node either in M0 or successor of M0
75 for ix in g.neighbors(from) {
76 if self.out[ix.index()] == 0 {
77 self.out[ix.index()] = s;
78 self.out_size += 1;
79 }
80 }
81 if g.is_directed() {
82 for ix in g.neighbors_directed(from, Incoming) {
83 if self.ins[ix.index()] == 0 {
84 self.ins[ix.index()] = s;
85 self.ins_size += 1;
86 }
87 }
88 }
89 }
90
91 /// Restore the state to before the last added mapping
pop_mapping<N, E>(&mut self, from: NodeIndex<Ix>, g: &Graph<N, E, Ty, Ix>)92 pub fn pop_mapping<N, E>(&mut self, from: NodeIndex<Ix>, g: &Graph<N, E, Ty, Ix>) {
93 let s = self.generation;
94 self.generation -= 1;
95
96 // undo (n, m) mapping
97 self.mapping[from.index()] = NodeIndex::end();
98
99 // unmark in ins and outs
100 for ix in g.neighbors(from) {
101 if self.out[ix.index()] == s {
102 self.out[ix.index()] = 0;
103 self.out_size -= 1;
104 }
105 }
106 if g.is_directed() {
107 for ix in g.neighbors_directed(from, Incoming) {
108 if self.ins[ix.index()] == s {
109 self.ins[ix.index()] = 0;
110 self.ins_size -= 1;
111 }
112 }
113 }
114 }
115
116 /// Find the next (least) node in the Tout set.
next_out_index(&self, from_index: usize) -> Option<usize>117 pub fn next_out_index(&self, from_index: usize) -> Option<usize> {
118 self.out[from_index..]
119 .iter()
120 .enumerate()
121 .find(move |&(index, elt)| {
122 *elt > 0 && self.mapping[from_index + index] == NodeIndex::end()
123 })
124 .map(|(index, _)| index)
125 }
126
127 /// Find the next (least) node in the Tin set.
next_in_index(&self, from_index: usize) -> Option<usize>128 pub fn next_in_index(&self, from_index: usize) -> Option<usize> {
129 if !Ty::is_directed() {
130 return None;
131 }
132 self.ins[from_index..]
133 .iter()
134 .enumerate()
135 .find(move |&(index, elt)| {
136 *elt > 0 && self.mapping[from_index + index] == NodeIndex::end()
137 })
138 .map(|(index, _)| index)
139 }
140
141 /// Find the next (least) node in the N - M set.
next_rest_index(&self, from_index: usize) -> Option<usize>142 pub fn next_rest_index(&self, from_index: usize) -> Option<usize> {
143 self.mapping[from_index..]
144 .iter()
145 .enumerate()
146 .find(|&(_, elt)| *elt == NodeIndex::end())
147 .map(|(index, _)| index)
148 }
149 }
150
151 /// [Graph] Return `true` if the graphs `g0` and `g1` are isomorphic.
152 ///
153 /// Using the VF2 algorithm, only matching graph syntactically (graph
154 /// structure).
155 ///
156 /// The graphs should not be multigraphs.
157 ///
158 /// **Reference**
159 ///
160 /// * Luigi P. Cordella, Pasquale Foggia, Carlo Sansone, Mario Vento;
161 /// *A (Sub)Graph Isomorphism Algorithm for Matching Large Graphs*
is_isomorphic<N, E, Ty, Ix>(g0: &Graph<N, E, Ty, Ix>, g1: &Graph<N, E, Ty, Ix>) -> bool where Ty: EdgeType, Ix: IndexType,162 pub fn is_isomorphic<N, E, Ty, Ix>(g0: &Graph<N, E, Ty, Ix>, g1: &Graph<N, E, Ty, Ix>) -> bool
163 where
164 Ty: EdgeType,
165 Ix: IndexType,
166 {
167 if g0.node_count() != g1.node_count() || g0.edge_count() != g1.edge_count() {
168 return false;
169 }
170
171 let mut st = [Vf2State::new(g0), Vf2State::new(g1)];
172 try_match(&mut st, g0, g1, &mut NoSemanticMatch, &mut NoSemanticMatch).unwrap_or(false)
173 }
174
175 /// [Graph] Return `true` if the graphs `g0` and `g1` are isomorphic.
176 ///
177 /// Using the VF2 algorithm, examining both syntactic and semantic
178 /// graph isomorphism (graph structure and matching node and edge weights).
179 ///
180 /// The graphs should not be multigraphs.
is_isomorphic_matching<N, E, Ty, Ix, F, G>( g0: &Graph<N, E, Ty, Ix>, g1: &Graph<N, E, Ty, Ix>, mut node_match: F, mut edge_match: G, ) -> bool where Ty: EdgeType, Ix: IndexType, F: FnMut(&N, &N) -> bool, G: FnMut(&E, &E) -> bool,181 pub fn is_isomorphic_matching<N, E, Ty, Ix, F, G>(
182 g0: &Graph<N, E, Ty, Ix>,
183 g1: &Graph<N, E, Ty, Ix>,
184 mut node_match: F,
185 mut edge_match: G,
186 ) -> bool
187 where
188 Ty: EdgeType,
189 Ix: IndexType,
190 F: FnMut(&N, &N) -> bool,
191 G: FnMut(&E, &E) -> bool,
192 {
193 if g0.node_count() != g1.node_count() || g0.edge_count() != g1.edge_count() {
194 return false;
195 }
196
197 let mut st = [Vf2State::new(g0), Vf2State::new(g1)];
198 try_match(&mut st, g0, g1, &mut node_match, &mut edge_match).unwrap_or(false)
199 }
200
201 trait SemanticMatcher<T> {
enabled() -> bool202 fn enabled() -> bool;
eq(&mut self, _: &T, _: &T) -> bool203 fn eq(&mut self, _: &T, _: &T) -> bool;
204 }
205
206 struct NoSemanticMatch;
207
208 impl<T> SemanticMatcher<T> for NoSemanticMatch {
209 #[inline]
enabled() -> bool210 fn enabled() -> bool {
211 false
212 }
213 #[inline]
eq(&mut self, _: &T, _: &T) -> bool214 fn eq(&mut self, _: &T, _: &T) -> bool {
215 true
216 }
217 }
218
219 impl<T, F> SemanticMatcher<T> for F
220 where
221 F: FnMut(&T, &T) -> bool,
222 {
223 #[inline]
enabled() -> bool224 fn enabled() -> bool {
225 true
226 }
227 #[inline]
eq(&mut self, a: &T, b: &T) -> bool228 fn eq(&mut self, a: &T, b: &T) -> bool {
229 self(a, b)
230 }
231 }
232
233 /// Return Some(bool) if isomorphism is decided, else None.
try_match<N, E, Ty, Ix, F, G>( mut st: &mut [Vf2State<Ty, Ix>; 2], g0: &Graph<N, E, Ty, Ix>, g1: &Graph<N, E, Ty, Ix>, node_match: &mut F, edge_match: &mut G, ) -> Option<bool> where Ty: EdgeType, Ix: IndexType, F: SemanticMatcher<N>, G: SemanticMatcher<E>,234 fn try_match<N, E, Ty, Ix, F, G>(
235 mut st: &mut [Vf2State<Ty, Ix>; 2],
236 g0: &Graph<N, E, Ty, Ix>,
237 g1: &Graph<N, E, Ty, Ix>,
238 node_match: &mut F,
239 edge_match: &mut G,
240 ) -> Option<bool>
241 where
242 Ty: EdgeType,
243 Ix: IndexType,
244 F: SemanticMatcher<N>,
245 G: SemanticMatcher<E>,
246 {
247 if st[0].is_complete() {
248 return Some(true);
249 }
250 let g = [g0, g1];
251 let graph_indices = 0..2;
252 let end = NodeIndex::end();
253
254 // A "depth first" search of a valid mapping from graph 1 to graph 2
255
256 // F(s, n, m) -- evaluate state s and add mapping n <-> m
257
258 // Find least T1out node (in st.out[1] but not in M[1])
259 #[derive(Copy, Clone, PartialEq, Debug)]
260 enum OpenList {
261 Out,
262 In,
263 Other,
264 }
265
266 #[derive(Clone, PartialEq, Debug)]
267 enum Frame<N: marker::Copy> {
268 Outer,
269 Inner { nodes: [N; 2], open_list: OpenList },
270 Unwind { nodes: [N; 2], open_list: OpenList },
271 }
272
273 let next_candidate =
274 |st: &mut [Vf2State<Ty, Ix>; 2]| -> Option<(NodeIndex<Ix>, NodeIndex<Ix>, OpenList)> {
275 let mut to_index;
276 let mut from_index = None;
277 let mut open_list = OpenList::Out;
278 // Try the out list
279 to_index = st[1].next_out_index(0);
280
281 if to_index.is_some() {
282 from_index = st[0].next_out_index(0);
283 open_list = OpenList::Out;
284 }
285 // Try the in list
286 if to_index.is_none() || from_index.is_none() {
287 to_index = st[1].next_in_index(0);
288
289 if to_index.is_some() {
290 from_index = st[0].next_in_index(0);
291 open_list = OpenList::In;
292 }
293 }
294 // Try the other list -- disconnected graph
295 if to_index.is_none() || from_index.is_none() {
296 to_index = st[1].next_rest_index(0);
297 if to_index.is_some() {
298 from_index = st[0].next_rest_index(0);
299 open_list = OpenList::Other;
300 }
301 }
302 match (from_index, to_index) {
303 (Some(n), Some(m)) => Some((NodeIndex::new(n), NodeIndex::new(m), open_list)),
304 // No more candidates
305 _ => None,
306 }
307 };
308 let next_from_ix = |st: &mut [Vf2State<Ty, Ix>; 2],
309 nx: NodeIndex<Ix>,
310 open_list: OpenList|
311 -> Option<NodeIndex<Ix>> {
312 // Find the next node index to try on the `from` side of the mapping
313 let start = nx.index() + 1;
314 let cand0 = match open_list {
315 OpenList::Out => st[0].next_out_index(start),
316 OpenList::In => st[0].next_in_index(start),
317 OpenList::Other => st[0].next_rest_index(start),
318 }
319 .map(|c| c + start); // compensate for start offset.
320 match cand0 {
321 None => None, // no more candidates
322 Some(ix) => {
323 debug_assert!(ix >= start);
324 Some(NodeIndex::new(ix))
325 }
326 }
327 };
328 //fn pop_state(nodes: [NodeIndex<Ix>; 2]) {
329 let pop_state = |st: &mut [Vf2State<Ty, Ix>; 2], nodes: [NodeIndex<Ix>; 2]| {
330 // Restore state.
331 for j in graph_indices.clone() {
332 st[j].pop_mapping(nodes[j], g[j]);
333 }
334 };
335 //fn push_state(nodes: [NodeIndex<Ix>; 2]) {
336 let push_state = |st: &mut [Vf2State<Ty, Ix>; 2], nodes: [NodeIndex<Ix>; 2]| {
337 // Add mapping nx <-> mx to the state
338 for j in graph_indices.clone() {
339 st[j].push_mapping(nodes[j], nodes[1 - j], g[j]);
340 }
341 };
342 //fn is_feasible(nodes: [NodeIndex<Ix>; 2]) -> bool {
343 let mut is_feasible = |st: &mut [Vf2State<Ty, Ix>; 2], nodes: [NodeIndex<Ix>; 2]| -> bool {
344 // Check syntactic feasibility of mapping by ensuring adjacencies
345 // of nx map to adjacencies of mx.
346 //
347 // nx == map to => mx
348 //
349 // R_succ
350 //
351 // Check that every neighbor of nx is mapped to a neighbor of mx,
352 // then check the reverse, from mx to nx. Check that they have the same
353 // count of edges.
354 //
355 // Note: We want to check the lookahead measures here if we can,
356 // R_out: Equal for G0, G1: Card(Succ(G, n) ^ Tout); for both Succ and Pred
357 // R_in: Same with Tin
358 // R_new: Equal for G0, G1: Ñ n Pred(G, n); both Succ and Pred,
359 // Ñ is G0 - M - Tin - Tout
360 // last attempt to add these did not speed up any of the testcases
361 let mut succ_count = [0, 0];
362 for j in graph_indices.clone() {
363 for n_neigh in g[j].neighbors(nodes[j]) {
364 succ_count[j] += 1;
365 // handle the self loop case; it's not in the mapping (yet)
366 let m_neigh = if nodes[j] != n_neigh {
367 st[j].mapping[n_neigh.index()]
368 } else {
369 nodes[1 - j]
370 };
371 if m_neigh == end {
372 continue;
373 }
374 let has_edge =
375 g[1 - j].is_adjacent(&st[1 - j].adjacency_matrix, nodes[1 - j], m_neigh);
376 if !has_edge {
377 return false;
378 }
379 }
380 }
381 if succ_count[0] != succ_count[1] {
382 return false;
383 }
384 // R_pred
385 if g[0].is_directed() {
386 let mut pred_count = [0, 0];
387 for j in graph_indices.clone() {
388 for n_neigh in g[j].neighbors_directed(nodes[j], Incoming) {
389 pred_count[j] += 1;
390 // the self loop case is handled in outgoing
391 let m_neigh = st[j].mapping[n_neigh.index()];
392 if m_neigh == end {
393 continue;
394 }
395 let has_edge =
396 g[1 - j].is_adjacent(&st[1 - j].adjacency_matrix, m_neigh, nodes[1 - j]);
397 if !has_edge {
398 return false;
399 }
400 }
401 }
402 if pred_count[0] != pred_count[1] {
403 return false;
404 }
405 }
406 // semantic feasibility: compare associated data for nodes
407 if F::enabled() && !node_match.eq(&g[0][nodes[0]], &g[1][nodes[1]]) {
408 return false;
409 }
410 // semantic feasibility: compare associated data for edges
411 if G::enabled() {
412 // outgoing edges
413 for j in graph_indices.clone() {
414 let mut edges = g[j].neighbors(nodes[j]).detach();
415 while let Some((n_edge, n_neigh)) = edges.next(g[j]) {
416 // handle the self loop case; it's not in the mapping (yet)
417 let m_neigh = if nodes[j] != n_neigh {
418 st[j].mapping[n_neigh.index()]
419 } else {
420 nodes[1 - j]
421 };
422 if m_neigh == end {
423 continue;
424 }
425 match g[1 - j].find_edge(nodes[1 - j], m_neigh) {
426 Some(m_edge) => {
427 if !edge_match.eq(&g[j][n_edge], &g[1 - j][m_edge]) {
428 return false;
429 }
430 }
431 None => unreachable!(), // covered by syntactic check
432 }
433 }
434 }
435 // incoming edges
436 if g[0].is_directed() {
437 for j in graph_indices.clone() {
438 let mut edges = g[j].neighbors_directed(nodes[j], Incoming).detach();
439 while let Some((n_edge, n_neigh)) = edges.next(g[j]) {
440 // the self loop case is handled in outgoing
441 let m_neigh = st[j].mapping[n_neigh.index()];
442 if m_neigh == end {
443 continue;
444 }
445 match g[1 - j].find_edge(m_neigh, nodes[1 - j]) {
446 Some(m_edge) => {
447 if !edge_match.eq(&g[j][n_edge], &g[1 - j][m_edge]) {
448 return false;
449 }
450 }
451 None => unreachable!(), // covered by syntactic check
452 }
453 }
454 }
455 }
456 }
457 true
458 };
459 let mut stack: Vec<Frame<NodeIndex<Ix>>> = vec![Frame::Outer];
460
461 while let Some(frame) = stack.pop() {
462 match frame {
463 Frame::Unwind {
464 nodes,
465 open_list: ol,
466 } => {
467 pop_state(&mut st, nodes);
468
469 match next_from_ix(&mut st, nodes[0], ol) {
470 None => continue,
471 Some(nx) => {
472 let f = Frame::Inner {
473 nodes: [nx, nodes[1]],
474 open_list: ol,
475 };
476 stack.push(f);
477 }
478 }
479 }
480 Frame::Outer => match next_candidate(&mut st) {
481 None => continue,
482 Some((nx, mx, ol)) => {
483 let f = Frame::Inner {
484 nodes: [nx, mx],
485 open_list: ol,
486 };
487 stack.push(f);
488 }
489 },
490 Frame::Inner {
491 nodes,
492 open_list: ol,
493 } => {
494 if is_feasible(&mut st, nodes) {
495 push_state(&mut st, nodes);
496 if st[0].is_complete() {
497 return Some(true);
498 }
499 // Check cardinalities of Tin, Tout sets
500 if st[0].out_size == st[1].out_size && st[0].ins_size == st[1].ins_size {
501 let f0 = Frame::Unwind {
502 nodes,
503 open_list: ol,
504 };
505 stack.push(f0);
506 stack.push(Frame::Outer);
507 continue;
508 }
509 pop_state(&mut st, nodes);
510 }
511 match next_from_ix(&mut st, nodes[0], ol) {
512 None => continue,
513 Some(nx) => {
514 let f = Frame::Inner {
515 nodes: [nx, nodes[1]],
516 open_list: ol,
517 };
518 stack.push(f);
519 }
520 }
521 }
522 }
523 }
524 None
525 }
526