path: root/graph/src/labelled/binary.rs

//! This file implements a labelled graph that can index vertices by
//! labels and each node knows about its parents.

use super::*;
use crate::{Parent, ParentsGraph};

use std::{
    collections::{hash_map::Iter as MapIter, HashMap as Map},
    slice::Iter,
};

use crate::builder::BuilderMut;

/// An ad-hoc `IndexSet` for children.
#[derive(Debug, Clone, Default)]
struct PLChildren {
    children: Vec<usize>,
    indices: Map<usize, usize>,
}

impl PLChildren {
    fn iter(&self) -> Iter<'_, usize> {
        self.children.iter()
    }

    fn len(&self) -> usize {
        self.children.len()
    }

    fn is_empty(&self) -> bool {
        self.children.is_empty()
    }

    fn contains(&self, key: &usize) -> bool {
        self.indices.contains_key(key)
    }

    // The return value matters not for me.
    fn insert(&mut self, key: usize) {
        if let Some(key_index) = self.indices.get(&key) {
            debug_assert!(*key_index < self.children.len());

            *self.children.get_mut(*key_index).unwrap() = key;
        } else {
            let key_index = self.children.len();
            self.indices.insert(key, key_index);
            self.children.push(key);
        }
    }

    /// Remove an element from children.
    ///
    /// We must preserve the order of elements, so we have to shift
    /// every element that follows it, which leads to a slow
    /// performance.  So try to avoid removing edges, if possible.
    fn remove(&mut self, key: usize) {
        let key_index = if let Some(key_index_result) = self.indices.get(&key) {
            *key_index_result
        } else {
            // If the key is not contained in children, we have
            // nothing to do.
            return;
        };

        let children_len = self.children.len();

        debug_assert!(key_index < children_len);

        for i in (key_index + 1)..children_len {
            let key = self.children.get(i).unwrap();
            *self.indices.get_mut(key).unwrap() -= 1;
        }

        self.children.remove(key_index);
    }
}

/// A node has some children, some parents, and a label.
#[derive(Debug, Clone)]
struct PLNode<T: GraphLabel> {
    children: PLChildren,
    parents: Map<usize, usize>,
    label: T,
}

impl<T: GraphLabel> PLNode<T> {
    fn new(children: PLChildren, parents: Map<usize, usize>, label: T) -> Self {
        Self {
            children,
            parents,
            label,
        }
    }
}

impl<T: GraphLabel + Default> Default for PLNode<T> {
    #[inline]
    fn default() -> Self {
        let children = Default::default();
        let parents = Default::default();
        let label = Default::default();
        Self {
            children,
            label,
            parents,
        }
    }
}

/// A Parents-knowing, vertex-Labelled Graph.
#[derive(Debug, Clone)]
pub struct PLGraph<T: GraphLabel> {
    nodes: Vec<PLNode<T>>,
    label_index_map: Map<T, usize>,
}

impl<T: GraphLabel> Default for PLGraph<T> {
    #[inline]
    fn default() -> Self {
        let nodes = Default::default();
        let label_index_map = Default::default();
        Self {
            nodes,
            label_index_map,
        }
    }
}

impl<T: GraphLabel> Graph for PLGraph<T> {
    type Iter<'a> = std::iter::Copied<Iter<'a, usize>>
    where
        Self: 'a;

    #[inline]
    fn is_empty(&self) -> bool {
        self.nodes.is_empty()
    }

    #[inline]
    fn nodes_len(&self) -> usize {
        self.nodes.len()
    }

    #[inline]
    fn children_of(&self, node_id: usize) -> Result<Self::Iter<'_>, Error> {
        if let Some(node) = self.nodes.get(node_id) {
            Ok(node.children.iter().copied())
        } else {
            Err(Error::IndexOutOfBounds(node_id, self.nodes.len()))
        }
    }

    #[inline]
    fn degree(&self, node_id: usize) -> Result<usize, Error> {
        if let Some(node) = self.nodes.get(node_id) {
            Ok(node.children.len())
        } else {
            Err(Error::IndexOutOfBounds(node_id, self.nodes.len()))
        }
    }

    #[inline]
    fn is_empty_node(&self, node_id: usize) -> Result<bool, Error> {
        if let Some(node) = self.nodes.get(node_id) {
            Ok(node.children.is_empty())
        } else {
            Err(Error::IndexOutOfBounds(node_id, self.nodes.len()))
        }
    }

    #[inline]
    fn has_edge(&self, source: usize, target: usize) -> Result<bool, Error> {
        if let Some(node) = self.nodes.get(source) {
            if !self.has_node(target) {
                return Err(Error::IndexOutOfBounds(target, self.nodes.len()));
            }

            Ok(node.children.contains(&target))
        } else {
            Err(Error::IndexOutOfBounds(source, self.nodes.len()))
        }
    }

    fn replace_by_builder(&mut self, _builder: impl Builder<Result = Self>) {
        todo!()
    }

    fn print_viz(&self, _filename: &str) -> Result<(), std::io::Error> {
        todo!()
    }
}

/// An iterator of parents.
///
/// This is to avoid a boxed allocation.
#[derive(Debug, Clone)]
pub struct ParentIter<'a> {
    /// MapIter yields (&usize, &usize), so we need to dereference
    /// that.
    parents: MapIter<'a, usize, usize>,
}

impl<'a> ParentIter<'a> {
    fn new(parents: MapIter<'a, usize, usize>) -> Self {
        Self { parents }
    }
}

impl<'a> Iterator for ParentIter<'a> {
    type Item = Parent;

    #[inline]
    fn next(&mut self) -> Option<Self::Item> {
        self.parents
            .next()
            .map(|(key, value)| Parent::new(*key, *value))
    }

    #[inline]
    fn size_hint(&self) -> (usize, Option<usize>) {
        self.parents.size_hint()
    }
}

impl<'a> ExactSizeIterator for ParentIter<'a> {
    #[inline]
    fn len(&self) -> usize {
        self.parents.len()
    }
}

impl<T: GraphLabel> ParentsGraph for PLGraph<T> {
    type Iter<'a> = ParentIter<'a>
        where Self: 'a;

    #[inline]
    fn parents_of(&self, node_id: usize) -> Result<<Self as ParentsGraph>::Iter<'_>, Error> {
        if let Some(node) = self.nodes.get(node_id) {
            Ok(ParentIter::new(node.parents.iter()))
        } else {
            Err(Error::IndexOutOfBounds(node_id, self.nodes.len()))
        }
    }
}

impl<T: GraphLabel> LabelGraph<T> for PLGraph<T> {
    type Iter<'a> = std::iter::Empty<usize>
    where
        Self: 'a;

    type LabelIter<'a> = std::iter::Empty<(&'a T, <Self as LabelGraph<T>>::Iter<'a>)>
    where
        Self: 'a,
        T: 'a;

    type EdgeLabelIter<'a> = std::iter::Empty<T>
    where
        Self: 'a,
        T: 'a;

    #[inline]
    fn query_label(&self, label: T) -> Option<usize> {
        self.label_index_map.get(&label).copied()
    }

    #[inline]
    fn vertex_label(&self, node_id: usize) -> Result<Option<T>, Error> {
        if let Some(node) = self.nodes.get(node_id) {
            Ok(Some(node.label))
        } else {
            Err(Error::IndexOutOfBounds(node_id, self.nodes.len()))
        }
    }

    fn edge_label(&self, _source: usize, _target: usize) -> Result<Self::EdgeLabelIter<'_>, Error> {
        unimplemented!("Edges have no labels")
    }

    fn find_children_with_label(
        &self,
        _node_id: usize,
        _label: &T,
    ) -> Result<<Self as LabelGraph<T>>::Iter<'_>, Error> {
        unimplemented!("Edges have no labels")
    }

    fn labels_of(&self, _node_id: usize) -> Result<Self::LabelIter<'_>, Error> {
        unimplemented!("Edges have no labels")
    }

    fn has_edge_label(&self, _node_id: usize, _label: &T, _target: usize) -> Result<bool, Error> {
        unimplemented!("Edges have no labels")
    }
}

/// A builder that modifies PLGraph in place.
#[derive(Debug)]
pub struct PLGBuilderMut<'a, T: GraphLabel> {
    graph: &'a mut PLGraph<T>,
}

impl<'a, T: GraphLabel> BuilderMut for PLGBuilderMut<'a, T> {
    type Label = T;

    type Graph = PLGraph<T>;

    type ResultBuilder<'b> = PLGBuilderMut<'b, T>
    where
        Self::Label: 'b;

    #[inline]
    fn from_graph_mut(graph: &mut Self::Graph) -> Self::ResultBuilder<'_> {
        PLGBuilderMut { graph }
    }

    #[inline]
    fn add_vertex(&mut self, label: Self::Label) -> usize {
        if let Some(old) = self.graph.label_index_map.get(&label) {
            *old
        } else {
            let new_node = PLNode::new(Default::default(), Default::default(), label);
            self.graph.nodes.push(new_node);

            let new_index = self.graph.nodes.len() - 1;

            self.graph.label_index_map.insert(label, new_index);

            new_index
        }
    }

    #[inline]
    fn add_edge(&mut self, source: usize, target: usize, _label: Self::Label) -> Result<(), Error> {
        if self.graph.has_edge(source, target)? {
            return Ok(());
        }

        // The validity of source and target is guaranteed now.

        let parent_child_index = self.graph.degree(source).unwrap();

        self.graph
            .nodes
            .get_mut(source)
            .unwrap()
            .children
            .insert(target);

        self.graph
            .nodes
            .get_mut(target)
            .unwrap()
            .parents
            .insert(source, parent_child_index);

        Ok(())
    }

    /// Remove an edge from the source to the target.
    ///
    /// Since some graphs are labelled, the users are allowed to pass
    /// a predicate to determine if an edge from the source to the
    /// target should be removed.
    ///
    /// # Performance
    ///
    /// Removal is slow since we need to keep the order of the elements.
    fn remove_edge<F>(&mut self, source: usize, target: usize, _predicate: F) -> Result<(), Error>
    where
        F: FnMut(Self::Label) -> bool,
    {
        if !self.graph.has_edge(source, target)? {
            return Ok(());
        }

        // Both source and target are valid indices now.

        let child_index = *self
            .graph
            .nodes
            .get(target)
            .unwrap()
            .parents
            .get(&source)
            .unwrap();

        let source_degree = self.graph.degree(source).unwrap();

        // Decrement the relevant children's parents index.
        for i in (child_index + 1)..source_degree {
            let child = *self
                .graph
                .nodes
                .get(source)
                .unwrap()
                .children
                .children
                .get(i)
                .unwrap();

            *self
                .graph
                .nodes
                .get_mut(child)
                .unwrap()
                .parents
                .get_mut(&source)
                .unwrap() -= 1;
        }

        self.graph
            .nodes
            .get_mut(source)
            .unwrap()
            .children
            .remove(target);

        self.graph
            .nodes
            .get_mut(target)
            .unwrap()
            .parents
            .remove(&source);

        Ok(())
    }
}

#[cfg(test)]
mod binary_test {
    use super::*;
    use std::collections::HashSet as Set;

    macro_rules! set {
        ($type:tt) => { Set::<$type>::default() };
        ($($num:expr),*) => {
            {
                let mut set: Set<_> = Set::default();
                $(set.insert($num);)*
                set
            }
        };
    }

    #[test]
    fn test_graph_apis() -> Result<(), Error> {
        let mut graph: PLGraph<usize> = Default::default();

        // testing empty graph
        assert!(graph.is_empty());

        let mut builder = PLGBuilderMut::from_graph_mut(&mut graph);

        // testing adding an empty node
        assert_eq!(builder.add_vertex(0), 0);

        // testing nodes_len
        assert_eq!(graph.nodes_len(), 1);

        let mut builder = PLGBuilderMut::from_graph_mut(&mut graph);

        // testing more vertices and edges

        builder.add_vertex(1);
        builder.add_vertex(2);
        builder.add_vertex(3);
        builder.add_vertex(4);
        builder.add_vertex(5);

        builder.add_edge(1, 0, 0)?;
        builder.add_edge(2, 0, 0)?;
        builder.add_edge(2, 1, 0)?;
        builder.add_edge(3, 0, 0)?;
        builder.add_edge(3, 2, 0)?;
        builder.add_edge(4, 1, 0)?;
        builder.add_edge(4, 2, 0)?;
        builder.add_edge(5, 2, 0)?;
        builder.add_edge(5, 3, 0)?;
        builder.add_edge(5, 1, 0)?;

        // testing adding a duplicatedly labelled node
        assert_eq!(builder.add_vertex(0), 0);

        let graph = graph;

        // ensuring the correct length
        assert_eq!(graph.nodes_len(), 6);

        // testing children_of
        assert_eq!(graph.children_of(5)?.collect::<Set<_>>(), set!(1, 3, 2));

        // testing parents_of

        assert_eq!(
            graph.parents_of(0)?.collect::<Set<_>>(),
            set!(Parent::new(1, 0), Parent::new(2, 0), Parent::new(3, 0))
        );

        assert_eq!(
            graph.parents_of(1)?.collect::<Set<_>>(),
            set!(Parent::new(2, 1), Parent::new(4, 0), Parent::new(5, 2))
        );

        assert_eq!(graph.parents_of(5)?.len(), 0);

        // testing degree
        assert_eq!(graph.degree(4)?, 2);

        // testing is_empty_node
        assert!(graph.is_empty_node(0)?);
        assert!(!graph.is_empty_node(1)?);

        // testing has_edge
        assert!(graph.has_edge(3, 2)?);
        assert!(!graph.has_edge(3, 1)?);
        assert!(matches!(
            graph.has_edge(3, 6),
            Err(Error::IndexOutOfBounds(6, 6))
        ));

        Ok(())
    }
}

#[cfg(test)]
mod test_plgraph_builder {
    use super::*;

    #[test]
    fn test_builder() -> Result<(), Box<dyn std::error::Error>> {
        let mut graph = PLGraph::<usize>::default();
        let mut builder = PLGBuilderMut::from_graph_mut(&mut graph);

        // Add five nodes
        builder.add_vertex(0);
        builder.add_vertex(1);
        builder.add_vertex(2);
        builder.add_vertex(3);
        builder.add_vertex(4);

        // println!("five empty nodes: {builder:?}");

        // Link each node to its successor and link the last node with
        // the first one to form a cycle.
        for i in 0..5 {
            builder.add_edge(i, if i < 4 { i + 1 } else { 0 }, 0)?;
        }

        // println!("a cycle of five nodes: {builder:?}");

        // Remove the link from the last node to the first node.
        builder.remove_edge(4, 0, |_| true)?;

        // println!("a line of five nodes: {builder:?}");

        // build a graph

        let graph = graph;

        println!("final graph: {graph:?}");

        Ok(())
    }

    #[test]
    fn test_errors() -> Result<(), Box<dyn std::error::Error>> {
        let mut graph = PLGraph::<usize>::default();
        let mut builder = PLGBuilderMut::from_graph_mut(&mut graph);

        // Add five nodes
        builder.add_vertex(0);
        builder.add_vertex(1);
        builder.add_vertex(2);
        builder.add_vertex(3);
        builder.add_vertex(4);

        // println!("five empty nodes: {builder:?}");

        // Errors in add_edge

        // println!();
        // println!("Testing errors in add_edge:");
        // println!();

        assert!(matches!(
            builder.add_edge(0, 5, 0),
            Err(Error::IndexOutOfBounds(5, 5))
        ));

        // println!("Right error for an index out of bounds as the target");

        assert!(matches!(
            builder.add_edge(10, 5, 0),
            Err(Error::IndexOutOfBounds(10, 5))
        ));

        // println!("Right error for an index out of bounds as the source");

        assert!(matches!(
            builder.add_edge(10, 50, 0),
            Err(Error::IndexOutOfBounds(10, 5))
        ));

        // println!("Right error for both indices out of bounds");

        // Errors in remove_edge

        // println!();
        // println!("Testing errors in remove_edge:");
        // println!();

        assert!(matches!(
            builder.remove_edge(0, 5, |_| true),
            Err(Error::IndexOutOfBounds(5, 5))
        ));

        // println!("Right error for an index out of bounds as the target");

        assert!(matches!(
            builder.remove_edge(10, 5, |_| true),
            Err(Error::IndexOutOfBounds(10, 5))
        ));

        // println!("Right error for an index out of bounds as the source");

        assert!(matches!(
            builder.remove_edge(10, 50, |_| true),
            Err(Error::IndexOutOfBounds(10, 5))
        ));

        // println!("Right error for both indices out of bounds");

        assert!(builder.remove_edge(0, 1, |_| true).is_ok());

        // println!("No errors for removing a non-existing edge");

        // println!();

        let graph = graph;

        println!("final graph: {graph:?}");

        Ok(())
    }
}