| use super::data::DataMap; |
| use super::visit::EdgeCount; |
| use super::visit::EdgeRef; |
| use super::visit::GetAdjacencyMatrix; |
| use super::visit::GraphBase; |
| use super::visit::GraphProp; |
| use super::visit::IntoEdgesDirected; |
| use super::visit::IntoNeighborsDirected; |
| use super::visit::NodeCompactIndexable; |
| use super::{Incoming, Outgoing}; |
| |
| use self::semantic::EdgeMatcher; |
| use self::semantic::NoSemanticMatch; |
| use self::semantic::NodeMatcher; |
| use self::state::Vf2State; |
| |
| mod state { |
| use super::*; |
| |
| #[derive(Debug)] |
| // TODO: make mapping generic over the index type of the other graph. |
| pub struct Vf2State<'a, G: GetAdjacencyMatrix> { |
| /// A reference to the graph this state was built from. |
| pub graph: &'a G, |
| /// The current mapping M(s) of nodes from G0 → G1 and G1 → G0, |
| /// `usize::MAX` for no mapping. |
| pub mapping: Vec<usize>, |
| /// out[i] is non-zero if i is in either M_0(s) or Tout_0(s) |
| /// These are all the next vertices that are not mapped yet, but |
| /// have an outgoing edge from the mapping. |
| out: Vec<usize>, |
| /// ins[i] is non-zero if i is in either M_0(s) or Tin_0(s) |
| /// These are all the incoming vertices, those not mapped yet, but |
| /// have an edge from them into the mapping. |
| /// Unused if graph is undirected -- it's identical with out in that case. |
| ins: Vec<usize>, |
| pub out_size: usize, |
| pub ins_size: usize, |
| pub adjacency_matrix: G::AdjMatrix, |
| generation: usize, |
| } |
| |
| impl<'a, G> Vf2State<'a, G> |
| where |
| G: GetAdjacencyMatrix + GraphProp + NodeCompactIndexable + IntoNeighborsDirected, |
| { |
| pub fn new(g: &'a G) -> Self { |
| let c0 = g.node_count(); |
| Vf2State { |
| graph: g, |
| mapping: vec![std::usize::MAX; c0], |
| out: vec![0; c0], |
| ins: vec![0; c0 * (g.is_directed() as usize)], |
| out_size: 0, |
| ins_size: 0, |
| adjacency_matrix: g.adjacency_matrix(), |
| generation: 0, |
| } |
| } |
| |
| /// Return **true** if we have a complete mapping |
| pub fn is_complete(&self) -> bool { |
| self.generation == self.mapping.len() |
| } |
| |
| /// Add mapping **from** <-> **to** to the state. |
| pub fn push_mapping(&mut self, from: G::NodeId, to: usize) { |
| self.generation += 1; |
| self.mapping[self.graph.to_index(from)] = to; |
| // update T0 & T1 ins/outs |
| // T0out: Node in G0 not in M0 but successor of a node in M0. |
| // st.out[0]: Node either in M0 or successor of M0 |
| for ix in self.graph.neighbors_directed(from, Outgoing) { |
| if self.out[self.graph.to_index(ix)] == 0 { |
| self.out[self.graph.to_index(ix)] = self.generation; |
| self.out_size += 1; |
| } |
| } |
| if self.graph.is_directed() { |
| for ix in self.graph.neighbors_directed(from, Incoming) { |
| if self.ins[self.graph.to_index(ix)] == 0 { |
| self.ins[self.graph.to_index(ix)] = self.generation; |
| self.ins_size += 1; |
| } |
| } |
| } |
| } |
| |
| /// Restore the state to before the last added mapping |
| pub fn pop_mapping(&mut self, from: G::NodeId) { |
| // undo (n, m) mapping |
| self.mapping[self.graph.to_index(from)] = std::usize::MAX; |
| |
| // unmark in ins and outs |
| for ix in self.graph.neighbors_directed(from, Outgoing) { |
| if self.out[self.graph.to_index(ix)] == self.generation { |
| self.out[self.graph.to_index(ix)] = 0; |
| self.out_size -= 1; |
| } |
| } |
| if self.graph.is_directed() { |
| for ix in self.graph.neighbors_directed(from, Incoming) { |
| if self.ins[self.graph.to_index(ix)] == self.generation { |
| self.ins[self.graph.to_index(ix)] = 0; |
| self.ins_size -= 1; |
| } |
| } |
| } |
| |
| self.generation -= 1; |
| } |
| |
| /// Find the next (least) node in the Tout set. |
| pub fn next_out_index(&self, from_index: usize) -> Option<usize> { |
| self.out[from_index..] |
| .iter() |
| .enumerate() |
| .find(move |&(index, &elt)| { |
| elt > 0 && self.mapping[from_index + index] == std::usize::MAX |
| }) |
| .map(|(index, _)| index) |
| } |
| |
| /// Find the next (least) node in the Tin set. |
| pub fn next_in_index(&self, from_index: usize) -> Option<usize> { |
| if !self.graph.is_directed() { |
| return None; |
| } |
| self.ins[from_index..] |
| .iter() |
| .enumerate() |
| .find(move |&(index, &elt)| { |
| elt > 0 && self.mapping[from_index + index] == std::usize::MAX |
| }) |
| .map(|(index, _)| index) |
| } |
| |
| /// Find the next (least) node in the N - M set. |
| pub fn next_rest_index(&self, from_index: usize) -> Option<usize> { |
| self.mapping[from_index..] |
| .iter() |
| .enumerate() |
| .find(|&(_, &elt)| elt == std::usize::MAX) |
| .map(|(index, _)| index) |
| } |
| } |
| } |
| |
| mod semantic { |
| use super::*; |
| |
| pub struct NoSemanticMatch; |
| |
| pub trait NodeMatcher<G0: GraphBase, G1: GraphBase> { |
| fn enabled() -> bool; |
| fn eq(&mut self, _g0: &G0, _g1: &G1, _n0: G0::NodeId, _n1: G1::NodeId) -> bool; |
| } |
| |
| impl<G0: GraphBase, G1: GraphBase> NodeMatcher<G0, G1> for NoSemanticMatch { |
| #[inline] |
| fn enabled() -> bool { |
| false |
| } |
| #[inline] |
| fn eq(&mut self, _g0: &G0, _g1: &G1, _n0: G0::NodeId, _n1: G1::NodeId) -> bool { |
| true |
| } |
| } |
| |
| impl<G0, G1, F> NodeMatcher<G0, G1> for F |
| where |
| G0: GraphBase + DataMap, |
| G1: GraphBase + DataMap, |
| F: FnMut(&G0::NodeWeight, &G1::NodeWeight) -> bool, |
| { |
| #[inline] |
| fn enabled() -> bool { |
| true |
| } |
| #[inline] |
| fn eq(&mut self, g0: &G0, g1: &G1, n0: G0::NodeId, n1: G1::NodeId) -> bool { |
| if let (Some(x), Some(y)) = (g0.node_weight(n0), g1.node_weight(n1)) { |
| self(x, y) |
| } else { |
| false |
| } |
| } |
| } |
| |
| pub trait EdgeMatcher<G0: GraphBase, G1: GraphBase> { |
| fn enabled() -> bool; |
| fn eq( |
| &mut self, |
| _g0: &G0, |
| _g1: &G1, |
| e0: (G0::NodeId, G0::NodeId), |
| e1: (G1::NodeId, G1::NodeId), |
| ) -> bool; |
| } |
| |
| impl<G0: GraphBase, G1: GraphBase> EdgeMatcher<G0, G1> for NoSemanticMatch { |
| #[inline] |
| fn enabled() -> bool { |
| false |
| } |
| #[inline] |
| fn eq( |
| &mut self, |
| _g0: &G0, |
| _g1: &G1, |
| _e0: (G0::NodeId, G0::NodeId), |
| _e1: (G1::NodeId, G1::NodeId), |
| ) -> bool { |
| true |
| } |
| } |
| |
| impl<G0, G1, F> EdgeMatcher<G0, G1> for F |
| where |
| G0: GraphBase + DataMap + IntoEdgesDirected, |
| G1: GraphBase + DataMap + IntoEdgesDirected, |
| F: FnMut(&G0::EdgeWeight, &G1::EdgeWeight) -> bool, |
| { |
| #[inline] |
| fn enabled() -> bool { |
| true |
| } |
| #[inline] |
| fn eq( |
| &mut self, |
| g0: &G0, |
| g1: &G1, |
| e0: (G0::NodeId, G0::NodeId), |
| e1: (G1::NodeId, G1::NodeId), |
| ) -> bool { |
| let w0 = g0 |
| .edges_directed(e0.0, Outgoing) |
| .find(|edge| edge.target() == e0.1) |
| .and_then(|edge| g0.edge_weight(edge.id())); |
| let w1 = g1 |
| .edges_directed(e1.0, Outgoing) |
| .find(|edge| edge.target() == e1.1) |
| .and_then(|edge| g1.edge_weight(edge.id())); |
| if let (Some(x), Some(y)) = (w0, w1) { |
| self(x, y) |
| } else { |
| false |
| } |
| } |
| } |
| } |
| |
| mod matching { |
| use super::*; |
| |
| #[derive(Copy, Clone, PartialEq, Debug)] |
| enum OpenList { |
| Out, |
| In, |
| Other, |
| } |
| |
| #[derive(Clone, PartialEq, Debug)] |
| enum Frame<G0, G1> |
| where |
| G0: GraphBase, |
| G1: GraphBase, |
| { |
| Outer, |
| Inner { |
| nodes: (G0::NodeId, G1::NodeId), |
| open_list: OpenList, |
| }, |
| Unwind { |
| nodes: (G0::NodeId, G1::NodeId), |
| open_list: OpenList, |
| }, |
| } |
| |
| fn 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>, |
| { |
| macro_rules! field { |
| ($x:ident, 0) => { |
| $x.0 |
| }; |
| ($x:ident, 1) => { |
| $x.1 |
| }; |
| ($x:ident, 1 - 0) => { |
| $x.1 |
| }; |
| ($x:ident, 1 - 1) => { |
| $x.0 |
| }; |
| } |
| |
| macro_rules! r_succ { |
| ($j:tt) => {{ |
| let mut succ_count = 0; |
| for n_neigh in field!(st, $j) |
| .graph |
| .neighbors_directed(field!(nodes, $j), Outgoing) |
| { |
| succ_count += 1; |
| // handle the self loop case; it's not in the mapping (yet) |
| let m_neigh = if field!(nodes, $j) != n_neigh { |
| field!(st, $j).mapping[field!(st, $j).graph.to_index(n_neigh)] |
| } else { |
| field!(st, 1 - $j).graph.to_index(field!(nodes, 1 - $j)) |
| }; |
| if m_neigh == std::usize::MAX { |
| continue; |
| } |
| let has_edge = field!(st, 1 - $j).graph.is_adjacent( |
| &field!(st, 1 - $j).adjacency_matrix, |
| field!(nodes, 1 - $j), |
| field!(st, 1 - $j).graph.from_index(m_neigh), |
| ); |
| if !has_edge { |
| return false; |
| } |
| } |
| succ_count |
| }}; |
| } |
| |
| macro_rules! r_pred { |
| ($j:tt) => {{ |
| let mut pred_count = 0; |
| for n_neigh in field!(st, $j) |
| .graph |
| .neighbors_directed(field!(nodes, $j), Incoming) |
| { |
| pred_count += 1; |
| // the self loop case is handled in outgoing |
| let m_neigh = field!(st, $j).mapping[field!(st, $j).graph.to_index(n_neigh)]; |
| if m_neigh == std::usize::MAX { |
| continue; |
| } |
| let has_edge = field!(st, 1 - $j).graph.is_adjacent( |
| &field!(st, 1 - $j).adjacency_matrix, |
| field!(st, 1 - $j).graph.from_index(m_neigh), |
| field!(nodes, 1 - $j), |
| ); |
| if !has_edge { |
| return false; |
| } |
| } |
| pred_count |
| }}; |
| } |
| |
| // Check syntactic feasibility of mapping by ensuring adjacencies |
| // of nx map to adjacencies of mx. |
| // |
| // nx == map to => mx |
| // |
| // R_succ |
| // |
| // Check that every neighbor of nx is mapped to a neighbor of mx, |
| // then check the reverse, from mx to nx. Check that they have the same |
| // count of edges. |
| // |
| // Note: We want to check the lookahead measures here if we can, |
| // R_out: Equal for G0, G1: Card(Succ(G, n) ^ Tout); for both Succ and Pred |
| // R_in: Same with Tin |
| // R_new: Equal for G0, G1: Ñ n Pred(G, n); both Succ and Pred, |
| // Ñ is G0 - M - Tin - Tout |
| // last attempt to add these did not speed up any of the testcases |
| if r_succ!(0) > r_succ!(1) { |
| return false; |
| } |
| // R_pred |
| if st.0.graph.is_directed() { |
| if r_pred!(0) > r_pred!(1) { |
| return false; |
| } |
| } |
| |
| // // semantic feasibility: compare associated data for nodes |
| if NM::enabled() { |
| if !node_match.eq(st.0.graph, st.1.graph, nodes.0, nodes.1) { |
| return false; |
| } |
| } |
| // semantic feasibility: compare associated data for edges |
| if EM::enabled() { |
| macro_rules! edge_feasibility { |
| ($j:tt) => {{ |
| for n_neigh in field!(st, $j) |
| .graph |
| .neighbors_directed(field!(nodes, $j), Outgoing) |
| { |
| let m_neigh = if field!(nodes, $j) != n_neigh { |
| field!(st, $j).mapping[field!(st, $j).graph.to_index(n_neigh)] |
| } else { |
| field!(st, 1 - $j).graph.to_index(field!(nodes, 1 - $j)) |
| }; |
| if m_neigh == std::usize::MAX { |
| continue; |
| } |
| |
| let e0 = (field!(nodes, $j), n_neigh); |
| let e1 = ( |
| field!(nodes, 1 - $j), |
| field!(st, 1 - $j).graph.from_index(m_neigh), |
| ); |
| let edges = (e0, e1); |
| if !edge_match.eq( |
| st.0.graph, |
| st.1.graph, |
| field!(edges, $j), |
| field!(edges, 1 - $j), |
| ) { |
| return false; |
| } |
| } |
| if field!(st, $j).graph.is_directed() { |
| for n_neigh in field!(st, $j) |
| .graph |
| .neighbors_directed(field!(nodes, $j), Incoming) |
| { |
| // the self loop case is handled in outgoing |
| let m_neigh = |
| field!(st, $j).mapping[field!(st, $j).graph.to_index(n_neigh)]; |
| if m_neigh == std::usize::MAX { |
| continue; |
| } |
| |
| let e0 = (n_neigh, field!(nodes, $j)); |
| let e1 = ( |
| field!(st, 1 - $j).graph.from_index(m_neigh), |
| field!(nodes, 1 - $j), |
| ); |
| let edges = (e0, e1); |
| if !edge_match.eq( |
| st.0.graph, |
| st.1.graph, |
| field!(edges, $j), |
| field!(edges, 1 - $j), |
| ) { |
| return false; |
| } |
| } |
| } |
| }}; |
| } |
| |
| edge_feasibility!(0); |
| edge_feasibility!(1); |
| } |
| true |
| } |
| |
| fn 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, |
| { |
| let mut from_index = None; |
| let mut open_list = OpenList::Out; |
| let mut to_index = st.1.next_out_index(0); |
| |
| // Try the out list |
| if to_index.is_some() { |
| from_index = st.0.next_out_index(0); |
| open_list = OpenList::Out; |
| } |
| // Try the in list |
| if to_index.is_none() || from_index.is_none() { |
| to_index = st.1.next_in_index(0); |
| |
| if to_index.is_some() { |
| from_index = st.0.next_in_index(0); |
| open_list = OpenList::In; |
| } |
| } |
| // Try the other list -- disconnected graph |
| if to_index.is_none() || from_index.is_none() { |
| to_index = st.1.next_rest_index(0); |
| if to_index.is_some() { |
| from_index = st.0.next_rest_index(0); |
| open_list = OpenList::Other; |
| } |
| } |
| match (from_index, to_index) { |
| (Some(n), Some(m)) => Some(( |
| st.0.graph.from_index(n), |
| st.1.graph.from_index(m), |
| open_list, |
| )), |
| // No more candidates |
| _ => None, |
| } |
| } |
| |
| fn next_from_ix<G0, G1>( |
| st: &mut (Vf2State<'_, G0>, Vf2State<'_, G1>), |
| nx: G0::NodeId, |
| open_list: OpenList, |
| ) -> Option<G0::NodeId> |
| where |
| G0: GetAdjacencyMatrix + GraphProp + NodeCompactIndexable + IntoNeighborsDirected, |
| G1: GetAdjacencyMatrix + GraphProp + NodeCompactIndexable + IntoNeighborsDirected, |
| { |
| // Find the next node index to try on the `from` side of the mapping |
| let start = st.0.graph.to_index(nx) + 1; |
| let cand0 = match open_list { |
| OpenList::Out => st.0.next_out_index(start), |
| OpenList::In => st.0.next_in_index(start), |
| OpenList::Other => st.0.next_rest_index(start), |
| } |
| .map(|c| c + start); // compensate for start offset. |
| match cand0 { |
| None => None, // no more candidates |
| Some(ix) => { |
| debug_assert!(ix >= start); |
| Some(st.0.graph.from_index(ix)) |
| } |
| } |
| } |
| |
| fn 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, |
| { |
| st.0.pop_mapping(nodes.0); |
| st.1.pop_mapping(nodes.1); |
| } |
| |
| fn 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, |
| { |
| st.0.push_mapping(nodes.0, st.1.graph.to_index(nodes.1)); |
| st.1.push_mapping(nodes.1, st.0.graph.to_index(nodes.0)); |
| } |
| |
| /// Return Some(bool) if isomorphism is decided, else None. |
| pub fn try_match<G0, G1, NM, EM>( |
| mut st: &mut (Vf2State<'_, G0>, Vf2State<'_, G1>), |
| node_match: &mut NM, |
| edge_match: &mut EM, |
| ) -> Option<bool> |
| where |
| G0: NodeCompactIndexable |
| + EdgeCount |
| + GetAdjacencyMatrix |
| + GraphProp |
| + IntoNeighborsDirected, |
| G1: NodeCompactIndexable |
| + EdgeCount |
| + GetAdjacencyMatrix |
| + GraphProp |
| + IntoNeighborsDirected, |
| NM: NodeMatcher<G0, G1>, |
| EM: EdgeMatcher<G0, G1>, |
| { |
| if st.0.is_complete() { |
| return Some(true); |
| } |
| |
| // A "depth first" search of a valid mapping from graph 1 to graph 2 |
| // F(s, n, m) -- evaluate state s and add mapping n <-> m |
| // Find least T1out node (in st.out[1] but not in M[1]) |
| let mut stack: Vec<Frame<G0, G1>> = vec![Frame::Outer]; |
| while let Some(frame) = stack.pop() { |
| match frame { |
| Frame::Unwind { nodes, open_list } => { |
| pop_state(&mut st, nodes); |
| |
| match next_from_ix(&mut st, nodes.0, open_list) { |
| None => continue, |
| Some(nx) => { |
| let f = Frame::Inner { |
| nodes: (nx, nodes.1), |
| open_list, |
| }; |
| stack.push(f); |
| } |
| } |
| } |
| Frame::Outer => match next_candidate(&mut st) { |
| None => continue, |
| Some((nx, mx, open_list)) => { |
| let f = Frame::Inner { |
| nodes: (nx, mx), |
| open_list, |
| }; |
| stack.push(f); |
| } |
| }, |
| Frame::Inner { nodes, open_list } => { |
| if is_feasible(&mut st, nodes, node_match, edge_match) { |
| push_state(&mut st, nodes); |
| if st.0.is_complete() { |
| return Some(true); |
| } |
| // Check cardinalities of Tin, Tout sets |
| if st.0.out_size == st.1.out_size && st.0.ins_size == st.1.ins_size { |
| let f0 = Frame::Unwind { nodes, open_list }; |
| stack.push(f0); |
| stack.push(Frame::Outer); |
| continue; |
| } |
| pop_state(&mut st, nodes); |
| } |
| match next_from_ix(&mut st, nodes.0, open_list) { |
| None => continue, |
| Some(nx) => { |
| let f = Frame::Inner { |
| nodes: (nx, nodes.1), |
| open_list, |
| }; |
| stack.push(f); |
| } |
| } |
| } |
| } |
| } |
| None |
| } |
| } |
| |
| /// \[Generic\] Return `true` if the graphs `g0` and `g1` are isomorphic. |
| /// |
| /// Using the VF2 algorithm, only matching graph syntactically (graph |
| /// structure). |
| /// |
| /// The graphs should not be multigraphs. |
| /// |
| /// **Reference** |
| /// |
| /// * Luigi P. Cordella, Pasquale Foggia, Carlo Sansone, Mario Vento; |
| /// *A (Sub)Graph Isomorphism Algorithm for Matching Large Graphs* |
| pub fn 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, |
| { |
| if g0.node_count() != g1.node_count() || g0.edge_count() != g1.edge_count() { |
| return false; |
| } |
| |
| let mut st = (Vf2State::new(&g0), Vf2State::new(&g1)); |
| self::matching::try_match(&mut st, &mut NoSemanticMatch, &mut NoSemanticMatch).unwrap_or(false) |
| } |
| |
| /// \[Generic\] Return `true` if the graphs `g0` and `g1` are isomorphic. |
| /// |
| /// Using the VF2 algorithm, examining both syntactic and semantic |
| /// graph isomorphism (graph structure and matching node and edge weights). |
| /// |
| /// The graphs should not be multigraphs. |
| pub fn 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, |
| { |
| if g0.node_count() != g1.node_count() || g0.edge_count() != g1.edge_count() { |
| return false; |
| } |
| |
| let mut st = (Vf2State::new(&g0), Vf2State::new(&g1)); |
| self::matching::try_match(&mut st, &mut node_match, &mut edge_match).unwrap_or(false) |
| } |
| |
| /// \[Generic\] Return `true` if `g0` is isomorphic to a subgraph of `g1`. |
| /// |
| /// Using the VF2 algorithm, only matching graph syntactically (graph |
| /// structure). |
| /// |
| /// The graphs should not be multigraphs. |
| /// |
| /// # Subgraph isomorphism |
| /// |
| /// (adapted from [`networkx` documentation](https://networkx.github.io/documentation/stable/reference/algorithms/isomorphism.vf2.html)) |
| /// |
| /// Graph theory literature can be ambiguous about the meaning of the above statement, |
| /// and we seek to clarify it now. |
| /// |
| /// In the VF2 literature, a mapping **M** is said to be a *graph-subgraph isomorphism* |
| /// iff **M** is an isomorphism between **G2** and a subgraph of **G1**. Thus, to say |
| /// that **G1** and **G2** are graph-subgraph isomorphic is to say that a subgraph of |
| /// **G1** is isomorphic to **G2**. |
| /// |
| /// Other literature uses the phrase ‘subgraph isomorphic’ as in |
| /// ‘**G1** does not have a subgraph isomorphic to **G2**’. Another use is as an in adverb |
| /// for isomorphic. Thus, to say that **G1** and **G2** are subgraph isomorphic is to say |
| /// that a subgraph of **G1** is isomorphic to **G2**. |
| /// |
| /// Finally, the term ‘subgraph’ can have multiple meanings. In this context, |
| /// ‘subgraph’ always means a ‘node-induced subgraph’. Edge-induced subgraph |
| /// isomorphisms are not directly supported. For subgraphs which are not |
| /// induced, the term ‘monomorphism’ is preferred over ‘isomorphism’. |
| /// |
| /// **Reference** |
| /// |
| /// * Luigi P. Cordella, Pasquale Foggia, Carlo Sansone, Mario Vento; |
| /// *A (Sub)Graph Isomorphism Algorithm for Matching Large Graphs* |
| pub fn 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, |
| { |
| if g0.node_count() > g1.node_count() || g0.edge_count() > g1.edge_count() { |
| return false; |
| } |
| |
| let mut st = (Vf2State::new(&g0), Vf2State::new(&g1)); |
| self::matching::try_match(&mut st, &mut NoSemanticMatch, &mut NoSemanticMatch).unwrap_or(false) |
| } |
| |
| /// \[Generic\] Return `true` if `g0` is isomorphic to a subgraph of `g1`. |
| /// |
| /// Using the VF2 algorithm, examining both syntactic and semantic |
| /// graph isomorphism (graph structure and matching node and edge weights). |
| /// |
| /// The graphs should not be multigraphs. |
| pub fn 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, |
| { |
| if g0.node_count() > g1.node_count() || g0.edge_count() > g1.edge_count() { |
| return false; |
| } |
| |
| let mut st = (Vf2State::new(&g0), Vf2State::new(&g1)); |
| self::matching::try_match(&mut st, &mut node_match, &mut edge_match).unwrap_or(false) |
| } |