use crate::data::DataMap;
use crate::visit::EdgeCount;
use crate::visit::EdgeRef;
use crate::visit::GetAdjacencyMatrix;
use crate::visit::GraphBase;
use crate::visit::GraphProp;
use crate::visit::IntoEdgesDirected;
use crate::visit::IntoNeighborsDirected;
use crate::visit::NodeCompactIndexable;
use crate::{Incoming, Outgoing};
use self::semantic::EdgeMatcher;
use self::semantic::NoSemanticMatch;
use self::semantic::NodeMatcher;
use self::state::Vf2State;
mod state {
use super::*;
#[derive(Debug)]
pub struct Vf2State<'a, G: GetAdjacencyMatrix> {
pub graph: &'a G,
pub mapping: Vec<usize>,
out: Vec<usize>,
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,
}
}
pub fn is_complete(&self) -> bool {
self.generation == self.mapping.len()
}
pub fn push_mapping(&mut self, from: G::NodeId, to: usize) {
self.generation += 1;
self.mapping[self.graph.to_index(from)] = to;
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;
}
}
}
}
pub fn pop_mapping(&mut self, from: G::NodeId) {
self.mapping[self.graph.to_index(from)] = std::usize::MAX;
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;
}
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)
}
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)
}
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;
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;
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
}};
}
if r_succ!(0) > r_succ!(1) {
return false;
}
if st.0.graph.is_directed() && r_pred!(0) > r_pred!(1) {
return false;
}
if NM::enabled() && !node_match.eq(st.0.graph, st.1.graph, nodes.0, nodes.1) {
return false;
}
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)
{
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);
if to_index.is_some() {
from_index = st.0.next_out_index(0);
open_list = OpenList::Out;
}
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;
}
}
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,
)),
_ => 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,
{
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); match cand0 {
None => None, 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));
}
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);
}
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);
}
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
}
}
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)
}
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)
}
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)
}
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)
}