1 use crate::data::DataMap; 2 use crate::visit::EdgeCount; 3 use crate::visit::EdgeRef; 4 use crate::visit::GetAdjacencyMatrix; 5 use crate::visit::GraphBase; 6 use crate::visit::GraphProp; 7 use crate::visit::IntoEdgesDirected; 8 use crate::visit::IntoNeighborsDirected; 9 use crate::visit::NodeCompactIndexable; 10 use crate::{Incoming, Outgoing}; 11 12 use self::semantic::EdgeMatcher; 13 use self::semantic::NoSemanticMatch; 14 use self::semantic::NodeMatcher; 15 use self::state::Vf2State; 16 17 mod state { 18 use super::*; 19 20 #[derive(Debug)] 21 // TODO: make mapping generic over the index type of the other graph. 22 pub struct Vf2State<'a, G: GetAdjacencyMatrix> { 23 /// A reference to the graph this state was built from. 24 pub graph: &'a G, 25 /// The current mapping M(s) of nodes from G0 → G1 and G1 → G0, 26 /// `usize::MAX` for no mapping. 27 pub mapping: Vec<usize>, 28 /// out[i] is non-zero if i is in either M_0(s) or Tout_0(s) 29 /// These are all the next vertices that are not mapped yet, but 30 /// have an outgoing edge from the mapping. 31 out: Vec<usize>, 32 /// ins[i] is non-zero if i is in either M_0(s) or Tin_0(s) 33 /// These are all the incoming vertices, those not mapped yet, but 34 /// have an edge from them into the mapping. 35 /// Unused if graph is undirected -- it's identical with out in that case. 36 ins: Vec<usize>, 37 pub out_size: usize, 38 pub ins_size: usize, 39 pub adjacency_matrix: G::AdjMatrix, 40 generation: usize, 41 } 42 43 impl<'a, G> Vf2State<'a, G> 44 where 45 G: GetAdjacencyMatrix + GraphProp + NodeCompactIndexable + IntoNeighborsDirected, 46 { 47 pub fn new(g: &'a G) -> Self { 48 let c0 = g.node_count(); 49 Vf2State { 50 graph: g, 51 mapping: vec![std::usize::MAX; c0], 52 out: vec![0; c0], 53 ins: vec![0; c0 * (g.is_directed() as usize)], 54 out_size: 0, 55 ins_size: 0, 56 adjacency_matrix: g.adjacency_matrix(), 57 generation: 0, 58 } 59 } 60 61 /// Return **true** if we have a complete mapping greedy_feedback_arc_set<G>(g: G) -> impl Iterator<Item = G::EdgeRef> where G: IntoEdgeReferences + GraphProp<EdgeType = Directed>, G::NodeId: GraphIndex, G: crate::visit::NodeCount,62 pub fn is_complete(&self) -> bool { 63 self.generation == self.mapping.len() 64 } 65 66 /// Add mapping **from** <-> **to** to the state. 67 pub fn push_mapping(&mut self, from: G::NodeId, to: usize) { 68 self.generation += 1; 69 self.mapping[self.graph.to_index(from)] = to; 70 // update T0 & T1 ins/outs 71 // T0out: Node in G0 not in M0 but successor of a node in M0. 72 // st.out[0]: Node either in M0 or successor of M0 73 for ix in self.graph.neighbors_directed(from, Outgoing) { 74 if self.out[self.graph.to_index(ix)] == 0 { 75 self.out[self.graph.to_index(ix)] = self.generation; 76 self.out_size += 1; 77 } 78 } good_node_sequence( edge_refs: impl Iterator<Item = (NodeIndex<usize>, NodeIndex<usize>)>, ) -> HashMap<usize, usize>79 if self.graph.is_directed() { 80 for ix in self.graph.neighbors_directed(from, Incoming) { 81 if self.ins[self.graph.to_index(ix)] == 0 { 82 self.ins[self.graph.to_index(ix)] = self.generation; 83 self.ins_size += 1; 84 } 85 } 86 } 87 } 88 89 /// Restore the state to before the last added mapping 90 pub fn pop_mapping(&mut self, from: G::NodeId) { 91 // undo (n, m) mapping 92 self.mapping[self.graph.to_index(from)] = std::usize::MAX; 93 94 // unmark in ins and outs 95 for ix in self.graph.neighbors_directed(from, Outgoing) { 96 if self.out[self.graph.to_index(ix)] == self.generation { 97 self.out[self.graph.to_index(ix)] = 0; 98 self.out_size -= 1; 99 } 100 } 101 if self.graph.is_directed() { 102 for ix in self.graph.neighbors_directed(from, Incoming) { 103 if self.ins[self.graph.to_index(ix)] == self.generation { 104 self.ins[self.graph.to_index(ix)] = 0; 105 self.ins_size -= 1; 106 } 107 } 108 } 109 110 self.generation -= 1; 111 } 112 113 /// Find the next (least) node in the Tout set. 114 pub fn next_out_index(&self, from_index: usize) -> Option<usize> { 115 self.out[from_index..] 116 .iter() 117 .enumerate() 118 .find(move |&(index, &elt)| { 119 elt > 0 && self.mapping[from_index + index] == std::usize::MAX 120 }) 121 .map(|(index, _)| index) 122 } 123 124 /// Find the next (least) node in the Tin set. 125 pub fn next_in_index(&self, from_index: usize) -> Option<usize> { 126 if !self.graph.is_directed() { 127 return None; 128 } 129 self.ins[from_index..] 130 .iter() 131 .enumerate() 132 .find(move |&(index, &elt)| { 133 elt > 0 && self.mapping[from_index + index] == std::usize::MAX 134 }) 135 .map(|(index, _)| index) 136 } 137 138 /// Find the next (least) node in the N - M set. 139 pub fn next_rest_index(&self, from_index: usize) -> Option<usize> { 140 self.mapping[from_index..] 141 .iter() 142 .enumerate() 143 .find(|&(_, &elt)| elt == std::usize::MAX) 144 .map(|(index, _)| index) 145 } 146 } 147 } 148 149 mod semantic { 150 use super::*; 151 152 pub struct NoSemanticMatch; 153 154 pub trait NodeMatcher<G0: GraphBase, G1: GraphBase> { 155 fn enabled() -> bool; 156 fn eq(&mut self, _g0: &G0, _g1: &G1, _n0: G0::NodeId, _n1: G1::NodeId) -> bool; 157 } 158 159 impl<G0: GraphBase, G1: GraphBase> NodeMatcher<G0, G1> for NoSemanticMatch { 160 #[inline] 161 fn enabled() -> bool { 162 false 163 } 164 #[inline] 165 fn eq(&mut self, _g0: &G0, _g1: &G1, _n0: G0::NodeId, _n1: G1::NodeId) -> bool { 166 true 167 } 168 } 169 170 impl<G0, G1, F> NodeMatcher<G0, G1> for F 171 where 172 G0: GraphBase + DataMap, 173 G1: GraphBase + DataMap, 174 F: FnMut(&G0::NodeWeight, &G1::NodeWeight) -> bool, 175 { 176 #[inline] 177 fn enabled() -> bool { 178 true 179 } 180 #[inline] 181 fn eq(&mut self, g0: &G0, g1: &G1, n0: G0::NodeId, n1: G1::NodeId) -> bool { 182 if let (Some(x), Some(y)) = (g0.node_weight(n0), g1.node_weight(n1)) { 183 self(x, y) 184 } else { 185 false 186 } 187 } 188 } 189 190 pub trait EdgeMatcher<G0: GraphBase, G1: GraphBase> { 191 fn enabled() -> bool; 192 fn eq( index(&self, index: FasNodeIndex) -> &Self::Output193 &mut self, 194 _g0: &G0, 195 _g1: &G1, 196 e0: (G0::NodeId, G0::NodeId), 197 e1: (G1::NodeId, G1::NodeId), 198 ) -> bool; index_mut(&mut self, index: FasNodeIndex) -> &mut Self::Output199 } 200 201 impl<G0: GraphBase, G1: GraphBase> EdgeMatcher<G0, G1> for NoSemanticMatch { 202 #[inline] 203 fn enabled() -> bool { 204 false 205 } 206 #[inline] 207 fn eq( 208 &mut self, 209 _g0: &G0, 210 _g1: &G1, 211 _e0: (G0::NodeId, G0::NodeId), 212 _e1: (G1::NodeId, G1::NodeId), 213 ) -> bool { 214 true 215 } 216 } 217 218 impl<G0, G1, F> EdgeMatcher<G0, G1> for F 219 where 220 G0: GraphBase + DataMap + IntoEdgesDirected, 221 G1: GraphBase + DataMap + IntoEdgesDirected, 222 F: FnMut(&G0::EdgeWeight, &G1::EdgeWeight) -> bool, 223 { 224 #[inline] 225 fn enabled() -> bool { 226 true 227 } 228 #[inline] 229 fn eq( 230 &mut self, 231 g0: &G0, 232 g1: &G1, 233 e0: (G0::NodeId, G0::NodeId), 234 e1: (G1::NodeId, G1::NodeId), 235 ) -> bool { 236 let w0 = g0 237 .edges_directed(e0.0, Outgoing) 238 .find(|edge| edge.target() == e0.1) suitable_bucket( &mut self, ix: FasNodeIndex, nodes: &mut FasNodeContainer, ) -> &mut NodeLinkedList239 .and_then(|edge| g0.edge_weight(edge.id())); 240 let w1 = g1 241 .edges_directed(e1.0, Outgoing) 242 .find(|edge| edge.target() == e1.1) 243 .and_then(|edge| g1.edge_weight(edge.id())); 244 if let (Some(x), Some(y)) = (w0, w1) { 245 self(x, y) 246 } else { 247 false 248 } 249 } 250 } 251 } 252 253 mod matching { 254 use super::*; 255 256 #[derive(Copy, Clone, PartialEq, Debug)] 257 enum OpenList { 258 Out, 259 In, 260 Other, 261 } 262 263 #[derive(Clone, PartialEq, Debug)] 264 enum Frame<G0, G1> 265 where 266 G0: GraphBase, 267 G1: GraphBase, 268 { 269 Outer, 270 Inner { 271 nodes: (G0::NodeId, G1::NodeId), 272 open_list: OpenList, 273 }, 274 Unwind { update_neighbour_node_buckets(&mut self, ix: FasNodeIndex, nodes: &mut FasNodeContainer)275 nodes: (G0::NodeId, G1::NodeId), 276 open_list: OpenList, 277 }, 278 } 279 280 fn is_feasible<G0, G1, NM, EM>( 281 st: &mut (Vf2State<'_, G0>, Vf2State<'_, G1>), 282 nodes: (G0::NodeId, G1::NodeId), 283 node_match: &mut NM, 284 edge_match: &mut EM, 285 ) -> bool 286 where 287 G0: GetAdjacencyMatrix + GraphProp + NodeCompactIndexable + IntoNeighborsDirected, 288 G1: GetAdjacencyMatrix + GraphProp + NodeCompactIndexable + IntoNeighborsDirected, 289 NM: NodeMatcher<G0, G1>, 290 EM: EdgeMatcher<G0, G1>, 291 { 292 macro_rules! field { 293 ($x:ident, 0) => { 294 $x.0 295 }; 296 ($x:ident, 1) => { 297 $x.1 298 }; 299 ($x:ident, 1 - 0) => { 300 $x.1 301 }; 302 ($x:ident, 1 - 1) => { 303 $x.0 304 }; 305 } 306 307 macro_rules! r_succ { 308 ($j:tt) => {{ 309 let mut succ_count = 0; 310 for n_neigh in field!(st, $j) 311 .graph 312 .neighbors_directed(field!(nodes, $j), Outgoing) 313 { 314 succ_count += 1; 315 // handle the self loop case; it's not in the mapping (yet) 316 let m_neigh = if field!(nodes, $j) != n_neigh { 317 field!(st, $j).mapping[field!(st, $j).graph.to_index(n_neigh)] 318 } else { 319 field!(st, 1 - $j).graph.to_index(field!(nodes, 1 - $j)) 320 }; 321 if m_neigh == std::usize::MAX { 322 continue; 323 } 324 let has_edge = field!(st, 1 - $j).graph.is_adjacent( 325 &field!(st, 1 - $j).adjacency_matrix, 326 field!(nodes, 1 - $j), 327 field!(st, 1 - $j).graph.from_index(m_neigh), 328 ); 329 if !has_edge { 330 return false; 331 } 332 } 333 succ_count 334 }}; 335 } 336 337 macro_rules! r_pred { 338 ($j:tt) => {{ 339 let mut pred_count = 0; 340 for n_neigh in field!(st, $j) 341 .graph 342 .neighbors_directed(field!(nodes, $j), Incoming) 343 { 344 pred_count += 1; 345 // the self loop case is handled in outgoing 346 let m_neigh = field!(st, $j).mapping[field!(st, $j).graph.to_index(n_neigh)]; 347 if m_neigh == std::usize::MAX { 348 continue; 349 } 350 let has_edge = field!(st, 1 - $j).graph.is_adjacent( 351 &field!(st, 1 - $j).adjacency_matrix, 352 field!(st, 1 - $j).graph.from_index(m_neigh), 353 field!(nodes, 1 - $j), 354 ); 355 if !has_edge { 356 return false; 357 } 358 } 359 pred_count 360 }}; 361 } 362 363 // Check syntactic feasibility of mapping by ensuring adjacencies 364 // of nx map to adjacencies of mx. 365 // 366 // nx == map to => mx 367 // 368 // R_succ 369 // 370 // Check that every neighbor of nx is mapped to a neighbor of mx, 371 // then check the reverse, from mx to nx. Check that they have the same 372 // count of edges. 373 // 374 // Note: We want to check the lookahead measures here if we can, 375 // R_out: Equal for G0, G1: Card(Succ(G, n) ^ Tout); for both Succ and Pred 376 // R_in: Same with Tin 377 // R_new: Equal for G0, G1: Ñ n Pred(G, n); both Succ and Pred, 378 // Ñ is G0 - M - Tin - Tout 379 // last attempt to add these did not speed up any of the testcases 380 if r_succ!(0) > r_succ!(1) { 381 return false; 382 } 383 // R_pred 384 if st.0.graph.is_directed() && r_pred!(0) > r_pred!(1) { 385 return false; 386 } 387 388 // // semantic feasibility: compare associated data for nodes 389 if NM::enabled() && !node_match.eq(st.0.graph, st.1.graph, nodes.0, nodes.1) { 390 return false; 391 } 392 // semantic feasibility: compare associated data for edges 393 if EM::enabled() { 394 macro_rules! edge_feasibility { 395 ($j:tt) => {{ 396 for n_neigh in field!(st, $j) 397 .graph 398 .neighbors_directed(field!(nodes, $j), Outgoing) 399 { 400 let m_neigh = if field!(nodes, $j) != n_neigh { 401 field!(st, $j).mapping[field!(st, $j).graph.to_index(n_neigh)] 402 } else { 403 field!(st, 1 - $j).graph.to_index(field!(nodes, 1 - $j)) 404 }; 405 if m_neigh == std::usize::MAX { 406 continue; 407 } 408 409 let e0 = (field!(nodes, $j), n_neigh); 410 let e1 = ( 411 field!(nodes, 1 - $j), 412 field!(st, 1 - $j).graph.from_index(m_neigh), 413 ); 414 let edges = (e0, e1); 415 if !edge_match.eq( 416 st.0.graph, 417 st.1.graph, 418 field!(edges, $j), 419 field!(edges, 1 - $j), 420 ) { 421 return false; 422 } 423 } 424 if field!(st, $j).graph.is_directed() { 425 for n_neigh in field!(st, $j) 426 .graph 427 .neighbors_directed(field!(nodes, $j), Incoming) 428 { 429 // the self loop case is handled in outgoing 430 let m_neigh = 431 field!(st, $j).mapping[field!(st, $j).graph.to_index(n_neigh)]; 432 if m_neigh == std::usize::MAX { 433 continue; 434 } 435 436 let e0 = (n_neigh, field!(nodes, $j)); 437 let e1 = ( 438 field!(st, 1 - $j).graph.from_index(m_neigh), 439 field!(nodes, 1 - $j), 440 ); 441 let edges = (e0, e1); 442 if !edge_match.eq( 443 st.0.graph, 444 st.1.graph, 445 field!(edges, $j), 446 field!(edges, 1 - $j), 447 ) { 448 return false; 449 } 450 } 451 } 452 }}; 453 } 454 455 edge_feasibility!(0); 456 edge_feasibility!(1); 457 } 458 true 459 } 460 461 fn next_candidate<G0, G1>( 462 st: &mut (Vf2State<'_, G0>, Vf2State<'_, G1>), 463 ) -> Option<(G0::NodeId, G1::NodeId, OpenList)> 464 where 465 G0: GetAdjacencyMatrix + GraphProp + NodeCompactIndexable + IntoNeighborsDirected, 466 G1: GetAdjacencyMatrix + GraphProp + NodeCompactIndexable + IntoNeighborsDirected, 467 { 468 let mut from_index = None; 469 let mut open_list = OpenList::Out; 470 let mut to_index = st.1.next_out_index(0); 471 472 // Try the out list 473 if to_index.is_some() { 474 from_index = st.0.next_out_index(0); 475 open_list = OpenList::Out; 476 } 477 // Try the in list 478 if to_index.is_none() || from_index.is_none() { 479 to_index = st.1.next_in_index(0); 480 481 if to_index.is_some() { 482 from_index = st.0.next_in_index(0); 483 open_list = OpenList::In; 484 } 485 } 486 // Try the other list -- disconnected graph 487 if to_index.is_none() || from_index.is_none() { 488 to_index = st.1.next_rest_index(0); 489 if to_index.is_some() { 490 from_index = st.0.next_rest_index(0); 491 open_list = OpenList::Other; 492 } 493 } 494 match (from_index, to_index) { 495 (Some(n), Some(m)) => Some(( 496 st.0.graph.from_index(n), 497 st.1.graph.from_index(m), 498 open_list, 499 )), 500 // No more candidates 501 _ => None, 502 } 503 } 504 505 fn next_from_ix<G0, G1>( 506 st: &mut (Vf2State<'_, G0>, Vf2State<'_, G1>), 507 nx: G0::NodeId, 508 open_list: OpenList, 509 ) -> Option<G0::NodeId> 510 where 511 G0: GetAdjacencyMatrix + GraphProp + NodeCompactIndexable + IntoNeighborsDirected, 512 G1: GetAdjacencyMatrix + GraphProp + NodeCompactIndexable + IntoNeighborsDirected, 513 { 514 // Find the next node index to try on the `from` side of the mapping 515 let start = st.0.graph.to_index(nx) + 1; 516 let cand0 = match open_list { 517 OpenList::Out => st.0.next_out_index(start), 518 OpenList::In => st.0.next_in_index(start), 519 OpenList::Other => st.0.next_rest_index(start), 520 } 521 .map(|c| c + start); // compensate for start offset. 522 match cand0 { 523 None => None, // no more candidates 524 Some(ix) => { 525 debug_assert!(ix >= start); 526 Some(st.0.graph.from_index(ix)) 527 } 528 } 529 } 530 531 fn pop_state<G0, G1>( 532 st: &mut (Vf2State<'_, G0>, Vf2State<'_, G1>), 533 nodes: (G0::NodeId, G1::NodeId), 534 ) where 535 G0: GetAdjacencyMatrix + GraphProp + NodeCompactIndexable + IntoNeighborsDirected, 536 G1: GetAdjacencyMatrix + GraphProp + NodeCompactIndexable + IntoNeighborsDirected, 537 { 538 st.0.pop_mapping(nodes.0); 539 st.1.pop_mapping(nodes.1); 540 } 541 542 fn push_state<G0, G1>( 543 st: &mut (Vf2State<'_, G0>, Vf2State<'_, G1>), 544 nodes: (G0::NodeId, G1::NodeId), 545 ) where 546 G0: GetAdjacencyMatrix + GraphProp + NodeCompactIndexable + IntoNeighborsDirected, 547 G1: GetAdjacencyMatrix + GraphProp + NodeCompactIndexable + IntoNeighborsDirected, 548 { 549 st.0.push_mapping(nodes.0, st.1.graph.to_index(nodes.1)); 550 st.1.push_mapping(nodes.1, st.0.graph.to_index(nodes.0)); 551 } 552 553 /// Return Some(bool) if isomorphism is decided, else None. 554 pub fn try_match<G0, G1, NM, EM>( 555 mut st: &mut (Vf2State<'_, G0>, Vf2State<'_, G1>), 556 node_match: &mut NM, 557 edge_match: &mut EM, 558 ) -> Option<bool> 559 where 560 G0: NodeCompactIndexable 561 + EdgeCount 562 + GetAdjacencyMatrix 563 + GraphProp 564 + IntoNeighborsDirected, 565 G1: NodeCompactIndexable 566 + EdgeCount 567 + GetAdjacencyMatrix 568 + GraphProp 569 + IntoNeighborsDirected, 570 NM: NodeMatcher<G0, G1>, 571 EM: EdgeMatcher<G0, G1>, 572 { 573 if st.0.is_complete() { 574 return Some(true); 575 } 576 577 // A "depth first" search of a valid mapping from graph 1 to graph 2 578 // F(s, n, m) -- evaluate state s and add mapping n <-> m 579 // Find least T1out node (in st.out[1] but not in M[1]) 580 let mut stack: Vec<Frame<G0, G1>> = vec![Frame::Outer]; 581 while let Some(frame) = stack.pop() { 582 match frame { 583 Frame::Unwind { nodes, open_list } => { 584 pop_state(&mut st, nodes); 585 586 match next_from_ix(&mut st, nodes.0, open_list) { 587 None => continue, 588 Some(nx) => { 589 let f = Frame::Inner { 590 nodes: (nx, nodes.1), 591 open_list, 592 }; 593 stack.push(f); 594 } 595 } 596 } 597 Frame::Outer => match next_candidate(&mut st) { 598 None => continue, 599 Some((nx, mx, open_list)) => { 600 let f = Frame::Inner { 601 nodes: (nx, mx), 602 open_list, 603 }; 604 stack.push(f); 605 } 606 }, 607 Frame::Inner { nodes, open_list } => { 608 if is_feasible(&mut st, nodes, node_match, edge_match) { 609 push_state(&mut st, nodes); 610 if st.0.is_complete() { 611 return Some(true); 612 } 613 // Check cardinalities of Tin, Tout sets 614 if st.0.out_size == st.1.out_size && st.0.ins_size == st.1.ins_size { 615 let f0 = Frame::Unwind { nodes, open_list }; 616 stack.push(f0); 617 stack.push(Frame::Outer); 618 continue; 619 } 620 pop_state(&mut st, nodes); 621 } 622 match next_from_ix(&mut st, nodes.0, open_list) { 623 None => continue, 624 Some(nx) => { 625 let f = Frame::Inner { 626 nodes: (nx, nodes.1), 627 open_list, 628 }; 629 stack.push(f); 630 } 631 } 632 } 633 } 634 } 635 None 636 } 637 } 638 639 /// \[Generic\] Return `true` if the graphs `g0` and `g1` are isomorphic. 640 /// 641 /// Using the VF2 algorithm, only matching graph syntactically (graph 642 /// structure). 643 /// 644 /// The graphs should not be multigraphs. 645 /// 646 /// **Reference** 647 /// 648 /// * Luigi P. Cordella, Pasquale Foggia, Carlo Sansone, Mario Vento; 649 /// *A (Sub)Graph Isomorphism Algorithm for Matching Large Graphs* 650 pub fn is_isomorphic<G0, G1>(g0: G0, g1: G1) -> bool 651 where 652 G0: NodeCompactIndexable + EdgeCount + GetAdjacencyMatrix + GraphProp + IntoNeighborsDirected, 653 G1: NodeCompactIndexable 654 + EdgeCount 655 + GetAdjacencyMatrix 656 + GraphProp<EdgeType = G0::EdgeType> 657 + IntoNeighborsDirected, 658 { 659 if g0.node_count() != g1.node_count() || g0.edge_count() != g1.edge_count() { 660 return false; 661 } 662 663 let mut st = (Vf2State::new(&g0), Vf2State::new(&g1)); 664 self::matching::try_match(&mut st, &mut NoSemanticMatch, &mut NoSemanticMatch).unwrap_or(false) 665 } 666 667 /// \[Generic\] Return `true` if the graphs `g0` and `g1` are isomorphic. 668 /// 669 /// Using the VF2 algorithm, examining both syntactic and semantic 670 /// graph isomorphism (graph structure and matching node and edge weights). 671 /// 672 /// The graphs should not be multigraphs. 673 pub fn is_isomorphic_matching<G0, G1, NM, EM>( 674 g0: G0, 675 g1: G1, 676 mut node_match: NM, 677 mut edge_match: EM, 678 ) -> bool 679 where 680 G0: NodeCompactIndexable 681 + EdgeCount 682 + DataMap 683 + GetAdjacencyMatrix 684 + GraphProp 685 + IntoEdgesDirected, 686 G1: NodeCompactIndexable 687 + EdgeCount 688 + DataMap 689 + GetAdjacencyMatrix 690 + GraphProp<EdgeType = G0::EdgeType> 691 + IntoEdgesDirected, 692 NM: FnMut(&G0::NodeWeight, &G1::NodeWeight) -> bool, 693 EM: FnMut(&G0::EdgeWeight, &G1::EdgeWeight) -> bool, 694 { 695 if g0.node_count() != g1.node_count() || g0.edge_count() != g1.edge_count() { 696 return false; 697 } 698 699 let mut st = (Vf2State::new(&g0), Vf2State::new(&g1)); 700 self::matching::try_match(&mut st, &mut node_match, &mut edge_match).unwrap_or(false) 701 } 702 703 /// \[Generic\] Return `true` if `g0` is isomorphic to a subgraph of `g1`. 704 /// 705 /// Using the VF2 algorithm, only matching graph syntactically (graph 706 /// structure). 707 /// 708 /// The graphs should not be multigraphs. 709 /// 710 /// # Subgraph isomorphism 711 /// 712 /// (adapted from [`networkx` documentation](https://networkx.github.io/documentation/stable/reference/algorithms/isomorphism.vf2.html)) 713 /// 714 /// Graph theory literature can be ambiguous about the meaning of the above statement, 715 /// and we seek to clarify it now. 716 /// 717 /// In the VF2 literature, a mapping **M** is said to be a *graph-subgraph isomorphism* 718 /// iff **M** is an isomorphism between **G2** and a subgraph of **G1**. Thus, to say 719 /// that **G1** and **G2** are graph-subgraph isomorphic is to say that a subgraph of 720 /// **G1** is isomorphic to **G2**. 721 /// 722 /// Other literature uses the phrase ‘subgraph isomorphic’ as in 723 /// ‘**G1** does not have a subgraph isomorphic to **G2**’. Another use is as an in adverb 724 /// for isomorphic. Thus, to say that **G1** and **G2** are subgraph isomorphic is to say 725 /// that a subgraph of **G1** is isomorphic to **G2**. 726 /// 727 /// Finally, the term ‘subgraph’ can have multiple meanings. In this context, 728 /// ‘subgraph’ always means a ‘node-induced subgraph’. Edge-induced subgraph 729 /// isomorphisms are not directly supported. For subgraphs which are not 730 /// induced, the term ‘monomorphism’ is preferred over ‘isomorphism’. 731 /// 732 /// **Reference** 733 /// 734 /// * Luigi P. Cordella, Pasquale Foggia, Carlo Sansone, Mario Vento; 735 /// *A (Sub)Graph Isomorphism Algorithm for Matching Large Graphs* 736 pub fn is_isomorphic_subgraph<G0, G1>(g0: G0, g1: G1) -> bool 737 where 738 G0: NodeCompactIndexable + EdgeCount + GetAdjacencyMatrix + GraphProp + IntoNeighborsDirected, 739 G1: NodeCompactIndexable 740 + EdgeCount 741 + GetAdjacencyMatrix 742 + GraphProp<EdgeType = G0::EdgeType> 743 + IntoNeighborsDirected, 744 { 745 if g0.node_count() > g1.node_count() || g0.edge_count() > g1.edge_count() { 746 return false; 747 } 748 749 let mut st = (Vf2State::new(&g0), Vf2State::new(&g1)); 750 self::matching::try_match(&mut st, &mut NoSemanticMatch, &mut NoSemanticMatch).unwrap_or(false) 751 } 752 753 /// \[Generic\] Return `true` if `g0` is isomorphic to a subgraph of `g1`. 754 /// 755 /// Using the VF2 algorithm, examining both syntactic and semantic 756 /// graph isomorphism (graph structure and matching node and edge weights). 757 /// 758 /// The graphs should not be multigraphs. 759 pub fn is_isomorphic_subgraph_matching<G0, G1, NM, EM>( 760 g0: G0, 761 g1: G1, 762 mut node_match: NM, 763 mut edge_match: EM, 764 ) -> bool 765 where 766 G0: NodeCompactIndexable 767 + EdgeCount 768 + DataMap 769 + GetAdjacencyMatrix 770 + GraphProp 771 + IntoEdgesDirected, 772 G1: NodeCompactIndexable 773 + EdgeCount 774 + DataMap 775 + GetAdjacencyMatrix 776 + GraphProp<EdgeType = G0::EdgeType> 777 + IntoEdgesDirected, 778 NM: FnMut(&G0::NodeWeight, &G1::NodeWeight) -> bool, 779 EM: FnMut(&G0::EdgeWeight, &G1::EdgeWeight) -> bool, 780 { 781 if g0.node_count() > g1.node_count() || g0.edge_count() > g1.edge_count() { 782 return false; 783 } 784 785 let mut st = (Vf2State::new(&g0), Vf2State::new(&g1)); 786 self::matching::try_match(&mut st, &mut node_match, &mut edge_match).unwrap_or(false) 787 } 788