1 use std::convert::TryFrom;
2 
3 use crate::data::DataMap;
4 use crate::visit::EdgeCount;
5 use crate::visit::EdgeRef;
6 use crate::visit::GetAdjacencyMatrix;
7 use crate::visit::GraphBase;
8 use crate::visit::GraphProp;
9 use crate::visit::IntoEdgesDirected;
10 use crate::visit::IntoNeighborsDirected;
11 use crate::visit::NodeCompactIndexable;
12 use crate::{Incoming, Outgoing};
13 
14 use self::semantic::EdgeMatcher;
15 use self::semantic::NoSemanticMatch;
16 use self::semantic::NodeMatcher;
17 use self::state::Vf2State;
18 
19 mod state {
20     use super::*;
21 
22     #[derive(Debug)]
23     // TODO: make mapping generic over the index type of the other graph.
24     pub struct Vf2State<'a, G: GetAdjacencyMatrix> {
25         /// A reference to the graph this state was built from.
26         pub graph: &'a G,
27         /// The current mapping M(s) of nodes from G0 → G1 and G1 → G0,
28         /// `usize::MAX` for no mapping.
29         pub mapping: Vec<usize>,
30         /// out[i] is non-zero if i is in either M_0(s) or Tout_0(s)
31         /// These are all the next vertices that are not mapped yet, but
32         /// have an outgoing edge from the mapping.
33         out: Vec<usize>,
34         /// ins[i] is non-zero if i is in either M_0(s) or Tin_0(s)
35         /// These are all the incoming vertices, those not mapped yet, but
36         /// have an edge from them into the mapping.
37         /// Unused if graph is undirected -- it's identical with out in that case.
38         ins: Vec<usize>,
39         pub out_size: usize,
40         pub ins_size: usize,
41         pub adjacency_matrix: G::AdjMatrix,
42         generation: usize,
43     }
44 
45     impl<'a, G> Vf2State<'a, G>
46     where
47         G: GetAdjacencyMatrix + GraphProp + NodeCompactIndexable + IntoNeighborsDirected,
48     {
new(g: &'a G) -> Self49         pub fn new(g: &'a G) -> Self {
50             let c0 = g.node_count();
51             Vf2State {
52                 graph: g,
53                 mapping: vec![std::usize::MAX; c0],
54                 out: vec![0; c0],
55                 ins: vec![0; c0 * (g.is_directed() as usize)],
56                 out_size: 0,
57                 ins_size: 0,
58                 adjacency_matrix: g.adjacency_matrix(),
59                 generation: 0,
60             }
61         }
62 
63         /// Return **true** if we have a complete mapping
is_complete(&self) -> bool64         pub fn is_complete(&self) -> bool {
65             self.generation == self.mapping.len()
66         }
67 
68         /// Add mapping **from** <-> **to** to the state.
push_mapping(&mut self, from: G::NodeId, to: usize)69         pub fn push_mapping(&mut self, from: G::NodeId, to: usize) {
70             self.generation += 1;
71             self.mapping[self.graph.to_index(from)] = 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 self.graph.neighbors_directed(from, Outgoing) {
76                 if self.out[self.graph.to_index(ix)] == 0 {
77                     self.out[self.graph.to_index(ix)] = self.generation;
78                     self.out_size += 1;
79                 }
80             }
81             if self.graph.is_directed() {
82                 for ix in self.graph.neighbors_directed(from, Incoming) {
83                     if self.ins[self.graph.to_index(ix)] == 0 {
84                         self.ins[self.graph.to_index(ix)] = self.generation;
85                         self.ins_size += 1;
86                     }
87                 }
88             }
89         }
90 
91         /// Restore the state to before the last added mapping
pop_mapping(&mut self, from: G::NodeId)92         pub fn pop_mapping(&mut self, from: G::NodeId) {
93             // undo (n, m) mapping
94             self.mapping[self.graph.to_index(from)] = std::usize::MAX;
95 
96             // unmark in ins and outs
97             for ix in self.graph.neighbors_directed(from, Outgoing) {
98                 if self.out[self.graph.to_index(ix)] == self.generation {
99                     self.out[self.graph.to_index(ix)] = 0;
100                     self.out_size -= 1;
101                 }
102             }
103             if self.graph.is_directed() {
104                 for ix in self.graph.neighbors_directed(from, Incoming) {
105                     if self.ins[self.graph.to_index(ix)] == self.generation {
106                         self.ins[self.graph.to_index(ix)] = 0;
107                         self.ins_size -= 1;
108                     }
109                 }
110             }
111 
112             self.generation -= 1;
113         }
114 
115         /// Find the next (least) node in the Tout set.
next_out_index(&self, from_index: usize) -> Option<usize>116         pub fn next_out_index(&self, from_index: usize) -> Option<usize> {
117             self.out[from_index..]
118                 .iter()
119                 .enumerate()
120                 .find(move |&(index, &elt)| {
121                     elt > 0 && self.mapping[from_index + index] == std::usize::MAX
122                 })
123                 .map(|(index, _)| index)
124         }
125 
126         /// Find the next (least) node in the Tin set.
next_in_index(&self, from_index: usize) -> Option<usize>127         pub fn next_in_index(&self, from_index: usize) -> Option<usize> {
128             if !self.graph.is_directed() {
129                 return None;
130             }
131             self.ins[from_index..]
132                 .iter()
133                 .enumerate()
134                 .find(move |&(index, &elt)| {
135                     elt > 0 && self.mapping[from_index + index] == std::usize::MAX
136                 })
137                 .map(|(index, _)| index)
138         }
139 
140         /// Find the next (least) node in the N - M set.
next_rest_index(&self, from_index: usize) -> Option<usize>141         pub fn next_rest_index(&self, from_index: usize) -> Option<usize> {
142             self.mapping[from_index..]
143                 .iter()
144                 .enumerate()
145                 .find(|&(_, &elt)| elt == std::usize::MAX)
146                 .map(|(index, _)| index)
147         }
148     }
149 }
150 
151 mod semantic {
152     use super::*;
153 
154     pub struct NoSemanticMatch;
155 
156     pub trait NodeMatcher<G0: GraphBase, G1: GraphBase> {
enabled() -> bool157         fn enabled() -> bool;
eq(&mut self, _g0: &G0, _g1: &G1, _n0: G0::NodeId, _n1: G1::NodeId) -> bool158         fn eq(&mut self, _g0: &G0, _g1: &G1, _n0: G0::NodeId, _n1: G1::NodeId) -> bool;
159     }
160 
161     impl<G0: GraphBase, G1: GraphBase> NodeMatcher<G0, G1> for NoSemanticMatch {
162         #[inline]
enabled() -> bool163         fn enabled() -> bool {
164             false
165         }
166         #[inline]
eq(&mut self, _g0: &G0, _g1: &G1, _n0: G0::NodeId, _n1: G1::NodeId) -> bool167         fn eq(&mut self, _g0: &G0, _g1: &G1, _n0: G0::NodeId, _n1: G1::NodeId) -> bool {
168             true
169         }
170     }
171 
172     impl<G0, G1, F> NodeMatcher<G0, G1> for F
173     where
174         G0: GraphBase + DataMap,
175         G1: GraphBase + DataMap,
176         F: FnMut(&G0::NodeWeight, &G1::NodeWeight) -> bool,
177     {
178         #[inline]
enabled() -> bool179         fn enabled() -> bool {
180             true
181         }
182         #[inline]
eq(&mut self, g0: &G0, g1: &G1, n0: G0::NodeId, n1: G1::NodeId) -> bool183         fn eq(&mut self, g0: &G0, g1: &G1, n0: G0::NodeId, n1: G1::NodeId) -> bool {
184             if let (Some(x), Some(y)) = (g0.node_weight(n0), g1.node_weight(n1)) {
185                 self(x, y)
186             } else {
187                 false
188             }
189         }
190     }
191 
192     pub trait EdgeMatcher<G0: GraphBase, G1: GraphBase> {
enabled() -> bool193         fn enabled() -> bool;
eq( &mut self, _g0: &G0, _g1: &G1, e0: (G0::NodeId, G0::NodeId), e1: (G1::NodeId, G1::NodeId), ) -> bool194         fn eq(
195             &mut self,
196             _g0: &G0,
197             _g1: &G1,
198             e0: (G0::NodeId, G0::NodeId),
199             e1: (G1::NodeId, G1::NodeId),
200         ) -> bool;
201     }
202 
203     impl<G0: GraphBase, G1: GraphBase> EdgeMatcher<G0, G1> for NoSemanticMatch {
204         #[inline]
enabled() -> bool205         fn enabled() -> bool {
206             false
207         }
208         #[inline]
eq( &mut self, _g0: &G0, _g1: &G1, _e0: (G0::NodeId, G0::NodeId), _e1: (G1::NodeId, G1::NodeId), ) -> bool209         fn eq(
210             &mut self,
211             _g0: &G0,
212             _g1: &G1,
213             _e0: (G0::NodeId, G0::NodeId),
214             _e1: (G1::NodeId, G1::NodeId),
215         ) -> bool {
216             true
217         }
218     }
219 
220     impl<G0, G1, F> EdgeMatcher<G0, G1> for F
221     where
222         G0: GraphBase + DataMap + IntoEdgesDirected,
223         G1: GraphBase + DataMap + IntoEdgesDirected,
224         F: FnMut(&G0::EdgeWeight, &G1::EdgeWeight) -> bool,
225     {
226         #[inline]
enabled() -> bool227         fn enabled() -> bool {
228             true
229         }
230         #[inline]
eq( &mut self, g0: &G0, g1: &G1, e0: (G0::NodeId, G0::NodeId), e1: (G1::NodeId, G1::NodeId), ) -> bool231         fn eq(
232             &mut self,
233             g0: &G0,
234             g1: &G1,
235             e0: (G0::NodeId, G0::NodeId),
236             e1: (G1::NodeId, G1::NodeId),
237         ) -> bool {
238             let w0 = g0
239                 .edges_directed(e0.0, Outgoing)
240                 .find(|edge| edge.target() == e0.1)
241                 .and_then(|edge| g0.edge_weight(edge.id()));
242             let w1 = g1
243                 .edges_directed(e1.0, Outgoing)
244                 .find(|edge| edge.target() == e1.1)
245                 .and_then(|edge| g1.edge_weight(edge.id()));
246             if let (Some(x), Some(y)) = (w0, w1) {
247                 self(x, y)
248             } else {
249                 false
250             }
251         }
252     }
253 }
254 
255 mod matching {
256     use super::*;
257 
258     #[derive(Copy, Clone, PartialEq, Debug)]
259     enum OpenList {
260         Out,
261         In,
262         Other,
263     }
264 
265     #[derive(Clone, PartialEq, Debug)]
266     enum Frame<G0, G1>
267     where
268         G0: GraphBase,
269         G1: GraphBase,
270     {
271         Outer,
272         Inner {
273             nodes: (G0::NodeId, G1::NodeId),
274             open_list: OpenList,
275         },
276         Unwind {
277             nodes: (G0::NodeId, G1::NodeId),
278             open_list: OpenList,
279         },
280     }
281 
is_feasible<G0, G1, NM, EM>( st: &mut (Vf2State<'_, G0>, Vf2State<'_, G1>), nodes: (G0::NodeId, G1::NodeId), node_match: &mut NM, edge_match: &mut EM, ) -> bool where G0: GetAdjacencyMatrix + GraphProp + NodeCompactIndexable + IntoNeighborsDirected, G1: GetAdjacencyMatrix + GraphProp + NodeCompactIndexable + IntoNeighborsDirected, NM: NodeMatcher<G0, G1>, EM: EdgeMatcher<G0, G1>,282     fn is_feasible<G0, G1, NM, EM>(
283         st: &mut (Vf2State<'_, G0>, Vf2State<'_, G1>),
284         nodes: (G0::NodeId, G1::NodeId),
285         node_match: &mut NM,
286         edge_match: &mut EM,
287     ) -> bool
288     where
289         G0: GetAdjacencyMatrix + GraphProp + NodeCompactIndexable + IntoNeighborsDirected,
290         G1: GetAdjacencyMatrix + GraphProp + NodeCompactIndexable + IntoNeighborsDirected,
291         NM: NodeMatcher<G0, G1>,
292         EM: EdgeMatcher<G0, G1>,
293     {
294         macro_rules! field {
295             ($x:ident,     0) => {
296                 $x.0
297             };
298             ($x:ident,     1) => {
299                 $x.1
300             };
301             ($x:ident, 1 - 0) => {
302                 $x.1
303             };
304             ($x:ident, 1 - 1) => {
305                 $x.0
306             };
307         }
308 
309         macro_rules! r_succ {
310             ($j:tt) => {{
311                 let mut succ_count = 0;
312                 for n_neigh in field!(st, $j)
313                     .graph
314                     .neighbors_directed(field!(nodes, $j), Outgoing)
315                 {
316                     succ_count += 1;
317                     // handle the self loop case; it's not in the mapping (yet)
318                     let m_neigh = if field!(nodes, $j) != n_neigh {
319                         field!(st, $j).mapping[field!(st, $j).graph.to_index(n_neigh)]
320                     } else {
321                         field!(st, 1 - $j).graph.to_index(field!(nodes, 1 - $j))
322                     };
323                     if m_neigh == std::usize::MAX {
324                         continue;
325                     }
326                     let has_edge = field!(st, 1 - $j).graph.is_adjacent(
327                         &field!(st, 1 - $j).adjacency_matrix,
328                         field!(nodes, 1 - $j),
329                         field!(st, 1 - $j).graph.from_index(m_neigh),
330                     );
331                     if !has_edge {
332                         return false;
333                     }
334                 }
335                 succ_count
336             }};
337         }
338 
339         macro_rules! r_pred {
340             ($j:tt) => {{
341                 let mut pred_count = 0;
342                 for n_neigh in field!(st, $j)
343                     .graph
344                     .neighbors_directed(field!(nodes, $j), Incoming)
345                 {
346                     pred_count += 1;
347                     // the self loop case is handled in outgoing
348                     let m_neigh = field!(st, $j).mapping[field!(st, $j).graph.to_index(n_neigh)];
349                     if m_neigh == std::usize::MAX {
350                         continue;
351                     }
352                     let has_edge = field!(st, 1 - $j).graph.is_adjacent(
353                         &field!(st, 1 - $j).adjacency_matrix,
354                         field!(st, 1 - $j).graph.from_index(m_neigh),
355                         field!(nodes, 1 - $j),
356                     );
357                     if !has_edge {
358                         return false;
359                     }
360                 }
361                 pred_count
362             }};
363         }
364 
365         // Check syntactic feasibility of mapping by ensuring adjacencies
366         // of nx map to adjacencies of mx.
367         //
368         // nx == map to => mx
369         //
370         // R_succ
371         //
372         // Check that every neighbor of nx is mapped to a neighbor of mx,
373         // then check the reverse, from mx to nx. Check that they have the same
374         // count of edges.
375         //
376         // Note: We want to check the lookahead measures here if we can,
377         // R_out: Equal for G0, G1: Card(Succ(G, n) ^ Tout); for both Succ and Pred
378         // R_in: Same with Tin
379         // R_new: Equal for G0, G1: Ñ n Pred(G, n); both Succ and Pred,
380         //      Ñ is G0 - M - Tin - Tout
381         // last attempt to add these did not speed up any of the testcases
382         if r_succ!(0) > r_succ!(1) {
383             return false;
384         }
385         // R_pred
386         if st.0.graph.is_directed() && r_pred!(0) > r_pred!(1) {
387             return false;
388         }
389 
390         // // semantic feasibility: compare associated data for nodes
391         if NM::enabled() && !node_match.eq(st.0.graph, st.1.graph, nodes.0, nodes.1) {
392             return false;
393         }
394         // semantic feasibility: compare associated data for edges
395         if EM::enabled() {
396             macro_rules! edge_feasibility {
397                 ($j:tt) => {{
398                     for n_neigh in field!(st, $j)
399                         .graph
400                         .neighbors_directed(field!(nodes, $j), Outgoing)
401                     {
402                         let m_neigh = if field!(nodes, $j) != n_neigh {
403                             field!(st, $j).mapping[field!(st, $j).graph.to_index(n_neigh)]
404                         } else {
405                             field!(st, 1 - $j).graph.to_index(field!(nodes, 1 - $j))
406                         };
407                         if m_neigh == std::usize::MAX {
408                             continue;
409                         }
410 
411                         let e0 = (field!(nodes, $j), n_neigh);
412                         let e1 = (
413                             field!(nodes, 1 - $j),
414                             field!(st, 1 - $j).graph.from_index(m_neigh),
415                         );
416                         let edges = (e0, e1);
417                         if !edge_match.eq(
418                             st.0.graph,
419                             st.1.graph,
420                             field!(edges, $j),
421                             field!(edges, 1 - $j),
422                         ) {
423                             return false;
424                         }
425                     }
426                     if field!(st, $j).graph.is_directed() {
427                         for n_neigh in field!(st, $j)
428                             .graph
429                             .neighbors_directed(field!(nodes, $j), Incoming)
430                         {
431                             // the self loop case is handled in outgoing
432                             let m_neigh =
433                                 field!(st, $j).mapping[field!(st, $j).graph.to_index(n_neigh)];
434                             if m_neigh == std::usize::MAX {
435                                 continue;
436                             }
437 
438                             let e0 = (n_neigh, field!(nodes, $j));
439                             let e1 = (
440                                 field!(st, 1 - $j).graph.from_index(m_neigh),
441                                 field!(nodes, 1 - $j),
442                             );
443                             let edges = (e0, e1);
444                             if !edge_match.eq(
445                                 st.0.graph,
446                                 st.1.graph,
447                                 field!(edges, $j),
448                                 field!(edges, 1 - $j),
449                             ) {
450                                 return false;
451                             }
452                         }
453                     }
454                 }};
455             }
456 
457             edge_feasibility!(0);
458             edge_feasibility!(1);
459         }
460         true
461     }
462 
next_candidate<G0, G1>( st: &mut (Vf2State<'_, G0>, Vf2State<'_, G1>), ) -> Option<(G0::NodeId, G1::NodeId, OpenList)> where G0: GetAdjacencyMatrix + GraphProp + NodeCompactIndexable + IntoNeighborsDirected, G1: GetAdjacencyMatrix + GraphProp + NodeCompactIndexable + IntoNeighborsDirected,463     fn next_candidate<G0, G1>(
464         st: &mut (Vf2State<'_, G0>, Vf2State<'_, G1>),
465     ) -> Option<(G0::NodeId, G1::NodeId, OpenList)>
466     where
467         G0: GetAdjacencyMatrix + GraphProp + NodeCompactIndexable + IntoNeighborsDirected,
468         G1: GetAdjacencyMatrix + GraphProp + NodeCompactIndexable + IntoNeighborsDirected,
469     {
470         let mut from_index = None;
471         let mut open_list = OpenList::Out;
472         let mut to_index = st.1.next_out_index(0);
473 
474         // Try the out list
475         if to_index.is_some() {
476             from_index = st.0.next_out_index(0);
477             open_list = OpenList::Out;
478         }
479         // Try the in list
480         if to_index.is_none() || from_index.is_none() {
481             to_index = st.1.next_in_index(0);
482 
483             if to_index.is_some() {
484                 from_index = st.0.next_in_index(0);
485                 open_list = OpenList::In;
486             }
487         }
488         // Try the other list -- disconnected graph
489         if to_index.is_none() || from_index.is_none() {
490             to_index = st.1.next_rest_index(0);
491             if to_index.is_some() {
492                 from_index = st.0.next_rest_index(0);
493                 open_list = OpenList::Other;
494             }
495         }
496         match (from_index, to_index) {
497             (Some(n), Some(m)) => Some((
498                 st.0.graph.from_index(n),
499                 st.1.graph.from_index(m),
500                 open_list,
501             )),
502             // No more candidates
503             _ => None,
504         }
505     }
506 
next_from_ix<G0, G1>( st: &mut (Vf2State<'_, G0>, Vf2State<'_, G1>), nx: G1::NodeId, open_list: OpenList, ) -> Option<G1::NodeId> where G0: GetAdjacencyMatrix + GraphProp + NodeCompactIndexable + IntoNeighborsDirected, G1: GetAdjacencyMatrix + GraphProp + NodeCompactIndexable + IntoNeighborsDirected,507     fn next_from_ix<G0, G1>(
508         st: &mut (Vf2State<'_, G0>, Vf2State<'_, G1>),
509         nx: G1::NodeId,
510         open_list: OpenList,
511     ) -> Option<G1::NodeId>
512     where
513         G0: GetAdjacencyMatrix + GraphProp + NodeCompactIndexable + IntoNeighborsDirected,
514         G1: GetAdjacencyMatrix + GraphProp + NodeCompactIndexable + IntoNeighborsDirected,
515     {
516         // Find the next node index to try on the `to` side of the mapping
517         let start = st.1.graph.to_index(nx) + 1;
518         let cand1 = match open_list {
519             OpenList::Out => st.1.next_out_index(start),
520             OpenList::In => st.1.next_in_index(start),
521             OpenList::Other => st.1.next_rest_index(start),
522         }
523         .map(|c| c + start); // compensate for start offset.
524         match cand1 {
525             None => None, // no more candidates
526             Some(ix) => {
527                 debug_assert!(ix >= start);
528                 Some(st.1.graph.from_index(ix))
529             }
530         }
531     }
532 
pop_state<G0, G1>( st: &mut (Vf2State<'_, G0>, Vf2State<'_, G1>), nodes: (G0::NodeId, G1::NodeId), ) where G0: GetAdjacencyMatrix + GraphProp + NodeCompactIndexable + IntoNeighborsDirected, G1: GetAdjacencyMatrix + GraphProp + NodeCompactIndexable + IntoNeighborsDirected,533     fn pop_state<G0, G1>(
534         st: &mut (Vf2State<'_, G0>, Vf2State<'_, G1>),
535         nodes: (G0::NodeId, G1::NodeId),
536     ) where
537         G0: GetAdjacencyMatrix + GraphProp + NodeCompactIndexable + IntoNeighborsDirected,
538         G1: GetAdjacencyMatrix + GraphProp + NodeCompactIndexable + IntoNeighborsDirected,
539     {
540         st.0.pop_mapping(nodes.0);
541         st.1.pop_mapping(nodes.1);
542     }
543 
push_state<G0, G1>( st: &mut (Vf2State<'_, G0>, Vf2State<'_, G1>), nodes: (G0::NodeId, G1::NodeId), ) where G0: GetAdjacencyMatrix + GraphProp + NodeCompactIndexable + IntoNeighborsDirected, G1: GetAdjacencyMatrix + GraphProp + NodeCompactIndexable + IntoNeighborsDirected,544     fn push_state<G0, G1>(
545         st: &mut (Vf2State<'_, G0>, Vf2State<'_, G1>),
546         nodes: (G0::NodeId, G1::NodeId),
547     ) where
548         G0: GetAdjacencyMatrix + GraphProp + NodeCompactIndexable + IntoNeighborsDirected,
549         G1: GetAdjacencyMatrix + GraphProp + NodeCompactIndexable + IntoNeighborsDirected,
550     {
551         st.0.push_mapping(nodes.0, st.1.graph.to_index(nodes.1));
552         st.1.push_mapping(nodes.1, st.0.graph.to_index(nodes.0));
553     }
554 
555     /// Return Some(bool) if isomorphism is decided, else None.
try_match<G0, G1, NM, EM>( st: &mut (Vf2State<'_, G0>, Vf2State<'_, G1>), node_match: &mut NM, edge_match: &mut EM, match_subgraph: bool, ) -> Option<bool> where G0: NodeCompactIndexable + EdgeCount + GetAdjacencyMatrix + GraphProp + IntoNeighborsDirected, G1: NodeCompactIndexable + EdgeCount + GetAdjacencyMatrix + GraphProp + IntoNeighborsDirected, NM: NodeMatcher<G0, G1>, EM: EdgeMatcher<G0, G1>,556     pub fn try_match<G0, G1, NM, EM>(
557         st: &mut (Vf2State<'_, G0>, Vf2State<'_, G1>),
558         node_match: &mut NM,
559         edge_match: &mut EM,
560         match_subgraph: bool,
561     ) -> Option<bool>
562     where
563         G0: NodeCompactIndexable
564             + EdgeCount
565             + GetAdjacencyMatrix
566             + GraphProp
567             + IntoNeighborsDirected,
568         G1: NodeCompactIndexable
569             + EdgeCount
570             + GetAdjacencyMatrix
571             + GraphProp
572             + IntoNeighborsDirected,
573         NM: NodeMatcher<G0, G1>,
574         EM: EdgeMatcher<G0, G1>,
575     {
576         let mut stack = vec![Frame::Outer];
577         if isomorphisms(st, node_match, edge_match, match_subgraph, &mut stack).is_some() {
578             Some(true)
579         } else {
580             None
581         }
582     }
583 
isomorphisms<G0, G1, NM, EM>( st: &mut (Vf2State<'_, G0>, Vf2State<'_, G1>), node_match: &mut NM, edge_match: &mut EM, match_subgraph: bool, stack: &mut Vec<Frame<G0, G1>>, ) -> Option<Vec<usize>> where G0: NodeCompactIndexable + EdgeCount + GetAdjacencyMatrix + GraphProp + IntoNeighborsDirected, G1: NodeCompactIndexable + EdgeCount + GetAdjacencyMatrix + GraphProp + IntoNeighborsDirected, NM: NodeMatcher<G0, G1>, EM: EdgeMatcher<G0, G1>,584     fn isomorphisms<G0, G1, NM, EM>(
585         st: &mut (Vf2State<'_, G0>, Vf2State<'_, G1>),
586         node_match: &mut NM,
587         edge_match: &mut EM,
588         match_subgraph: bool,
589         stack: &mut Vec<Frame<G0, G1>>,
590     ) -> Option<Vec<usize>>
591     where
592         G0: NodeCompactIndexable
593             + EdgeCount
594             + GetAdjacencyMatrix
595             + GraphProp
596             + IntoNeighborsDirected,
597         G1: NodeCompactIndexable
598             + EdgeCount
599             + GetAdjacencyMatrix
600             + GraphProp
601             + IntoNeighborsDirected,
602         NM: NodeMatcher<G0, G1>,
603         EM: EdgeMatcher<G0, G1>,
604     {
605         if st.0.is_complete() {
606             return Some(st.0.mapping.clone());
607         }
608 
609         // A "depth first" search of a valid mapping from graph 1 to graph 2
610         // F(s, n, m) -- evaluate state s and add mapping n <-> m
611         // Find least T1out node (in st.out[1] but not in M[1])
612         let mut result = None;
613         while let Some(frame) = stack.pop() {
614             match frame {
615                 Frame::Unwind { nodes, open_list } => {
616                     pop_state(st, nodes);
617 
618                     match next_from_ix(st, nodes.1, open_list) {
619                         None => continue,
620                         Some(nx) => {
621                             let f = Frame::Inner {
622                                 nodes: (nodes.0, nx),
623                                 open_list,
624                             };
625                             stack.push(f);
626                         }
627                     }
628                 }
629                 Frame::Outer => match next_candidate(st) {
630                     None => continue,
631                     Some((nx, mx, open_list)) => {
632                         let f = Frame::Inner {
633                             nodes: (nx, mx),
634                             open_list,
635                         };
636                         stack.push(f);
637                     }
638                 },
639                 Frame::Inner { nodes, open_list } => {
640                     if is_feasible(st, nodes, node_match, edge_match) {
641                         push_state(st, nodes);
642                         if st.0.is_complete() {
643                             result = Some(st.0.mapping.clone());
644                         }
645                         // Check cardinalities of Tin, Tout sets
646                         if (!match_subgraph
647                             && st.0.out_size == st.1.out_size
648                             && st.0.ins_size == st.1.ins_size)
649                             || (match_subgraph
650                                 && st.0.out_size <= st.1.out_size
651                                 && st.0.ins_size <= st.1.ins_size)
652                         {
653                             let f0 = Frame::Unwind { nodes, open_list };
654                             stack.push(f0);
655                             stack.push(Frame::Outer);
656                             continue;
657                         }
658                         pop_state(st, nodes);
659                     }
660                     match next_from_ix(st, nodes.1, open_list) {
661                         None => continue,
662                         Some(nx) => {
663                             let f = Frame::Inner {
664                                 nodes: (nodes.0, nx),
665                                 open_list,
666                             };
667                             stack.push(f);
668                         }
669                     }
670                 }
671             }
672             if result.is_some() {
673                 return result;
674             }
675         }
676         result
677     }
678 
679     pub struct GraphMatcher<'a, 'b, 'c, G0, G1, NM, EM>
680     where
681         G0: NodeCompactIndexable
682             + EdgeCount
683             + GetAdjacencyMatrix
684             + GraphProp
685             + IntoNeighborsDirected,
686         G1: NodeCompactIndexable
687             + EdgeCount
688             + GetAdjacencyMatrix
689             + GraphProp
690             + IntoNeighborsDirected,
691         NM: NodeMatcher<G0, G1>,
692         EM: EdgeMatcher<G0, G1>,
693     {
694         st: (Vf2State<'a, G0>, Vf2State<'b, G1>),
695         node_match: &'c mut NM,
696         edge_match: &'c mut EM,
697         match_subgraph: bool,
698         stack: Vec<Frame<G0, G1>>,
699     }
700 
701     impl<'a, 'b, 'c, G0, G1, NM, EM> GraphMatcher<'a, 'b, 'c, G0, G1, NM, EM>
702     where
703         G0: NodeCompactIndexable
704             + EdgeCount
705             + GetAdjacencyMatrix
706             + GraphProp
707             + IntoNeighborsDirected,
708         G1: NodeCompactIndexable
709             + EdgeCount
710             + GetAdjacencyMatrix
711             + GraphProp
712             + IntoNeighborsDirected,
713         NM: NodeMatcher<G0, G1>,
714         EM: EdgeMatcher<G0, G1>,
715     {
new( g0: &'a G0, g1: &'b G1, node_match: &'c mut NM, edge_match: &'c mut EM, match_subgraph: bool, ) -> Self716         pub fn new(
717             g0: &'a G0,
718             g1: &'b G1,
719             node_match: &'c mut NM,
720             edge_match: &'c mut EM,
721             match_subgraph: bool,
722         ) -> Self {
723             let stack = vec![Frame::Outer];
724             Self {
725                 st: (Vf2State::new(g0), Vf2State::new(g1)),
726                 node_match,
727                 edge_match,
728                 match_subgraph,
729                 stack,
730             }
731         }
732     }
733 
734     impl<'a, 'b, 'c, G0, G1, NM, EM> Iterator for GraphMatcher<'a, 'b, 'c, G0, G1, NM, EM>
735     where
736         G0: NodeCompactIndexable
737             + EdgeCount
738             + GetAdjacencyMatrix
739             + GraphProp
740             + IntoNeighborsDirected,
741         G1: NodeCompactIndexable
742             + EdgeCount
743             + GetAdjacencyMatrix
744             + GraphProp
745             + IntoNeighborsDirected,
746         NM: NodeMatcher<G0, G1>,
747         EM: EdgeMatcher<G0, G1>,
748     {
749         type Item = Vec<usize>;
750 
next(&mut self) -> Option<Self::Item>751         fn next(&mut self) -> Option<Self::Item> {
752             isomorphisms(
753                 &mut self.st,
754                 self.node_match,
755                 self.edge_match,
756                 self.match_subgraph,
757                 &mut self.stack,
758             )
759         }
760 
size_hint(&self) -> (usize, Option<usize>)761         fn size_hint(&self) -> (usize, Option<usize>) {
762             // To calculate the upper bound of results we use n! where n is the
763             // number of nodes in graph 1. n! values fit into a 64-bit usize up
764             // to n = 20, so we don't estimate an upper limit for n > 20.
765             let n = self.st.0.graph.node_count();
766 
767             // We hardcode n! values into an array that accounts for architectures
768             // with smaller usizes to get our upper bound.
769             let upper_bounds: Vec<Option<usize>> = [
770                 1u64,
771                 1,
772                 2,
773                 6,
774                 24,
775                 120,
776                 720,
777                 5040,
778                 40320,
779                 362880,
780                 3628800,
781                 39916800,
782                 479001600,
783                 6227020800,
784                 87178291200,
785                 1307674368000,
786                 20922789888000,
787                 355687428096000,
788                 6402373705728000,
789                 121645100408832000,
790                 2432902008176640000,
791             ]
792             .iter()
793             .map(|n| usize::try_from(*n).ok())
794             .collect();
795 
796             if n > upper_bounds.len() {
797                 return (0, None);
798             }
799 
800             (0, upper_bounds[n])
801         }
802     }
803 }
804 
805 /// \[Generic\] Return `true` if the graphs `g0` and `g1` are isomorphic.
806 ///
807 /// Using the VF2 algorithm, only matching graph syntactically (graph
808 /// structure).
809 ///
810 /// The graphs should not be multigraphs.
811 ///
812 /// **Reference**
813 ///
814 /// * Luigi P. Cordella, Pasquale Foggia, Carlo Sansone, Mario Vento;
815 ///   *A (Sub)Graph Isomorphism Algorithm for Matching Large Graphs*
is_isomorphic<G0, G1>(g0: G0, g1: G1) -> bool where G0: NodeCompactIndexable + EdgeCount + GetAdjacencyMatrix + GraphProp + IntoNeighborsDirected, G1: NodeCompactIndexable + EdgeCount + GetAdjacencyMatrix + GraphProp<EdgeType = G0::EdgeType> + IntoNeighborsDirected,816 pub fn is_isomorphic<G0, G1>(g0: G0, g1: G1) -> bool
817 where
818     G0: NodeCompactIndexable + EdgeCount + GetAdjacencyMatrix + GraphProp + IntoNeighborsDirected,
819     G1: NodeCompactIndexable
820         + EdgeCount
821         + GetAdjacencyMatrix
822         + GraphProp<EdgeType = G0::EdgeType>
823         + IntoNeighborsDirected,
824 {
825     if g0.node_count() != g1.node_count() || g0.edge_count() != g1.edge_count() {
826         return false;
827     }
828 
829     let mut st = (Vf2State::new(&g0), Vf2State::new(&g1));
830     self::matching::try_match(&mut st, &mut NoSemanticMatch, &mut NoSemanticMatch, false)
831         .unwrap_or(false)
832 }
833 
834 /// \[Generic\] Return `true` if the graphs `g0` and `g1` are isomorphic.
835 ///
836 /// Using the VF2 algorithm, examining both syntactic and semantic
837 /// graph isomorphism (graph structure and matching node and edge weights).
838 ///
839 /// The graphs should not be multigraphs.
is_isomorphic_matching<G0, G1, NM, EM>( g0: G0, g1: G1, mut node_match: NM, mut edge_match: EM, ) -> bool where G0: NodeCompactIndexable + EdgeCount + DataMap + GetAdjacencyMatrix + GraphProp + IntoEdgesDirected, G1: NodeCompactIndexable + EdgeCount + DataMap + GetAdjacencyMatrix + GraphProp<EdgeType = G0::EdgeType> + IntoEdgesDirected, NM: FnMut(&G0::NodeWeight, &G1::NodeWeight) -> bool, EM: FnMut(&G0::EdgeWeight, &G1::EdgeWeight) -> bool,840 pub fn is_isomorphic_matching<G0, G1, NM, EM>(
841     g0: G0,
842     g1: G1,
843     mut node_match: NM,
844     mut edge_match: EM,
845 ) -> bool
846 where
847     G0: NodeCompactIndexable
848         + EdgeCount
849         + DataMap
850         + GetAdjacencyMatrix
851         + GraphProp
852         + IntoEdgesDirected,
853     G1: NodeCompactIndexable
854         + EdgeCount
855         + DataMap
856         + GetAdjacencyMatrix
857         + GraphProp<EdgeType = G0::EdgeType>
858         + IntoEdgesDirected,
859     NM: FnMut(&G0::NodeWeight, &G1::NodeWeight) -> bool,
860     EM: FnMut(&G0::EdgeWeight, &G1::EdgeWeight) -> bool,
861 {
862     if g0.node_count() != g1.node_count() || g0.edge_count() != g1.edge_count() {
863         return false;
864     }
865 
866     let mut st = (Vf2State::new(&g0), Vf2State::new(&g1));
867     self::matching::try_match(&mut st, &mut node_match, &mut edge_match, false).unwrap_or(false)
868 }
869 
870 /// \[Generic\] Return `true` if `g0` is isomorphic to a subgraph of `g1`.
871 ///
872 /// Using the VF2 algorithm, only matching graph syntactically (graph
873 /// structure).
874 ///
875 /// The graphs should not be multigraphs.
876 ///
877 /// # Subgraph isomorphism
878 ///
879 /// (adapted from [`networkx` documentation](https://networkx.github.io/documentation/stable/reference/algorithms/isomorphism.vf2.html))
880 ///
881 /// Graph theory literature can be ambiguous about the meaning of the above statement,
882 /// and we seek to clarify it now.
883 ///
884 /// In the VF2 literature, a mapping **M** is said to be a *graph-subgraph isomorphism*
885 /// iff **M** is an isomorphism between **G2** and a subgraph of **G1**. Thus, to say
886 /// that **G1** and **G2** are graph-subgraph isomorphic is to say that a subgraph of
887 /// **G1** is isomorphic to **G2**.
888 ///
889 /// Other literature uses the phrase ‘subgraph isomorphic’ as in
890 /// ‘**G1** does not have a subgraph isomorphic to **G2**’. Another use is as an in adverb
891 /// for isomorphic. Thus, to say that **G1** and **G2** are subgraph isomorphic is to say
892 /// that a subgraph of **G1** is isomorphic to **G2**.
893 ///
894 /// Finally, the term ‘subgraph’ can have multiple meanings. In this context,
895 /// ‘subgraph’ always means a ‘node-induced subgraph’. Edge-induced subgraph
896 /// isomorphisms are not directly supported. For subgraphs which are not
897 /// induced, the term ‘monomorphism’ is preferred over ‘isomorphism’.
898 ///
899 /// **Reference**
900 ///
901 /// * Luigi P. Cordella, Pasquale Foggia, Carlo Sansone, Mario Vento;
902 ///   *A (Sub)Graph Isomorphism Algorithm for Matching Large Graphs*
is_isomorphic_subgraph<G0, G1>(g0: G0, g1: G1) -> bool where G0: NodeCompactIndexable + EdgeCount + GetAdjacencyMatrix + GraphProp + IntoNeighborsDirected, G1: NodeCompactIndexable + EdgeCount + GetAdjacencyMatrix + GraphProp<EdgeType = G0::EdgeType> + IntoNeighborsDirected,903 pub fn is_isomorphic_subgraph<G0, G1>(g0: G0, g1: G1) -> bool
904 where
905     G0: NodeCompactIndexable + EdgeCount + GetAdjacencyMatrix + GraphProp + IntoNeighborsDirected,
906     G1: NodeCompactIndexable
907         + EdgeCount
908         + GetAdjacencyMatrix
909         + GraphProp<EdgeType = G0::EdgeType>
910         + IntoNeighborsDirected,
911 {
912     if g0.node_count() > g1.node_count() || g0.edge_count() > g1.edge_count() {
913         return false;
914     }
915 
916     let mut st = (Vf2State::new(&g0), Vf2State::new(&g1));
917     self::matching::try_match(&mut st, &mut NoSemanticMatch, &mut NoSemanticMatch, true)
918         .unwrap_or(false)
919 }
920 
921 /// \[Generic\] Return `true` if `g0` is isomorphic to a subgraph of `g1`.
922 ///
923 /// Using the VF2 algorithm, examining both syntactic and semantic
924 /// graph isomorphism (graph structure and matching node and edge weights).
925 ///
926 /// The graphs should not be multigraphs.
is_isomorphic_subgraph_matching<G0, G1, NM, EM>( g0: G0, g1: G1, mut node_match: NM, mut edge_match: EM, ) -> bool where G0: NodeCompactIndexable + EdgeCount + DataMap + GetAdjacencyMatrix + GraphProp + IntoEdgesDirected, G1: NodeCompactIndexable + EdgeCount + DataMap + GetAdjacencyMatrix + GraphProp<EdgeType = G0::EdgeType> + IntoEdgesDirected, NM: FnMut(&G0::NodeWeight, &G1::NodeWeight) -> bool, EM: FnMut(&G0::EdgeWeight, &G1::EdgeWeight) -> bool,927 pub fn is_isomorphic_subgraph_matching<G0, G1, NM, EM>(
928     g0: G0,
929     g1: G1,
930     mut node_match: NM,
931     mut edge_match: EM,
932 ) -> bool
933 where
934     G0: NodeCompactIndexable
935         + EdgeCount
936         + DataMap
937         + GetAdjacencyMatrix
938         + GraphProp
939         + IntoEdgesDirected,
940     G1: NodeCompactIndexable
941         + EdgeCount
942         + DataMap
943         + GetAdjacencyMatrix
944         + GraphProp<EdgeType = G0::EdgeType>
945         + IntoEdgesDirected,
946     NM: FnMut(&G0::NodeWeight, &G1::NodeWeight) -> bool,
947     EM: FnMut(&G0::EdgeWeight, &G1::EdgeWeight) -> bool,
948 {
949     if g0.node_count() > g1.node_count() || g0.edge_count() > g1.edge_count() {
950         return false;
951     }
952 
953     let mut st = (Vf2State::new(&g0), Vf2State::new(&g1));
954     self::matching::try_match(&mut st, &mut node_match, &mut edge_match, true).unwrap_or(false)
955 }
956 
957 /// Using the VF2 algorithm, examine both syntactic and semantic graph
958 /// isomorphism (graph structure and matching node and edge weights) and,
959 /// if `g0` is isomorphic to a subgraph of `g1`, return the mappings between
960 /// them.
961 ///
962 /// The graphs should not be multigraphs.
subgraph_isomorphisms_iter<'a, G0, G1, NM, EM>( g0: &'a G0, g1: &'a G1, node_match: &'a mut NM, edge_match: &'a mut EM, ) -> Option<impl Iterator<Item = Vec<usize>> + 'a> where G0: 'a + NodeCompactIndexable + EdgeCount + DataMap + GetAdjacencyMatrix + GraphProp + IntoEdgesDirected, G1: 'a + NodeCompactIndexable + EdgeCount + DataMap + GetAdjacencyMatrix + GraphProp<EdgeType = G0::EdgeType> + IntoEdgesDirected, NM: 'a + FnMut(&G0::NodeWeight, &G1::NodeWeight) -> bool, EM: 'a + FnMut(&G0::EdgeWeight, &G1::EdgeWeight) -> bool,963 pub fn subgraph_isomorphisms_iter<'a, G0, G1, NM, EM>(
964     g0: &'a G0,
965     g1: &'a G1,
966     node_match: &'a mut NM,
967     edge_match: &'a mut EM,
968 ) -> Option<impl Iterator<Item = Vec<usize>> + 'a>
969 where
970     G0: 'a
971         + NodeCompactIndexable
972         + EdgeCount
973         + DataMap
974         + GetAdjacencyMatrix
975         + GraphProp
976         + IntoEdgesDirected,
977     G1: 'a
978         + NodeCompactIndexable
979         + EdgeCount
980         + DataMap
981         + GetAdjacencyMatrix
982         + GraphProp<EdgeType = G0::EdgeType>
983         + IntoEdgesDirected,
984     NM: 'a + FnMut(&G0::NodeWeight, &G1::NodeWeight) -> bool,
985     EM: 'a + FnMut(&G0::EdgeWeight, &G1::EdgeWeight) -> bool,
986 {
987     if g0.node_count() > g1.node_count() || g0.edge_count() > g1.edge_count() {
988         return None;
989     }
990 
991     Some(self::matching::GraphMatcher::new(
992         g0, g1, node_match, edge_match, true,
993     ))
994 }
995