1use alloc::{vec, vec::Vec};
2use core::convert::TryFrom;
3
4use crate::data::DataMap;
5use crate::visit::EdgeCount;
6use crate::visit::EdgeRef;
7use crate::visit::GetAdjacencyMatrix;
8use crate::visit::GraphBase;
9use crate::visit::GraphProp;
10use crate::visit::IntoEdgesDirected;
11use crate::visit::IntoNeighborsDirected;
12use crate::visit::NodeCompactIndexable;
13use crate::{Incoming, Outgoing};
14
15use self::semantic::EdgeMatcher;
16use self::semantic::NoSemanticMatch;
17use self::semantic::NodeMatcher;
18use self::state::Vf2State;
19
20mod state {
21 use super::*;
22
23 #[derive(Debug)]
24 pub struct Vf2State<'a, G: GetAdjacencyMatrix> {
26 pub graph: &'a G,
28 pub mapping: Vec<usize>,
31 out: Vec<usize>,
35 ins: Vec<usize>,
40 pub out_size: usize,
41 pub ins_size: usize,
42 pub adjacency_matrix: G::AdjMatrix,
43 generation: usize,
44 }
45
46 impl<'a, G> Vf2State<'a, G>
47 where
48 G: GetAdjacencyMatrix + GraphProp + NodeCompactIndexable + IntoNeighborsDirected,
49 {
50 pub fn new(g: &'a G) -> Self {
51 let c0 = g.node_count();
52 Vf2State {
53 graph: g,
54 mapping: vec![usize::MAX; c0],
55 out: vec![0; c0],
56 ins: vec![0; c0 * (g.is_directed() as usize)],
57 out_size: 0,
58 ins_size: 0,
59 adjacency_matrix: g.adjacency_matrix(),
60 generation: 0,
61 }
62 }
63
64 pub fn is_complete(&self) -> bool {
66 self.generation == self.mapping.len()
67 }
68
69 pub fn push_mapping(&mut self, from: G::NodeId, to: usize) {
71 self.generation += 1;
72 self.mapping[self.graph.to_index(from)] = to;
73 for ix in self.graph.neighbors_directed(from, Outgoing) {
77 if self.out[self.graph.to_index(ix)] == 0 {
78 self.out[self.graph.to_index(ix)] = self.generation;
79 self.out_size += 1;
80 }
81 }
82 if self.graph.is_directed() {
83 for ix in self.graph.neighbors_directed(from, Incoming) {
84 if self.ins[self.graph.to_index(ix)] == 0 {
85 self.ins[self.graph.to_index(ix)] = self.generation;
86 self.ins_size += 1;
87 }
88 }
89 }
90 }
91
92 pub fn pop_mapping(&mut self, from: G::NodeId) {
94 self.mapping[self.graph.to_index(from)] = usize::MAX;
96
97 for ix in self.graph.neighbors_directed(from, Outgoing) {
99 if self.out[self.graph.to_index(ix)] == self.generation {
100 self.out[self.graph.to_index(ix)] = 0;
101 self.out_size -= 1;
102 }
103 }
104 if self.graph.is_directed() {
105 for ix in self.graph.neighbors_directed(from, Incoming) {
106 if self.ins[self.graph.to_index(ix)] == self.generation {
107 self.ins[self.graph.to_index(ix)] = 0;
108 self.ins_size -= 1;
109 }
110 }
111 }
112
113 self.generation -= 1;
114 }
115
116 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] == usize::MAX
123 })
124 .map(|(index, _)| index)
125 }
126
127 pub fn next_in_index(&self, from_index: usize) -> Option<usize> {
129 if !self.graph.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] == usize::MAX
137 })
138 .map(|(index, _)| index)
139 }
140
141 pub fn next_rest_index(&self, from_index: usize) -> Option<usize> {
143 self.mapping[from_index..]
144 .iter()
145 .enumerate()
146 .find(|&(_, &elt)| elt == usize::MAX)
147 .map(|(index, _)| index)
148 }
149 }
150}
151
152mod semantic {
153 use super::*;
154
155 pub struct NoSemanticMatch;
156
157 pub trait NodeMatcher<G0: GraphBase, G1: GraphBase> {
158 fn enabled() -> bool;
159 fn eq(&mut self, _g0: &G0, _g1: &G1, _n0: G0::NodeId, _n1: G1::NodeId) -> bool;
160 }
161
162 impl<G0: GraphBase, G1: GraphBase> NodeMatcher<G0, G1> for NoSemanticMatch {
163 #[inline]
164 fn enabled() -> bool {
165 false
166 }
167 #[inline]
168 fn eq(&mut self, _g0: &G0, _g1: &G1, _n0: G0::NodeId, _n1: G1::NodeId) -> bool {
169 true
170 }
171 }
172
173 impl<G0, G1, F> NodeMatcher<G0, G1> for F
174 where
175 G0: GraphBase + DataMap,
176 G1: GraphBase + DataMap,
177 F: FnMut(&G0::NodeWeight, &G1::NodeWeight) -> bool,
178 {
179 #[inline]
180 fn enabled() -> bool {
181 true
182 }
183 #[inline]
184 fn eq(&mut self, g0: &G0, g1: &G1, n0: G0::NodeId, n1: G1::NodeId) -> bool {
185 if let (Some(x), Some(y)) = (g0.node_weight(n0), g1.node_weight(n1)) {
186 self(x, y)
187 } else {
188 false
189 }
190 }
191 }
192
193 pub trait EdgeMatcher<G0: GraphBase, G1: GraphBase> {
194 fn enabled() -> bool;
195 fn eq(
196 &mut self,
197 _g0: &G0,
198 _g1: &G1,
199 e0: (G0::NodeId, G0::NodeId),
200 e1: (G1::NodeId, G1::NodeId),
201 ) -> bool;
202 }
203
204 impl<G0: GraphBase, G1: GraphBase> EdgeMatcher<G0, G1> for NoSemanticMatch {
205 #[inline]
206 fn enabled() -> bool {
207 false
208 }
209 #[inline]
210 fn eq(
211 &mut self,
212 _g0: &G0,
213 _g1: &G1,
214 _e0: (G0::NodeId, G0::NodeId),
215 _e1: (G1::NodeId, G1::NodeId),
216 ) -> bool {
217 true
218 }
219 }
220
221 impl<G0, G1, F> EdgeMatcher<G0, G1> for F
222 where
223 G0: GraphBase + DataMap + IntoEdgesDirected,
224 G1: GraphBase + DataMap + IntoEdgesDirected,
225 F: FnMut(&G0::EdgeWeight, &G1::EdgeWeight) -> bool,
226 {
227 #[inline]
228 fn enabled() -> bool {
229 true
230 }
231 #[inline]
232 fn eq(
233 &mut self,
234 g0: &G0,
235 g1: &G1,
236 e0: (G0::NodeId, G0::NodeId),
237 e1: (G1::NodeId, G1::NodeId),
238 ) -> bool {
239 let w0 = g0
240 .edges_directed(e0.0, Outgoing)
241 .find(|edge| edge.target() == e0.1)
242 .and_then(|edge| g0.edge_weight(edge.id()));
243 let w1 = g1
244 .edges_directed(e1.0, Outgoing)
245 .find(|edge| edge.target() == e1.1)
246 .and_then(|edge| g1.edge_weight(edge.id()));
247 if let (Some(x), Some(y)) = (w0, w1) {
248 self(x, y)
249 } else {
250 false
251 }
252 }
253 }
254}
255
256mod matching {
257 use super::*;
258
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<G0, G1>
268 where
269 G0: GraphBase,
270 G1: GraphBase,
271 {
272 Outer,
273 Inner {
274 nodes: (G0::NodeId, G1::NodeId),
275 open_list: OpenList,
276 },
277 Unwind {
278 nodes: (G0::NodeId, G1::NodeId),
279 open_list: OpenList,
280 },
281 }
282
283 fn is_feasible<G0, G1, NM, EM>(
284 st: &mut (Vf2State<'_, G0>, Vf2State<'_, G1>),
285 nodes: (G0::NodeId, G1::NodeId),
286 node_match: &mut NM,
287 edge_match: &mut EM,
288 ) -> bool
289 where
290 G0: GetAdjacencyMatrix + GraphProp + NodeCompactIndexable + IntoNeighborsDirected,
291 G1: GetAdjacencyMatrix + GraphProp + NodeCompactIndexable + IntoNeighborsDirected,
292 NM: NodeMatcher<G0, G1>,
293 EM: EdgeMatcher<G0, G1>,
294 {
295 macro_rules! field {
296 ($x:ident, 0) => {
297 $x.0
298 };
299 ($x:ident, 1) => {
300 $x.1
301 };
302 ($x:ident, 1 - 0) => {
303 $x.1
304 };
305 ($x:ident, 1 - 1) => {
306 $x.0
307 };
308 }
309
310 macro_rules! r_succ {
311 ($j:tt) => {{
312 let mut succ_count = 0;
313 for n_neigh in field!(st, $j)
314 .graph
315 .neighbors_directed(field!(nodes, $j), Outgoing)
316 {
317 succ_count += 1;
318 let m_neigh = if field!(nodes, $j) != n_neigh {
320 field!(st, $j).mapping[field!(st, $j).graph.to_index(n_neigh)]
321 } else {
322 field!(st, 1 - $j).graph.to_index(field!(nodes, 1 - $j))
323 };
324 if m_neigh == usize::MAX {
325 continue;
326 }
327 let has_edge = field!(st, 1 - $j).graph.is_adjacent(
328 &field!(st, 1 - $j).adjacency_matrix,
329 field!(nodes, 1 - $j),
330 field!(st, 1 - $j).graph.from_index(m_neigh),
331 );
332 if !has_edge {
333 return false;
334 }
335 }
336 succ_count
337 }};
338 }
339
340 macro_rules! r_pred {
341 ($j:tt) => {{
342 let mut pred_count = 0;
343 for n_neigh in field!(st, $j)
344 .graph
345 .neighbors_directed(field!(nodes, $j), Incoming)
346 {
347 pred_count += 1;
348 let m_neigh = field!(st, $j).mapping[field!(st, $j).graph.to_index(n_neigh)];
350 if m_neigh == usize::MAX {
351 continue;
352 }
353 let has_edge = field!(st, 1 - $j).graph.is_adjacent(
354 &field!(st, 1 - $j).adjacency_matrix,
355 field!(st, 1 - $j).graph.from_index(m_neigh),
356 field!(nodes, 1 - $j),
357 );
358 if !has_edge {
359 return false;
360 }
361 }
362 pred_count
363 }};
364 }
365
366 if r_succ!(0) > r_succ!(1) {
384 return false;
385 }
386 if st.0.graph.is_directed() && r_pred!(0) > r_pred!(1) {
388 return false;
389 }
390
391 if NM::enabled() && !node_match.eq(st.0.graph, st.1.graph, nodes.0, nodes.1) {
393 return false;
394 }
395 if EM::enabled() {
397 macro_rules! edge_feasibility {
398 ($j:tt) => {{
399 for n_neigh in field!(st, $j)
400 .graph
401 .neighbors_directed(field!(nodes, $j), Outgoing)
402 {
403 let m_neigh = if field!(nodes, $j) != n_neigh {
404 field!(st, $j).mapping[field!(st, $j).graph.to_index(n_neigh)]
405 } else {
406 field!(st, 1 - $j).graph.to_index(field!(nodes, 1 - $j))
407 };
408 if m_neigh == usize::MAX {
409 continue;
410 }
411
412 let e0 = (field!(nodes, $j), n_neigh);
413 let e1 = (
414 field!(nodes, 1 - $j),
415 field!(st, 1 - $j).graph.from_index(m_neigh),
416 );
417 let edges = (e0, e1);
418 if !edge_match.eq(
419 st.0.graph,
420 st.1.graph,
421 field!(edges, $j),
422 field!(edges, 1 - $j),
423 ) {
424 return false;
425 }
426 }
427 if field!(st, $j).graph.is_directed() {
428 for n_neigh in field!(st, $j)
429 .graph
430 .neighbors_directed(field!(nodes, $j), Incoming)
431 {
432 let m_neigh =
434 field!(st, $j).mapping[field!(st, $j).graph.to_index(n_neigh)];
435 if m_neigh == usize::MAX {
436 continue;
437 }
438
439 let e0 = (n_neigh, field!(nodes, $j));
440 let e1 = (
441 field!(st, 1 - $j).graph.from_index(m_neigh),
442 field!(nodes, 1 - $j),
443 );
444 let edges = (e0, e1);
445 if !edge_match.eq(
446 st.0.graph,
447 st.1.graph,
448 field!(edges, $j),
449 field!(edges, 1 - $j),
450 ) {
451 return false;
452 }
453 }
454 }
455 }};
456 }
457
458 edge_feasibility!(0);
459 edge_feasibility!(1);
460 }
461 true
462 }
463
464 fn next_candidate<G0, G1>(
465 st: &mut (Vf2State<'_, G0>, Vf2State<'_, G1>),
466 ) -> Option<(G0::NodeId, G1::NodeId, OpenList)>
467 where
468 G0: GetAdjacencyMatrix + GraphProp + NodeCompactIndexable + IntoNeighborsDirected,
469 G1: GetAdjacencyMatrix + GraphProp + NodeCompactIndexable + IntoNeighborsDirected,
470 {
471 let mut from_index = None;
472 let mut open_list = OpenList::Out;
473 let mut to_index = st.1.next_out_index(0);
474
475 if to_index.is_some() {
477 from_index = st.0.next_out_index(0);
478 open_list = OpenList::Out;
479 }
480 if to_index.is_none() || from_index.is_none() {
482 to_index = st.1.next_in_index(0);
483
484 if to_index.is_some() {
485 from_index = st.0.next_in_index(0);
486 open_list = OpenList::In;
487 }
488 }
489 if to_index.is_none() || from_index.is_none() {
491 to_index = st.1.next_rest_index(0);
492 if to_index.is_some() {
493 from_index = st.0.next_rest_index(0);
494 open_list = OpenList::Other;
495 }
496 }
497 match (from_index, to_index) {
498 (Some(n), Some(m)) => Some((
499 st.0.graph.from_index(n),
500 st.1.graph.from_index(m),
501 open_list,
502 )),
503 _ => None,
505 }
506 }
507
508 fn next_from_ix<G0, G1>(
509 st: &mut (Vf2State<'_, G0>, Vf2State<'_, G1>),
510 nx: G1::NodeId,
511 open_list: OpenList,
512 ) -> Option<G1::NodeId>
513 where
514 G0: GetAdjacencyMatrix + GraphProp + NodeCompactIndexable + IntoNeighborsDirected,
515 G1: GetAdjacencyMatrix + GraphProp + NodeCompactIndexable + IntoNeighborsDirected,
516 {
517 let start = st.1.graph.to_index(nx) + 1;
519 let cand1 = match open_list {
520 OpenList::Out => st.1.next_out_index(start),
521 OpenList::In => st.1.next_in_index(start),
522 OpenList::Other => st.1.next_rest_index(start),
523 }
524 .map(|c| c + start); match cand1 {
526 None => None, Some(ix) => {
528 debug_assert!(ix >= start);
529 Some(st.1.graph.from_index(ix))
530 }
531 }
532 }
533
534 fn pop_state<G0, G1>(
535 st: &mut (Vf2State<'_, G0>, Vf2State<'_, G1>),
536 nodes: (G0::NodeId, G1::NodeId),
537 ) where
538 G0: GetAdjacencyMatrix + GraphProp + NodeCompactIndexable + IntoNeighborsDirected,
539 G1: GetAdjacencyMatrix + GraphProp + NodeCompactIndexable + IntoNeighborsDirected,
540 {
541 st.0.pop_mapping(nodes.0);
542 st.1.pop_mapping(nodes.1);
543 }
544
545 fn push_state<G0, G1>(
546 st: &mut (Vf2State<'_, G0>, Vf2State<'_, G1>),
547 nodes: (G0::NodeId, G1::NodeId),
548 ) where
549 G0: GetAdjacencyMatrix + GraphProp + NodeCompactIndexable + IntoNeighborsDirected,
550 G1: GetAdjacencyMatrix + GraphProp + NodeCompactIndexable + IntoNeighborsDirected,
551 {
552 st.0.push_mapping(nodes.0, st.1.graph.to_index(nodes.1));
553 st.1.push_mapping(nodes.1, st.0.graph.to_index(nodes.0));
554 }
555
556 fn isomorphisms<G0, G1, NM, EM>(
558 st: &mut (Vf2State<'_, G0>, Vf2State<'_, G1>),
559 node_match: &mut NM,
560 edge_match: &mut EM,
561 match_subgraph: bool,
562 stack: &mut Vec<Frame<G0, G1>>,
563 ) -> Option<Vec<usize>>
564 where
565 G0: NodeCompactIndexable
566 + EdgeCount
567 + GetAdjacencyMatrix
568 + GraphProp
569 + IntoNeighborsDirected,
570 G1: NodeCompactIndexable
571 + EdgeCount
572 + GetAdjacencyMatrix
573 + GraphProp
574 + IntoNeighborsDirected,
575 NM: NodeMatcher<G0, G1>,
576 EM: EdgeMatcher<G0, G1>,
577 {
578 let mut result = None;
582 while let Some(frame) = stack.pop() {
583 match frame {
584 Frame::Unwind { nodes, open_list } => {
585 pop_state(st, nodes);
586
587 match next_from_ix(st, nodes.1, open_list) {
588 None => continue,
589 Some(nx) => {
590 let f = Frame::Inner {
591 nodes: (nodes.0, nx),
592 open_list,
593 };
594 stack.push(f);
595 }
596 }
597 }
598 Frame::Outer => match next_candidate(st) {
599 None => continue,
600 Some((nx, mx, open_list)) => {
601 let f = Frame::Inner {
602 nodes: (nx, mx),
603 open_list,
604 };
605 stack.push(f);
606 }
607 },
608 Frame::Inner { nodes, open_list } => {
609 if is_feasible(st, nodes, node_match, edge_match) {
610 push_state(st, nodes);
611 if st.0.is_complete() {
612 result = Some(st.0.mapping.clone());
613 }
614 if (!match_subgraph
616 && st.0.out_size == st.1.out_size
617 && st.0.ins_size == st.1.ins_size)
618 || (match_subgraph
619 && st.0.out_size <= st.1.out_size
620 && st.0.ins_size <= st.1.ins_size)
621 {
622 let f0 = Frame::Unwind { nodes, open_list };
623 stack.push(f0);
624 stack.push(Frame::Outer);
625 continue;
626 }
627 pop_state(st, nodes);
628 }
629 match next_from_ix(st, nodes.1, open_list) {
630 None => continue,
631 Some(nx) => {
632 let f = Frame::Inner {
633 nodes: (nodes.0, nx),
634 open_list,
635 };
636 stack.push(f);
637 }
638 }
639 }
640 }
641 if result.is_some() {
642 return result;
643 }
644 }
645 result
646 }
647
648 pub struct GraphMatcher<'a, 'b, 'c, G0, G1, NM, EM>
649 where
650 G0: NodeCompactIndexable
651 + EdgeCount
652 + GetAdjacencyMatrix
653 + GraphProp
654 + IntoNeighborsDirected,
655 G1: NodeCompactIndexable
656 + EdgeCount
657 + GetAdjacencyMatrix
658 + GraphProp
659 + IntoNeighborsDirected,
660 NM: NodeMatcher<G0, G1>,
661 EM: EdgeMatcher<G0, G1>,
662 {
663 st: (Vf2State<'a, G0>, Vf2State<'b, G1>),
664 node_match: &'c mut NM,
665 edge_match: &'c mut EM,
666 match_subgraph: bool,
667 stack: Vec<Frame<G0, G1>>,
668 iter_override: Option<Option<Vec<usize>>>,
670 }
671
672 impl<'a, 'b, 'c, G0, G1, NM, EM> GraphMatcher<'a, 'b, 'c, G0, G1, NM, EM>
673 where
674 G0: NodeCompactIndexable
675 + EdgeCount
676 + GetAdjacencyMatrix
677 + GraphProp
678 + IntoNeighborsDirected,
679 G1: NodeCompactIndexable
680 + EdgeCount
681 + GetAdjacencyMatrix
682 + GraphProp
683 + IntoNeighborsDirected,
684 NM: NodeMatcher<G0, G1>,
685 EM: EdgeMatcher<G0, G1>,
686 {
687 pub fn new(
688 g0: &'a G0,
689 g1: &'b G1,
690 node_match: &'c mut NM,
691 edge_match: &'c mut EM,
692 match_subgraph: bool,
693 ) -> Self {
694 let stack = vec![Frame::Outer];
695 let st = (Vf2State::new(g0), Vf2State::new(g1));
696 let iter_override = if st.0.is_complete() {
697 Some(Some(st.0.mapping.clone()))
699 } else {
700 None
701 };
702 Self {
703 st,
704 node_match,
705 edge_match,
706 match_subgraph,
707 stack,
708 iter_override,
709 }
710 }
711 }
712
713 impl<G0, G1, NM, EM> Iterator for GraphMatcher<'_, '_, '_, G0, G1, NM, EM>
714 where
715 G0: NodeCompactIndexable
716 + EdgeCount
717 + GetAdjacencyMatrix
718 + GraphProp
719 + IntoNeighborsDirected,
720 G1: NodeCompactIndexable
721 + EdgeCount
722 + GetAdjacencyMatrix
723 + GraphProp
724 + IntoNeighborsDirected,
725 NM: NodeMatcher<G0, G1>,
726 EM: EdgeMatcher<G0, G1>,
727 {
728 type Item = Vec<usize>;
729
730 fn next(&mut self) -> Option<Self::Item> {
731 if let Some(iter) = self.iter_override.as_mut() {
732 return iter.take();
734 }
735 isomorphisms(
736 &mut self.st,
737 self.node_match,
738 self.edge_match,
739 self.match_subgraph,
740 &mut self.stack,
741 )
742 }
743
744 fn size_hint(&self) -> (usize, Option<usize>) {
745 let n = self.st.0.graph.node_count();
749
750 let upper_bounds: Vec<Option<usize>> = [
753 1u64,
754 1,
755 2,
756 6,
757 24,
758 120,
759 720,
760 5040,
761 40320,
762 362880,
763 3628800,
764 39916800,
765 479001600,
766 6227020800,
767 87178291200,
768 1307674368000,
769 20922789888000,
770 355687428096000,
771 6402373705728000,
772 121645100408832000,
773 2432902008176640000,
774 ]
775 .iter()
776 .map(|n| usize::try_from(*n).ok())
777 .collect();
778
779 if n > upper_bounds.len() {
780 return (0, None);
781 }
782
783 (0, upper_bounds[n])
784 }
785 }
786}
787
788pub fn is_isomorphic<G0, G1>(g0: G0, g1: G1) -> bool
802where
803 G0: NodeCompactIndexable + EdgeCount + GetAdjacencyMatrix + GraphProp + IntoNeighborsDirected,
804 G1: NodeCompactIndexable
805 + EdgeCount
806 + GetAdjacencyMatrix
807 + GraphProp<EdgeType = G0::EdgeType>
808 + IntoNeighborsDirected,
809{
810 if g0.node_count() != g1.node_count() || g0.edge_count() != g1.edge_count() {
811 return false;
812 }
813
814 self::matching::GraphMatcher::new(&g0, &g1, &mut NoSemanticMatch, &mut NoSemanticMatch, false)
815 .next()
816 .is_some()
817}
818
819pub fn is_isomorphic_matching<G0, G1, NM, EM>(
828 g0: G0,
829 g1: G1,
830 mut node_match: NM,
831 mut edge_match: EM,
832) -> bool
833where
834 G0: NodeCompactIndexable
835 + EdgeCount
836 + DataMap
837 + GetAdjacencyMatrix
838 + GraphProp
839 + IntoEdgesDirected,
840 G1: NodeCompactIndexable
841 + EdgeCount
842 + DataMap
843 + GetAdjacencyMatrix
844 + GraphProp<EdgeType = G0::EdgeType>
845 + IntoEdgesDirected,
846 NM: FnMut(&G0::NodeWeight, &G1::NodeWeight) -> bool,
847 EM: FnMut(&G0::EdgeWeight, &G1::EdgeWeight) -> bool,
848{
849 if g0.node_count() != g1.node_count() || g0.edge_count() != g1.edge_count() {
850 return false;
851 }
852
853 self::matching::GraphMatcher::new(&g0, &g1, &mut node_match, &mut edge_match, false)
854 .next()
855 .is_some()
856}
857
858pub fn is_isomorphic_subgraph<G0, G1>(g0: G0, g1: G1) -> bool
895where
896 G0: NodeCompactIndexable + EdgeCount + GetAdjacencyMatrix + GraphProp + IntoNeighborsDirected,
897 G1: NodeCompactIndexable
898 + EdgeCount
899 + GetAdjacencyMatrix
900 + GraphProp<EdgeType = G0::EdgeType>
901 + IntoNeighborsDirected,
902{
903 if g0.node_count() > g1.node_count() || g0.edge_count() > g1.edge_count() {
904 return false;
905 }
906
907 self::matching::GraphMatcher::new(&g0, &g1, &mut NoSemanticMatch, &mut NoSemanticMatch, true)
908 .next()
909 .is_some()
910}
911
912pub fn is_isomorphic_subgraph_matching<G0, G1, NM, EM>(
921 g0: G0,
922 g1: G1,
923 mut node_match: NM,
924 mut edge_match: EM,
925) -> bool
926where
927 G0: NodeCompactIndexable
928 + EdgeCount
929 + DataMap
930 + GetAdjacencyMatrix
931 + GraphProp
932 + IntoEdgesDirected,
933 G1: NodeCompactIndexable
934 + EdgeCount
935 + DataMap
936 + GetAdjacencyMatrix
937 + GraphProp<EdgeType = G0::EdgeType>
938 + IntoEdgesDirected,
939 NM: FnMut(&G0::NodeWeight, &G1::NodeWeight) -> bool,
940 EM: FnMut(&G0::EdgeWeight, &G1::EdgeWeight) -> bool,
941{
942 if g0.node_count() > g1.node_count() || g0.edge_count() > g1.edge_count() {
943 return false;
944 }
945
946 self::matching::GraphMatcher::new(&g0, &g1, &mut node_match, &mut edge_match, true)
947 .next()
948 .is_some()
949}
950
951pub fn subgraph_isomorphisms_iter<'a, G0, G1, NM, EM>(
960 g0: &'a G0,
961 g1: &'a G1,
962 node_match: &'a mut NM,
963 edge_match: &'a mut EM,
964) -> Option<impl Iterator<Item = Vec<usize>> + 'a>
965where
966 G0: 'a
967 + NodeCompactIndexable
968 + EdgeCount
969 + DataMap
970 + GetAdjacencyMatrix
971 + GraphProp
972 + IntoEdgesDirected,
973 G1: 'a
974 + NodeCompactIndexable
975 + EdgeCount
976 + DataMap
977 + GetAdjacencyMatrix
978 + GraphProp<EdgeType = G0::EdgeType>
979 + IntoEdgesDirected,
980 NM: 'a + FnMut(&G0::NodeWeight, &G1::NodeWeight) -> bool,
981 EM: 'a + FnMut(&G0::EdgeWeight, &G1::EdgeWeight) -> bool,
982{
983 if g0.node_count() > g1.node_count() || g0.edge_count() > g1.edge_count() {
984 return None;
985 }
986
987 Some(self::matching::GraphMatcher::new(
988 g0, g1, node_match, edge_match, true,
989 ))
990}