petgraph/algo/
isomorphism.rs

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    // TODO: make mapping generic over the index type of the other graph.
25    pub struct Vf2State<'a, G: GetAdjacencyMatrix> {
26        /// A reference to the graph this state was built from.
27        pub graph: &'a G,
28        /// The current mapping M(s) of nodes from G0 → G1 and G1 → G0,
29        /// `usize::MAX` for no mapping.
30        pub mapping: Vec<usize>,
31        /// out[i] is non-zero if i is in either M_0(s) or Tout_0(s)
32        /// These are all the next vertices that are not mapped yet, but
33        /// have an outgoing edge from the mapping.
34        out: Vec<usize>,
35        /// ins[i] is non-zero if i is in either M_0(s) or Tin_0(s)
36        /// These are all the incoming vertices, those not mapped yet, but
37        /// have an edge from them into the mapping.
38        /// Unused if graph is undirected -- it's identical with out in that case.
39        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        /// Return **true** if we have a complete mapping
65        pub fn is_complete(&self) -> bool {
66            self.generation == self.mapping.len()
67        }
68
69        /// Add mapping **from** <-> **to** to the state.
70        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            // update T0 & T1 ins/outs
74            // T0out: Node in G0 not in M0 but successor of a node in M0.
75            // st.out[0]: Node either in M0 or successor of M0
76            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        /// Restore the state to before the last added mapping
93        pub fn pop_mapping(&mut self, from: G::NodeId) {
94            // undo (n, m) mapping
95            self.mapping[self.graph.to_index(from)] = usize::MAX;
96
97            // unmark in ins and outs
98            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        /// Find the next (least) node in the Tout set.
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] == usize::MAX
123                })
124                .map(|(index, _)| index)
125        }
126
127        /// Find the next (least) node in the Tin set.
128        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        /// Find the next (least) node in the N - M set.
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 == 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                    // handle the self loop case; it's not in the mapping (yet)
319                    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                    // the self loop case is handled in outgoing
349                    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        // Check syntactic feasibility of mapping by ensuring adjacencies
367        // of nx map to adjacencies of mx.
368        //
369        // nx == map to => mx
370        //
371        // R_succ
372        //
373        // Check that every neighbor of nx is mapped to a neighbor of mx,
374        // then check the reverse, from mx to nx. Check that they have the same
375        // count of edges.
376        //
377        // Note: We want to check the lookahead measures here if we can,
378        // R_out: Equal for G0, G1: Card(Succ(G, n) ^ Tout); for both Succ and Pred
379        // R_in: Same with Tin
380        // R_new: Equal for G0, G1: Ñ n Pred(G, n); both Succ and Pred,
381        //      Ñ is G0 - M - Tin - Tout
382        // last attempt to add these did not speed up any of the testcases
383        if r_succ!(0) > r_succ!(1) {
384            return false;
385        }
386        // R_pred
387        if st.0.graph.is_directed() && r_pred!(0) > r_pred!(1) {
388            return false;
389        }
390
391        // // semantic feasibility: compare associated data for nodes
392        if NM::enabled() && !node_match.eq(st.0.graph, st.1.graph, nodes.0, nodes.1) {
393            return false;
394        }
395        // semantic feasibility: compare associated data for edges
396        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                            // the self loop case is handled in outgoing
433                            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        // Try the out list
476        if to_index.is_some() {
477            from_index = st.0.next_out_index(0);
478            open_list = OpenList::Out;
479        }
480        // Try the in list
481        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        // Try the other list -- disconnected graph
490        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            // No more candidates
504            _ => 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        // Find the next node index to try on the `to` side of the mapping
518        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); // compensate for start offset.
525        match cand1 {
526            None => None, // no more candidates
527            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    // Note: This function will not find the empty isomorphism (i.e., if g0 is the empty graph).
557    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        // A "depth first" search of a valid mapping from graph 1 to graph 2
579        // F(s, n, m) -- evaluate state s and add mapping n <-> m
580        // Find least T1out node (in st.out[1] but not in M[1])
581        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                        // Check cardinalities of Tin, Tout sets
615                        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        // if this is `Some(iter)` we're overriding any calls to `isomorphisms()` with calls to `iter` instead. that is, we return the single known mapping once.
669        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                // the initial state is already complete. if this is the case, need to return the mapping immediately, because `next_candidate` in Frame::Outer will not succeed.
698                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                // if we are overriding calls to `isomorphisms`, we return the mapping once
733                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            // To calculate the upper bound of results we use n! where n is the
746            // number of nodes in graph 1. n! values fit into a 64-bit usize up
747            // to n = 20, so we don't estimate an upper limit for n > 20.
748            let n = self.st.0.graph.node_count();
749
750            // We hardcode n! values into an array that accounts for architectures
751            // with smaller usizes to get our upper bound.
752            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
788/// Return `true` if the graphs `g0` and `g1` are isomorphic.
789///
790/// Using the VF2 algorithm, only matching graph syntactically (graph
791/// structure).
792///
793/// The graphs should not be [multigraphs].
794///
795/// **Reference**
796///
797/// * Luigi P. Cordella, Pasquale Foggia, Carlo Sansone, Mario Vento;
798///   *A (Sub)Graph Isomorphism Algorithm for Matching Large Graphs*
799///
800/// [multigraphs]: https://en.wikipedia.org/wiki/Multigraph
801pub 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
819/// Return `true` if the graphs `g0` and `g1` are isomorphic.
820///
821/// Using the VF2 algorithm, examining both syntactic and semantic
822/// graph isomorphism (graph structure and matching node and edge weights).
823///
824/// The graphs should not be [multigraphs].
825///
826/// [multigraphs]: https://en.wikipedia.org/wiki/Multigraph
827pub 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
858/// Return `true` if `g0` is isomorphic to a subgraph of `g1`.
859///
860/// Using the VF2 algorithm, only matching graph syntactically (graph
861/// structure).
862///
863/// The graphs should not be [multigraphs].
864///
865/// # Subgraph isomorphism
866///
867/// (adapted from [`networkx` documentation][networkx_vf2])
868///
869/// Graph theory literature can be ambiguous about the meaning of the above statement,
870/// and we seek to clarify it now.
871///
872/// In the VF2 literature, a mapping **M** is said to be a *graph-subgraph isomorphism*
873/// iff **M** is an isomorphism between **G2** and a subgraph of **G1**. Thus, to say
874/// that **G1** and **G2** are graph-subgraph isomorphic is to say that a subgraph of
875/// **G1** is isomorphic to **G2**.
876///
877/// Other literature uses the phrase ‘subgraph isomorphic’ as in
878/// ‘**G1** does not have a subgraph isomorphic to **G2**’. Another use is as an in adverb
879/// for isomorphic. Thus, to say that **G1** and **G2** are subgraph isomorphic is to say
880/// that a subgraph of **G1** is isomorphic to **G2**.
881///
882/// Finally, the term ‘subgraph’ can have multiple meanings. In this context,
883/// ‘subgraph’ always means a ‘node-induced subgraph’. Edge-induced subgraph
884/// isomorphisms are not directly supported. For subgraphs which are not
885/// induced, the term ‘monomorphism’ is preferred over ‘isomorphism’.
886///
887/// **Reference**
888///
889/// * Luigi P. Cordella, Pasquale Foggia, Carlo Sansone, Mario Vento;
890///   *A (Sub)Graph Isomorphism Algorithm for Matching Large Graphs*
891///
892/// [networkx_vf2]: https://networkx.github.io/documentation/stable/reference/algorithms/isomorphism.vf2.html
893/// [multigraphs]: https://en.wikipedia.org/wiki/Multigraph
894pub 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
912/// Return `true` if `g0` is isomorphic to a subgraph of `g1`.
913///
914/// Using the VF2 algorithm, examining both syntactic and semantic
915/// graph isomorphism (graph structure and matching node and edge weights).
916///
917/// The graphs should not be [multigraphs].
918///
919/// [multigraphs]: https://en.wikipedia.org/wiki/Multigraph
920pub 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
951/// Using the VF2 algorithm, examine both syntactic and semantic graph
952/// isomorphism (graph structure and matching node and edge weights) and,
953/// if `g0` is isomorphic to a subgraph of `g1`, return the mappings between
954/// them.
955///
956/// The graphs should not be [multigraphs].
957///
958/// [multigraphs]: https://en.wikipedia.org/wiki/Multigraph
959pub 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}