diff options
Diffstat (limited to 'forest/src/iter/query/mod.rs')
| -rw-r--r-- | forest/src/iter/query/mod.rs | 643 |
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(¤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()), + // } + // } +} |