use log::{debug, trace};
use rand::seq::IteratorRandom;
use rand::seq::SliceRandom;
use rand::thread_rng;
use crate::primitives::{Index, Label};
use crate::{Graph, Isomorphism, Node};
#[must_use]
pub fn match_subgraph<I: Index, NL: Label, EL: Label>(
graph: &Graph<I, NL, EL>,
subgraph: &Graph<I, NL, EL>,
) -> Option<Isomorphism<I>> {
custom(graph, subgraph)
}
fn custom<I: Index, NL: Label, EL: Label>(
graph: &Graph<I, NL, EL>,
subgraph: &Graph<I, NL, EL>,
) -> Option<Isomorphism<I>> {
let q_s = subgraph.nodes.iter().choose(&mut thread_rng())?;
trace!("Starting matching with query node: {:?}", &q_s);
for g_s in graph.nodes.iter().filter(|g| g.is_isomorph_to(q_s)) {
trace!("Starting matching with graph node: {:?}", &g_s);
let ret = custom_with_initial_nodes_2(graph, subgraph, q_s, g_s, &Isomorphism::default());
if ret.is_some() {
return ret;
}
}
debug!("No partial isomorphism found");
None
}
fn combine_neighbours<I: Index, NL: Label>(
graph: &[Node<I, NL>],
query: &[Node<I, NL>],
isomorphism: &Isomorphism<I>,
) -> Isomorphism<I> {
let mut iso = Isomorphism::default();
for q in query {
for g in graph {
if q.is_isomorph_to(g)
&& !isomorphism.contains_nodeid_on_lhs(&q.id)
&& !isomorphism.contains_nodeid_on_rhs(&g.id)
{
iso.0.insert(q.id.clone(), g.id.clone());
}
}
}
iso
}
#[test]
fn combine_neighbours_simple() {
let q = vec![Node {
id: 1u32,
label: "a",
}];
let g = vec![
Node {
id: 1u32,
label: "a",
},
Node { id: 3, label: "a" },
];
let possible_matches = combine_neighbours(&g, &q, &Isomorphism::default());
let reference: Isomorphism<u32> = (&[(1, 1), (1, 3)]).into();
assert_eq!(reference, possible_matches);
}
#[test]
fn combine_neighbours_with_filter() {
let g = vec![
Node {
id: 1u32,
label: "a",
},
Node { id: 3, label: "a" },
];
let q = vec![Node {
id: 1u32,
label: "a",
}];
let possible_isomorphisms: Isomorphism<u32> = (&[(2, 0)]).into();
let possible_matches = combine_neighbours(&g, &q, &possible_isomorphisms);
let reference: Isomorphism<u32> = (&[(1, 1), (1, 3)]).into();
assert_eq!(reference, possible_matches);
let possible_matches = combine_neighbours(&q, &g, &possible_isomorphisms);
let reference: Isomorphism<u32> = (&[(1, 1), (3, 1)]).into();
assert_eq!(reference, possible_matches);
}
#[test]
fn combine_neighbours_with_filter_2() {
let g: Vec<Node<u32, _>> = vec![
Node { id: 0, label: "a" },
Node { id: 2, label: "a" },
Node { id: 3, label: "a" },
];
let q: Vec<Node<u32, _>> = vec![Node { id: 0, label: "a" }, Node { id: 2, label: "a" }];
let possible_isomorphisms: Isomorphism<u32> = (&[(1, 1)]).into();
let possible_matches = combine_neighbours(&g, &q, &possible_isomorphisms);
let reference: Isomorphism<u32> = (&[(0, 0), (0, 2), (0, 3), (2, 0), (2, 2), (2, 3)]).into();
assert_eq!(reference, possible_matches);
}
fn custom_explore_all_options_2<I: Index, NL: Label, EL: Label>(
graph: &Graph<I, NL, EL>,
subgraph: &Graph<I, NL, EL>,
isomorphism: &Isomorphism<I>,
) -> Option<Isomorphism<I>> {
let mut keys = isomorphism.0.keys().collect::<Vec<_>>();
keys.shuffle(&mut thread_rng());
let mut number_of_hopless_nodes = 0;
for q in &keys {
let q = *q;
let g = isomorphism.0.get(q).unwrap();
let g_potentials = graph.neighbours(g);
let q_potentials = subgraph.neighbours(q);
trace!("");
trace!(" Used mapping {:?}", (&q, &g));
trace!(" g neigbours {:?}", &g_potentials);
trace!(" q neigbours {:?}", &q_potentials);
trace!("limiting mappings {:?}", &isomorphism);
let possible_matches = combine_neighbours(&g_potentials, &q_potentials, isomorphism);
trace!(" possible_matches {:?}", &possible_matches);
for (q_s, g_s) in &possible_matches.0 {
let q_s = subgraph.get_node_by_id(q_s)?;
let g_s = graph.get_node_by_id(g_s)?;
let ret = custom_with_initial_nodes_2(graph, subgraph, q_s, g_s, isomorphism);
if ret.is_some() {
return ret;
}
}
if possible_matches.0.is_empty() {
number_of_hopless_nodes += 1;
}
}
if number_of_hopless_nodes != isomorphism.0.len() {
return None;
}
let nodes_to_remove = isomorphism.0.keys().cloned().collect::<Vec<_>>();
let reduced_query: Graph<I, NL, EL> = subgraph - &nodes_to_remove[..];
if reduced_query.nodes.is_empty() {
trace!("This doesn't lead to anything ... we should go back.");
return None;
}
trace!("Match found for connected subgraph, but the following graph'island' is still unmapped:\n{:?}", &reduced_query);
let q_s = reduced_query.nodes.iter().choose(&mut thread_rng())?;
let mut isomorphism = isomorphism.clone();
for g_s in graph.nodes.iter().filter(|g| g.is_isomorph_to(q_s)) {
let iso = Isomorphism::default();
let ret = custom_with_initial_nodes_2(graph, &reduced_query, q_s, g_s, &iso)?;
if isomorphism.can_be_safely_merged(&ret) {
isomorphism.0.extend(ret.0);
return Some(isomorphism.clone());
}
}
trace!("Disconnected islands don't match. Back we go ...");
None
}
fn custom_with_initial_nodes_2<I: Index, NL: Label, EL: Label>(
graph: &Graph<I, NL, EL>,
subgraph: &Graph<I, NL, EL>,
q_s: &Node<I, NL>,
g_s: &Node<I, NL>,
isomorphism: &Isomorphism<I>,
) -> Option<Isomorphism<I>> {
let mut isomorphism = isomorphism.clone();
isomorphism.0.insert(q_s.id.clone(), g_s.id.clone());
trace!("The current isomorphism reads : {:?}", &isomorphism);
if isomorphism.0.len() == subgraph.nodes.len() {
debug!("(Sub-)Match found!");
return Some(isomorphism);
}
custom_explore_all_options_2(graph, subgraph, &isomorphism)
}
#[must_use]
pub fn are_graphs_isomorph<I: Index, NL: Label, EL: Label>(
lhs: &Graph<I, NL, EL>,
rhs: &Graph<I, NL, EL>,
) -> bool {
crate::match_subgraph(lhs, rhs).is_some() && crate::match_subgraph(rhs, lhs).is_some()
}
#[cfg(test)]
mod tests {
use super::*;
use crate::Edge;
#[test]
fn simple_unique_match() {
let _ = pretty_env_logger::try_init_timed();
let graph = Graph {
nodes: vec![Node::new(0u32, "a"), Node::new(1, "b")],
edges: vec![Edge::new_unlabeled(0, 1)],
};
let query = graph.clone();
let possible_isomorphisms: Vec<Isomorphism<u32>> = vec![(&[(0, 0), (1, 1)]).into()];
let custom_iso =
match_subgraph(&graph, &query).expect("There is at least one possible isomorphism");
assert!(possible_isomorphisms.contains(&custom_iso));
}
#[test]
fn trivial_disconnected_graphs() {
let _ = pretty_env_logger::try_init_timed();
let graph = Graph::<_, _, &str> {
nodes: vec![Node::new(0u32, "a"), Node::new(1, "b")],
edges: vec![],
};
let query = Graph::<_, _, &str> {
nodes: vec![Node::new(10u32, "a"), Node::new(11, "b")],
edges: vec![],
};
let possible_isomorphisms: Vec<Isomorphism<u32>> = vec![(&[(10, 0), (11, 1)]).into()];
let custom_iso =
match_subgraph(&graph, &query).expect("There is at least one possible isomorphism");
assert!(possible_isomorphisms.contains(&custom_iso));
}
#[test]
fn simple_nonunique_match() {
let _ = pretty_env_logger::try_init_timed();
let graph = Graph {
nodes: vec![Node::new(0u32, "a"), Node::new(1, "a"), Node::new(2, "b")],
edges: vec![Edge::new_unlabeled(0, 2), Edge::new_unlabeled(1, 2)],
};
let query = Graph {
nodes: vec![Node::new(0u32, "a"), Node::new(1, "b")],
edges: vec![Edge::new_unlabeled(0, 1)],
};
let possible_isomorphisms: Vec<Isomorphism<u32>> =
vec![(&[(0, 0), (1, 2)]).into(), (&[(0, 1), (1, 2)]).into()];
let custom_iso =
match_subgraph(&graph, &query).expect("There is at least one possible isomorphism");
assert!(possible_isomorphisms.contains(&custom_iso));
}
#[test]
fn nonunique_match_with_cycles() {
let graph = Graph {
nodes: vec![
Node::new(0u32, "a"),
Node::new(1, "a"),
Node::new(2, "a"),
Node::new(3, "a"),
],
edges: vec![
Edge::new_unlabeled(0, 1),
Edge::new_unlabeled(1, 2),
Edge::new_unlabeled(1, 3),
Edge::new_unlabeled(3, 0),
],
};
let query = Graph {
nodes: vec![Node::new(0u32, "a"), Node::new(1, "a"), Node::new(2, "a")],
edges: vec![Edge::new_unlabeled(0, 1), Edge::new_unlabeled(1, 2)],
};
let possible_isomorphisms: Vec<Isomorphism<u32>> = vec![
(&[(0, 0), (1, 1), (2, 2)]).into(),
(&[(0, 2), (1, 1), (2, 0)]).into(),
(&[(0, 0), (1, 1), (2, 3)]).into(),
(&[(0, 1), (1, 3), (2, 0)]).into(),
(&[(0, 3), (1, 0), (2, 1)]).into(),
(&[(0, 3), (1, 1), (2, 0)]).into(),
(&[(0, 0), (1, 3), (2, 1)]).into(),
(&[(0, 1), (1, 0), (2, 3)]).into(),
];
for _ in 0..60 {
let custom_iso =
match_subgraph(&graph, &query).expect("There is at least one possible isomorphism");
log::info!("Found isormorphism : {:#?}", custom_iso);
assert!(possible_isomorphisms.contains(&custom_iso));
}
}
}