diff options
Diffstat (limited to 'forest/src/iter/query')
| -rw-r--r-- | forest/src/iter/query/matching.rs | 338 | ||||
| -rw-r--r-- | forest/src/iter/query/mod.rs | 643 |
2 files changed, 981 insertions, 0 deletions
diff --git a/forest/src/iter/query/matching.rs b/forest/src/iter/query/matching.rs new file mode 100644 index 0000000..7ff47bb --- /dev/null +++ b/forest/src/iter/query/matching.rs @@ -0,0 +1,338 @@ +//! This file defines some traits and basic implementations for +//! matching pattern vertices against target vertices. + +use crate::{bytes::BytesForest, ForestLabel}; + +#[allow(unused_imports)] +use graph::{ + error::Error as GError, ELabelGraph, Graph, GraphLabel, LabelGraph, PLGraph, SLGBuilder, + SLGraph, VLabelGraph, +}; + +use graph_macro::Graph; + +use grammar::GrammarLabel; + +/// An aggregate struct that holds information about a parent as well +/// as its vertex label and the corresponding edge label. +#[derive(Debug, Clone, Copy)] +pub struct EVLabelParent<T: GraphLabel> { + parent: usize, + // edge_index: usize, + parent_label: T, + edge_label: EdgeType, +} + +impl<T: GraphLabel> EVLabelParent<T> { + /// Construct a new instance. + pub fn new(parent: usize, parent_label: T, edge_label: EdgeType) -> Self { + Self { + parent, + parent_label, + edge_label, + } + } + + /// Retrieve the `parent` field. + pub fn parent(&self) -> usize { + self.parent + } + + // /// Retrieve the `edge_index` field. + // pub fn edge_index(&self) -> usize { + // self.edge_index + // } + + /// Retrieve the `parent_label` field. + pub fn parent_label(&self) -> T { + self.parent_label + } + + /// Retrieve the `edge_label` field. + pub fn edge_label(&self) -> EdgeType { + self.edge_label + } +} + +/// A trait for pattern graphs. +pub trait Pattern<T: GraphLabel>: VLabelGraph<T> + ELabelGraph<EdgeType> { + /// An iterator delegation for parents and vertex and edge labels. + type ParentIter<'a>: Iterator<Item = EVLabelParent<T>> + 'a + where + Self: 'a, + T: 'a; + + /// Return an iterator that goes through the parents and edge + /// labels. + fn parents(&self, node: usize) -> Result<Self::ParentIter<'_>, GError>; +} + +/// A trait for target graphs. +pub trait Target<T: GraphLabel>: VLabelGraph<T> { + /// Return an array of node indices whose labels match the given + /// label. + fn filter_label(&self, label: T) -> Box<[usize]> { + let _label = label; + + (0..self.nodes_len()).collect::<Vec<_>>().into_boxed_slice() + } +} + +/// A custom pattern type with a fixed edge label and a generic vertex +/// label. +/// +/// This type contains two graphs, with the extra one containing +/// parentship information. +#[derive(Debug, Clone, Graph)] +pub struct SimplePattern<T: GraphLabel> { + graph: SLGBuilder<T, EdgeType>, + parents_graph: SLGBuilder<T, EdgeType>, +} + +impl<T: GraphLabel> Default for SimplePattern<T> { + fn default() -> Self { + let graph = SLGBuilder::default(); + let parents_graph = SLGBuilder::default(); + Self { + graph, + parents_graph, + } + } +} + +impl<T: GraphLabel> SimplePattern<T> { + /// Return a new pattern from an underlying graph builder. + pub fn new(graph: SLGBuilder<T, EdgeType>) -> Result<Self, GError> { + let nodes_len = graph.nodes_len(); + + let mut parents_graph: SLGBuilder<T, EdgeType> = SLGBuilder::with_capacity(nodes_len); + + for node in 0..nodes_len { + // Nodes must have labels. + let label = VLabelGraph::vertex_label(&graph, node)?.unwrap(); + + parents_graph.add_vertex(label); + } + + for node in 0..nodes_len { + for (label, child) in ELabelGraph::edlabren_of(&graph, node)? { + parents_graph.add_edge(node, child, label)?; + } + } + + Ok(Self { + graph, + parents_graph, + }) + } +} + +impl<T: GraphLabel> VLabelGraph<T> for SimplePattern<T> { + type TupleIter<'a> = <SLGBuilder::<T, EdgeType> as VLabelGraph<T>>::TupleIter<'a> + where + Self: 'a, + T: 'a; + + fn verlabren_of(&self, node_id: usize) -> Result<Self::TupleIter<'_>, GError> { + self.graph.verlabren_of(node_id) + } +} + +impl<T: GraphLabel> LabelGraph<EdgeType> for SimplePattern<T> { + type Iter<'a> = std::iter::Empty<usize> + where + Self: 'a; + + type TupleIter<'a> = <SLGBuilder::<T, EdgeType> as LabelGraph<EdgeType>>::TupleIter<'a> + where + Self: 'a, + T: 'a; + + type LabelIter<'a> = std::iter::Empty<(&'a EdgeType, std::iter::Empty<usize>)> + where + Self: 'a, + T: 'a; + + type EdgeLabelIter<'a> = std::option::IntoIter<EdgeType> + where + Self: 'a, + T: 'a; + + fn edge_label(&self, source: usize, target: usize) -> Result<Self::EdgeLabelIter<'_>, GError> { + LabelGraph::edge_label(&self.graph, source, target) + } + + fn find_children_with_label( + &self, + node_id: usize, + label: &EdgeType, + ) -> Result<<Self as LabelGraph<EdgeType>>::Iter<'_>, GError> { + self.graph.find_children_with_label(node_id, label) + } + + fn labels_of(&self, _node_id: usize) -> Result<Self::LabelIter<'_>, GError> { + unimplemented!("Unsupported operation!") + } + + fn tuples_of(&self, node_id: usize) -> Result<Self::TupleIter<'_>, GError> { + self.graph.tuples_of(node_id) + } + + fn has_edge_label( + &self, + node_id: usize, + label: &EdgeType, + target: usize, + ) -> Result<bool, GError> { + self.graph.has_edge_label(node_id, label, target) + } +} + +/// Iterator delegator for parents. +#[derive(Debug, Clone)] +pub struct PatternParents<'a, T> +where + T: GraphLabel + 'a, +{ + vertex_iter: <SLGBuilder<T, EdgeType> as VLabelGraph<T>>::TupleIter<'a>, + edge_iter: <SLGBuilder<T, EdgeType> as ELabelGraph<EdgeType>>::TupleIter<'a>, +} + +impl<'a, T> PatternParents<'a, T> +where + T: GraphLabel + 'a, +{ + /// Construct a new iterator. + pub fn new( + vertex_iter: <SLGBuilder<T, EdgeType> as VLabelGraph<T>>::TupleIter<'a>, + edge_iter: <SLGBuilder<T, EdgeType> as ELabelGraph<EdgeType>>::TupleIter<'a>, + ) -> Self { + Self { + vertex_iter, + edge_iter, + } + } +} + +impl<'a, T: 'a + GraphLabel> Iterator for PatternParents<'a, T> { + type Item = EVLabelParent<T>; + + fn next(&mut self) -> Option<Self::Item> { + self.vertex_iter.next().and_then(|(vlabel, target)| { + self.edge_iter + .next() + .map(|(elabel, _)| EVLabelParent::new(target, vlabel, elabel)) + }) + } + + #[inline] + fn size_hint(&self) -> (usize, Option<usize>) { + self.vertex_iter.size_hint() + } +} + +impl<'a, T: 'a + GraphLabel> ExactSizeIterator for PatternParents<'a, T> { + #[inline] + fn len(&self) -> usize { + self.vertex_iter.len() + } +} + +impl<T: GraphLabel> Pattern<T> for SimplePattern<T> { + type ParentIter<'a> = PatternParents<'a, T> where T:'a; + + fn parents(&self, node: usize) -> Result<Self::ParentIter<'_>, GError> { + let vertex_iter = self.parents_graph.verlabren_of(node)?; + let edge_iter = self.parents_graph.edlabren_of(node)?; + + Ok(PatternParents::new(vertex_iter, edge_iter)) + } +} + +// Implement Target for three types. Another type "DefaultForest" +// should implement this trait on its own when the need arises. +// +// Note that SimplePattern also implements the Target trait. + +impl<T: GraphLabel> Target<T> for SimplePattern<T> { + fn filter_label(&self, label: T) -> Box<[usize]> { + (0..self.nodes_len()) + .filter(|node| VLabelGraph::vertex_label(self, *node) == Ok(Some(label))) + .collect::<Vec<_>>() + .into_boxed_slice() + } +} + +impl<T: GraphLabel> Target<T> for PLGraph<T> { + fn filter_label(&self, label: T) -> Box<[usize]> { + (0..self.nodes_len()) + .filter(|node| VLabelGraph::vertex_label(self, *node) == Ok(Some(label))) + .collect::<Vec<_>>() + .into_boxed_slice() + } +} + +impl Target<ForestLabel<GrammarLabel>> for BytesForest { + fn filter_label(&self, label: ForestLabel<GrammarLabel>) -> Box<[usize]> { + (0..self.nodes_len()) + .filter(|node| VLabelGraph::vertex_label(self, *node) == Ok(Some(label))) + .collect::<Vec<_>>() + .into_boxed_slice() + } +} + +// Edge-filtering types + +/// The type of edges that this edge can match against. +/// +/// For the time being, we can only match either a direct child +/// (i.e. no extra condition) or a sibling of another node. +/// +/// In the future, we shall be able to use supplemental graphs to +/// match edges. +/// +/// This can be used as [`Graphlabel`][graph::GraphLabel]. +#[derive(Copy, Clone, Debug, Default, Eq, PartialEq, Hash, Ord, PartialOrd)] +pub enum EdgeType { + /// Matches a direct child. + #[default] + Direct, + /// Match a sibling of another node. + Sibling(usize), +} + +impl std::fmt::Display for EdgeType { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + match self { + EdgeType::Direct => write!(f, "direct edge"), + EdgeType::Sibling(node) => write!(f, "sibling of {node}"), + } + } +} + +impl EdgeType { + /// Return a Sibling-type edge. + pub fn sibling(node: usize) -> Self { + Self::Sibling(node) + } + + /// Return whether this edge matches. + pub fn matches<G: Graph>(&self, g: &G, from: usize, to: usize) -> Result<bool, GError> { + match self { + EdgeType::Direct => g.has_edge(from, to), + EdgeType::Sibling(sibling) => { + let mut iter = g.children_of(from)?; + + while let Some(child) = iter.next() { + if child == *sibling { + return Ok(iter.next() == Some(to)); + } + } + + // sibling not found + + Ok(false) + } + } + } +} diff --git a/forest/src/iter/query/mod.rs b/forest/src/iter/query/mod.rs new file mode 100644 index 0000000..8820704 --- /dev/null +++ b/forest/src/iter/query/mod.rs @@ -0,0 +1,643 @@ +//! This module implements an iterator of forests, which provides +//! querying capabilities. + +// use super::*; + +#[allow(unused_imports)] +use graph::{error::Error as GError, labelled::SLGraph, Graph, GraphLabel, VLabelGraph}; + +use std::collections::HashSet as Set; + +pub mod matching; + +use matching::{Pattern, Target}; + +// REVIEW: Find better approaches for our specific graphs, which are +// almost like trees. + +/// Most of my graphs are directed graphs, so a function is used to +/// simulate undirected graphs, in case needed. +#[allow(dead_code)] +fn has_edge_undirected<G: Graph>( + graph: &G, + from: usize, + to: usize, + simulationp: bool, +) -> Result<bool, GError> { + if !simulationp { + graph.has_edge(from, to) + } else { + Ok(graph.has_edge(from, to)? || graph.has_edge(to, from)?) + } +} + +/// Initialize a vector of true bits, of the given length. +fn initialize_bits(length: usize) -> Box<[bool]> { + std::iter::repeat(true) + .take(length) + .collect::<Vec<bool>>() + .into_boxed_slice() +} + +/// Return an index whose corresponding slice has the smallest length +/// that is not zero nor one. +/// +/// If some slice is empty return error. +/// +/// If every slice has length one, return `Ok(None)`. +fn choose_pattern(domains: &[Box<[bool]>], candidates: &[bool]) -> Result<Option<usize>, usize> { + let mut cands: Vec<usize> = Vec::with_capacity(domains.len()); + + let mut current_min = usize::MAX; + + for ((index, _), domain_size) in candidates + .iter() + .enumerate() + .filter(|(_, considerp)| **considerp) + .zip( + domains + .iter() + .map(|domain| domain.iter().filter(|element| **element).count()), + ) + { + match domain_size { + 0 => return Err(index), + _ => { + // dbg!(index, domain_size, current_min); + match domain_size.cmp(¤t_min) { + std::cmp::Ordering::Less => { + current_min = domain_size; + + cands.clear(); + cands.push(index); + } + std::cmp::Ordering::Equal => { + cands.push(index); + } + std::cmp::Ordering::Greater => (), + }; + } + } + } + + // TODO: Add random-ness later + Ok(cands.first().copied()) + + // if let Some(cand) = cands.first() { + // + + // Ok(Some(*cand)) + // } else { + // Ok(None) + // } +} + +/// Find a target vertex within the chosen domain. +/// +/// PATTERN_INDEX is used to obtain the degree of the pattern vertex, +/// so as to filter inappropriate target vertices. +/// +/// MAPPING is used to know whether some neighbour of the pattern +/// vertex has already been mapped, which information can be used to +/// filter the target vertices. +/// +/// Return the first found suitable target vertex with the highest +/// degree. +/// +/// If no suitable target vertex is found, return Ok(None). +fn choose_target<L, P, T>( + pattern: &P, + target: &T, + pattern_index: usize, + domain: &[bool], + mapping: &[Option<usize>], +) -> Result<Option<usize>, GError> +where + L: GraphLabel, + P: Pattern<L>, + T: Target<L>, +{ + let mut cands: Vec<usize> = Vec::with_capacity(target.nodes_len()); + + let mut current_max_degree = 0usize; + + 'target_loop: for target_index in domain + .iter() + .enumerate() + .filter(|(_, v)| **v) + .map(|(index, _)| index) + { + // TODO: Advanced and custom filtering should be added here. + // + // These are edge-related filtering, so perhaps we can use + // edge labels. + // + // Some filtering types to add: + // + // 1. Path with a length restriction: (>= or = or <=) a + // threshold. + // + // The default condition is to restrict to length-one + // paths. + // + // We can preprocess the target graph to associate a fixed + // set of "near" vertices to any vertex, so that we can + // filter within a constant amount of time. + // + // Or we can first restrict this type so that we can only + // use small lengths. + // + // 2. Being a sibling with another edge. + + for (label, elabel, pattern_neighbour) in pattern + .verlabren_of(pattern_index)? + .zip(pattern.edlabren_of(pattern_index)?) + .map(|((label, index), (elabel, _))| (label, elabel, index)) + { + match elabel { + matching::EdgeType::Direct => { + if let Some(Some(mapped)) = mapping.get(pattern_neighbour) { + if !target.has_edge(target_index, *mapped)? { + continue 'target_loop; + } + + let mapped_label = VLabelGraph::vertex_label(target, *mapped)?.unwrap(); + + if mapped_label != label { + continue 'target_loop; + } + } + } + matching::EdgeType::Sibling(_) => todo!(), + } + } + + for parent in pattern.parents(pattern_index)? { + let label = parent.parent_label(); + let elabel = parent.edge_label(); + let parent = parent.parent(); + + match elabel { + matching::EdgeType::Direct => { + if let Some(Some(mapped)) = mapping.get(parent) { + if !target.has_edge(*mapped, target_index)? { + continue 'target_loop; + } + + let mapped_label = VLabelGraph::vertex_label(target, *mapped)?.unwrap(); + + if mapped_label != label { + continue 'target_loop; + } + } + } + _ => todo!(), + } + } + + // a currently valid target is found + + let target_degree = target.degree(target_index)?; + + if target_degree > current_max_degree { + current_max_degree = target_degree; + + cands.clear(); + cands.push(target_index); + } else if target_index == current_max_degree { + cands.push(target_index); + } + } + + // TODO: Add random-ness later. + Ok(cands.first().copied()) + // if let Some(cand) = cands.first() { + // Ok(Some(*cand)) + // } else { + // Ok(None) + // } +} + +/// Detect if the domains contain a hidden hall set. +/// +/// This is an "intermediate level detection", so maybe some hall sets +/// are not found. +fn find_hall_sets(domains: &mut [Box<[bool]>]) -> Option<Box<[usize]>> { + let len = domains.len(); + + let mut result: Vec<usize> = Vec::with_capacity(len); + + let mut hall_set: Set<usize> = Set::with_capacity(len); + + let mut accumulated_set: Set<usize> = Set::with_capacity(len); + + let mut current_len = 0usize; + + let mut sorted_indices_by_len = (0..len).collect::<Vec<_>>(); + + sorted_indices_by_len.sort_by_cached_key(|element| { + domains + .get(*element) + .unwrap() + .iter() + .filter(|element| **element) + .count() + }); + + for index in sorted_indices_by_len { + result.push(index); + + let domain = domains.get_mut(index).unwrap(); + + for hall in hall_set.iter() { + *domain.get_mut(*hall).unwrap() = false; + } + + accumulated_set.extend( + domain + .iter() + .enumerate() + .filter(|(_, v)| **v) + .map(|(id, _)| id), + ); + + current_len += 1; + + if !domain.iter().any(|element| *element) || accumulated_set.len() < current_len { + return Some(result.into_boxed_slice()); + } + + if accumulated_set.len() == current_len { + hall_set.extend(accumulated_set.iter().copied()); + accumulated_set.clear(); + current_len = 0; + } + } + + None +} + +/// Determine if a pattern graph is a subgraph of a target graph. +/// +/// If true, then return Ok(Some(array)), where array is an array of +/// indices, whose n-th element is the index of a target vertex that +/// is associated to the n-th vertex in the pattern graph. +/// +/// If false, return Ok(None). +pub fn is_subgraph<L, P, T>(pattern: P, target: T) -> Result<Option<Box<[usize]>>, GError> +where + L: GraphLabel, + P: Pattern<L>, + T: Target<L>, +{ + let pattern_nodes_len = pattern.nodes_len(); + let target_nodes_len = target.nodes_len(); + + if pattern_nodes_len > target_nodes_len { + return Ok(None); + } + + let mut candidates: Box<[bool]> = std::iter::repeat(true) + .take(pattern_nodes_len) + .collect::<Vec<_>>() + .into_boxed_slice(); + + // Exclude isolated pattern vertices. + + // for (index, cand) in candidates.iter_mut().enumerate() { + // if pattern.is_empty_node(index)? { + // *cand = false; + // } + // } + + let mut mapping: Box<[Option<usize>]> = std::iter::repeat(None) + .take(pattern_nodes_len) + .collect::<Vec<_>>() + .into_boxed_slice(); + + /// A backtrack-vector: from, to, domains-vector, unvisited vertices + type Association = Vec<(usize, usize, Box<[Box<[bool]>]>, Box<[bool]>)>; + + let mut association_vec: Association = Vec::with_capacity(pattern_nodes_len); + + let mut pattern_domains: Box<[Box<[bool]>]> = + std::iter::repeat_with(|| initialize_bits(target_nodes_len)) + .take(pattern_nodes_len) + .collect::<Vec<_>>() + .into_boxed_slice(); + + // TODO: Perhaps consider some supplemental graphs to facilitate + // the filtering: for each supplemental graph S, if f is an + // injective mapping from P to T, then f induces an injective + // mapping from Hom(S, P) to Hom(S, T). Essentially this is using + // the paths information to filter targets. + + // TODO: Some target vertices might be excluded from every domain, + // so we can use the degree-filtering to exclude more domains. + // This recursive filtering might be useful. + + for (pattern_index, domain) in pattern_domains.iter_mut().enumerate() { + let pattern_degree = pattern.degree(pattern_index)?; + + if let Some(label) = pattern.vertex_label(pattern_index)? { + for cand in domain.iter_mut() { + *cand = false; + } + + for true_cand in target.filter_label(label).iter() { + *domain.get_mut(*true_cand).unwrap() = true; + } + } + + for (target_index, target_handle) in domain.iter_mut().enumerate().filter(|(_, b)| **b) { + let target_degree = target.degree(target_index)?; + + if pattern_degree > target_degree { + *target_handle = false; + } + } + } + + /// A macro for backtracking + macro_rules! backtrack { + () => { + match association_vec.pop() { + None => { + return Ok(None); + } + Some((from, to, prev_domains, prev_candidates)) => { + dbg!((from, to)); + *mapping.get_mut(from).unwrap() = None; + + pattern_domains = prev_domains; + + *pattern_domains.get_mut(from).unwrap().get_mut(to).unwrap() = false; + + candidates = prev_candidates; + } + } + }; + } + + // use a dummy counter for the time being + 'main_loop: for _ in 0..100 { + dbg!(&pattern_domains); + + match choose_pattern(&pattern_domains, &candidates) { + Err(index) => { + dbg!(format!("{index} proves impossibility")); + + // silence the compiler + let _index = index; + + backtrack!(); + } + Ok(None) => { + let mut final_mapping: Vec<usize> = Vec::with_capacity(pattern_nodes_len); + let mut target_used_p = std::iter::repeat(false) + .take(target_nodes_len) + .collect::<Vec<bool>>() + .into_boxed_slice(); + + for domain in pattern_domains.iter() { + // each domain should be a singleton list at this point + let domain_element = domain.iter().position(|x| *x).unwrap(); + + let used_p = target_used_p.get_mut(domain_element).unwrap(); + + if *used_p { + dbg!("repetition found"); + + backtrack!(); + + continue 'main_loop; + } + + *used_p = true; + + final_mapping.push(domain_element); + } + + return Ok(Some(final_mapping.into_boxed_slice())); + } + Ok(Some(index)) => { + dbg!(index); + + let chosen_domain = pattern_domains.get(index).unwrap(); + + let choice = choose_target(&pattern, &target, index, chosen_domain, &mapping)?; + + match choice { + None => { + backtrack!(); + } + Some(choice) => { + dbg!((index, choice)); + + // record this mapping + + *mapping.get_mut(index).unwrap() = Some(choice); + + let cloned_domains = pattern_domains.to_vec().into_boxed_slice(); + + let cloned_candidates = candidates.to_vec().into_boxed_slice(); + + association_vec.push((index, choice, cloned_domains, cloned_candidates)); + + // Do not consider this index again. + + *candidates.get_mut(index).unwrap() = false; + + // update domains + + for domain in pattern_domains.iter_mut() { + *domain.get_mut(choice).unwrap() = false; + } + + let domain = pattern_domains.get_mut(index).unwrap(); + + for domain_ref in domain.iter_mut() { + *domain_ref = false; + } + + *domain.get_mut(choice).unwrap() = true; + + // all-different propagation + + let hall_detection = find_hall_sets(&mut pattern_domains); + + if let Some(fail_set) = hall_detection { + dbg!(format!("a hall set is found: {fail_set:?}")); + + backtrack!(); + } + + // TODO: Optionally add degree filtering? + } + } + } + } + } + + dbg!("loop time out!"); + + Ok(None) +} + +// TODO: Reconstruct the tests from the new types. + +#[cfg(test)] +mod test_subgraph_solver { + use super::{ + matching::{EdgeType, SimplePattern}, + *, + }; + + #[allow(unused_imports)] + use graph::{Builder, SLGBuilder}; + + // /// Simulate undirected graphs by adding edges in both directions. + // fn add_edge<B>( + // builder: &mut B, + // from: usize, + // to: usize, + // label: <B>::Label, + // ) -> Result<(), Box<dyn std::error::Error>> + // where + // B: Builder, + // <B>::Label: Clone + Copy, + // { + // builder.add_edge(from, to, label)?; + // builder.add_edge(to, from, label)?; + // Ok(()) + // } + + #[allow(unused)] + fn build_line(len: usize) -> Result<SimplePattern<usize>, Box<dyn std::error::Error>> { + let mut builder = SLGBuilder::<usize, EdgeType>::default(); + + for i in 0..len { + builder.add_vertex(i); + } + + for i in 0..(len - 1) { + builder.add_edge(i, i + 1, EdgeType::Direct)?; + } + + Ok(SimplePattern::new(builder)?) + } + + #[allow(unused)] + fn build_star(len: usize) -> Result<SimplePattern<usize>, Box<dyn std::error::Error>> { + let mut builder = SLGBuilder::<usize, EdgeType>::default(); + + for i in 0..len { + builder.add_vertex(i); + } + + for i in 1..len { + builder.add_edge(i, 0, EdgeType::default())?; + } + + Ok(SimplePattern::new(builder)?) + } + + #[allow(unused)] + fn build_triangle_plus_one_edge() -> Result<SimplePattern<usize>, Box<dyn std::error::Error>> { + let mut builder = SLGBuilder::<usize, EdgeType>::default(); + + for i in 0..4 { + builder.add_vertex(i); + } + + for i in 1..=3 { + builder.add_edge(i, 0, Default::default())?; + } + + builder.add_edge(1, 2, EdgeType::default())?; + + Ok(SimplePattern::new(builder)?) + } + + #[allow(unused)] + fn build_two_triangles_connected() -> Result<SimplePattern<usize>, Box<dyn std::error::Error>> { + let mut builder = SLGBuilder::<usize, EdgeType>::default(); + + for i in 0..6 { + builder.add_vertex(i); + } + + for i in 0..=2 { + builder.add_edge(i, i + 1, EdgeType::default())?; + } + + builder.add_edge(0, 2, EdgeType::default())?; + + for i in 3..=4 { + builder.add_edge(i, i + 1, EdgeType::default())?; + } + + builder.add_edge(3, 5, EdgeType::default())?; + + Ok(SimplePattern::new(builder)?) + } + + #[test] + fn test_lines() -> Result<(), Box<dyn std::error::Error>> { + let pattern = build_line(4)?; + let target = build_line(5)?; + + let result = is_subgraph(pattern, target); + + println!("result = {result:?}"); + + match result { + Ok(Some(result)) => { + assert_eq!(result.to_vec(), [0, 1, 2, 3].to_vec()); + + Ok(()) + } + Ok(None) => Err("Subgraph solver thinks this is not a subgraph?!".into()), + Err(e) => Err(format!("Subgraph solver failed with error {e}").into()), + } + } + + #[test] + fn test_line_and_star() -> Result<(), Box<dyn std::error::Error>> { + let pattern = build_line(4)?; + let target = build_star(5)?; + + let result = is_subgraph(pattern, target); + + println!("result = {result:?}"); + + match result { + Ok(Some(result)) => Err(format!( + "Subgraph solver thinks this is a subgraph?!\nMapping = {result:?}" + ) + .into()), + Ok(None) => Ok(()), + Err(e) => Err(format!("Subgraph solver failed with error {e}").into()), + } + } + + // #[test] + // fn test_paper_page_317_example() -> Result<(), Box<dyn std::error::Error>> { + // let pattern = build_triangle_plus_one_edge()?; + // let target = build_two_triangles_connected()?; + + // let result = is_subgraph(pattern, target); + + // println!("result = {result:?}"); + + // match result { + // Ok(Some(result)) => { + // assert_eq!(result.to_vec(), [2, 0, 1, 3].to_vec()); + + // Ok(()) + // } + // Ok(None) => Err("Subgraph solver thinks this is not a subgraph?!".into()), + // Err(e) => Err(format!("Subgraph solver failed with error {e}").into()), + // } + // } +} |