aboutsummaryrefslogtreecommitdiff
path: root/forest/src/iter/query/mod.rs
diff options
context:
space:
mode:
Diffstat (limited to 'forest/src/iter/query/mod.rs')
-rw-r--r--forest/src/iter/query/mod.rs643
1 files changed, 643 insertions, 0 deletions
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(&current_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()),
+ // }
+ // }
+}
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2026-10-21 11:51:08 +0000