From fba9a90cfc6aca2a26cce72f55fb261789139781 Mon Sep 17 00:00:00 2001 From: JSDurand Date: Fri, 16 Oct 2026 14:01:01 +0800 Subject: new start Now I tested and discussed with claude, and had a working version of this project. The rest is to port the claude version to my own writings. So this serves as the starting point before that attempt. In the new attempt the design is better, and a number of bugs were found and supposedly fixed, so let us see how this goes at the end. --- forest/src/iter/query/matching.rs | 338 ++++++++++++++++++++ forest/src/iter/query/mod.rs | 643 ++++++++++++++++++++++++++++++++++++++ 2 files changed, 981 insertions(+) create mode 100644 forest/src/iter/query/matching.rs create mode 100644 forest/src/iter/query/mod.rs (limited to 'forest/src/iter/query') 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 { + parent: usize, + // edge_index: usize, + parent_label: T, + edge_label: EdgeType, +} + +impl EVLabelParent { + /// 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: VLabelGraph + ELabelGraph { + /// An iterator delegation for parents and vertex and edge labels. + type ParentIter<'a>: Iterator> + 'a + where + Self: 'a, + T: 'a; + + /// Return an iterator that goes through the parents and edge + /// labels. + fn parents(&self, node: usize) -> Result, GError>; +} + +/// A trait for target graphs. +pub trait Target: VLabelGraph { + /// 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::>().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 { + graph: SLGBuilder, + parents_graph: SLGBuilder, +} + +impl Default for SimplePattern { + fn default() -> Self { + let graph = SLGBuilder::default(); + let parents_graph = SLGBuilder::default(); + Self { + graph, + parents_graph, + } + } +} + +impl SimplePattern { + /// Return a new pattern from an underlying graph builder. + pub fn new(graph: SLGBuilder) -> Result { + let nodes_len = graph.nodes_len(); + + let mut parents_graph: SLGBuilder = 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 VLabelGraph for SimplePattern { + type TupleIter<'a> = as VLabelGraph>::TupleIter<'a> + where + Self: 'a, + T: 'a; + + fn verlabren_of(&self, node_id: usize) -> Result, GError> { + self.graph.verlabren_of(node_id) + } +} + +impl LabelGraph for SimplePattern { + type Iter<'a> = std::iter::Empty + where + Self: 'a; + + type TupleIter<'a> = as LabelGraph>::TupleIter<'a> + where + Self: 'a, + T: 'a; + + type LabelIter<'a> = std::iter::Empty<(&'a EdgeType, std::iter::Empty)> + where + Self: 'a, + T: 'a; + + type EdgeLabelIter<'a> = std::option::IntoIter + where + Self: 'a, + T: 'a; + + fn edge_label(&self, source: usize, target: usize) -> Result, GError> { + LabelGraph::edge_label(&self.graph, source, target) + } + + fn find_children_with_label( + &self, + node_id: usize, + label: &EdgeType, + ) -> Result<>::Iter<'_>, GError> { + self.graph.find_children_with_label(node_id, label) + } + + fn labels_of(&self, _node_id: usize) -> Result, GError> { + unimplemented!("Unsupported operation!") + } + + fn tuples_of(&self, node_id: usize) -> Result, GError> { + self.graph.tuples_of(node_id) + } + + fn has_edge_label( + &self, + node_id: usize, + label: &EdgeType, + target: usize, + ) -> Result { + 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: as VLabelGraph>::TupleIter<'a>, + edge_iter: as ELabelGraph>::TupleIter<'a>, +} + +impl<'a, T> PatternParents<'a, T> +where + T: GraphLabel + 'a, +{ + /// Construct a new iterator. + pub fn new( + vertex_iter: as VLabelGraph>::TupleIter<'a>, + edge_iter: as ELabelGraph>::TupleIter<'a>, + ) -> Self { + Self { + vertex_iter, + edge_iter, + } + } +} + +impl<'a, T: 'a + GraphLabel> Iterator for PatternParents<'a, T> { + type Item = EVLabelParent; + + fn next(&mut self) -> Option { + 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) { + 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 Pattern for SimplePattern { + type ParentIter<'a> = PatternParents<'a, T> where T:'a; + + fn parents(&self, node: usize) -> Result, 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 Target for SimplePattern { + fn filter_label(&self, label: T) -> Box<[usize]> { + (0..self.nodes_len()) + .filter(|node| VLabelGraph::vertex_label(self, *node) == Ok(Some(label))) + .collect::>() + .into_boxed_slice() + } +} + +impl Target for PLGraph { + fn filter_label(&self, label: T) -> Box<[usize]> { + (0..self.nodes_len()) + .filter(|node| VLabelGraph::vertex_label(self, *node) == Ok(Some(label))) + .collect::>() + .into_boxed_slice() + } +} + +impl Target> for BytesForest { + fn filter_label(&self, label: ForestLabel) -> Box<[usize]> { + (0..self.nodes_len()) + .filter(|node| VLabelGraph::vertex_label(self, *node) == Ok(Some(label))) + .collect::>() + .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(&self, g: &G, from: usize, to: usize) -> Result { + 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( + graph: &G, + from: usize, + to: usize, + simulationp: bool, +) -> Result { + 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::>() + .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, usize> { + let mut cands: Vec = 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( + pattern: &P, + target: &T, + pattern_index: usize, + domain: &[bool], + mapping: &[Option], +) -> Result, GError> +where + L: GraphLabel, + P: Pattern, + T: Target, +{ + let mut cands: Vec = 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> { + let len = domains.len(); + + let mut result: Vec = Vec::with_capacity(len); + + let mut hall_set: Set = Set::with_capacity(len); + + let mut accumulated_set: Set = Set::with_capacity(len); + + let mut current_len = 0usize; + + let mut sorted_indices_by_len = (0..len).collect::>(); + + 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(pattern: P, target: T) -> Result>, GError> +where + L: GraphLabel, + P: Pattern, + T: Target, +{ + 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::>() + .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]> = std::iter::repeat(None) + .take(pattern_nodes_len) + .collect::>() + .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::>() + .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 = Vec::with_capacity(pattern_nodes_len); + let mut target_used_p = std::iter::repeat(false) + .take(target_nodes_len) + .collect::>() + .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( + // builder: &mut B, + // from: usize, + // to: usize, + // label: ::Label, + // ) -> Result<(), Box> + // where + // B: Builder, + // ::Label: Clone + Copy, + // { + // builder.add_edge(from, to, label)?; + // builder.add_edge(to, from, label)?; + // Ok(()) + // } + + #[allow(unused)] + fn build_line(len: usize) -> Result, Box> { + let mut builder = SLGBuilder::::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, Box> { + let mut builder = SLGBuilder::::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, Box> { + let mut builder = SLGBuilder::::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, Box> { + let mut builder = SLGBuilder::::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> { + 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> { + 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> { + // 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()), + // } + // } +} -- cgit v1.2.3-18-g5258