path: root/forest/src/iter/query/mod.rs

//! 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()),
    //         }
    //     }
}