path: root/graph/src/lib.rs

#![warn(missing_docs)]
//! This crate implements a trait API for graphs that the crate "rep"
//! needs.
//!
//! Also a default implementation for the trait is provided, so that
//! by default no external crates are needed, whereas it is easy to
//! use external crates, if so derired.

use std::hash::Hash;

use core::fmt::{Debug, Display};

pub mod error;

pub mod adset;

pub use adset::ASGraph;

pub mod adlist;

pub use adlist::ALGraph;

pub mod labelled;

pub use labelled::DLGraph;
pub use labelled::PLGraph;

pub mod builder;

pub use builder::Builder;

use error::Error;

/// The expected behaviour of an immutable graph.
pub trait Graph: Default {
    /// A type that iterates through the node indices.
    type Iter<'a>: Iterator<Item = usize> + 'a
    where
        Self: 'a;

    /// Return true if and only if the graph has no nodes.
    fn is_empty(&self) -> bool;

    /// Return the length of nodes in the graph.
    fn nodes_len(&self) -> usize;

    #[inline]
    /// Return the length of edges in the graph.
    ///
    /// This is optional.  Implementations need not support this.
    fn edges_len(&self) -> Option<usize> {
        None
    }

    #[inline]
    /// Return an iterator of nodes represented as unsigned integers.
    ///
    /// If a custom application needs to have labels on nodes, just
    /// associate the label to the node internally, and define an
    /// extension trait that allows querying those additional labels.
    ///
    /// This design choice is based on the idea that this library
    /// should be minimal and only provide the core of a graph.  As a
    /// label is not really core, it is not included here.
    fn nodes(&self) -> Box<dyn Iterator<Item = usize> + '_> {
        Box::new(0..self.nodes_len())
    }

    /// Return an iterator of edges going out of a node.
    ///
    /// Return an error if the node is not known to the graph.
    fn children_of(&self, node_id: usize) -> Result<Self::Iter<'_>, Error>;

    #[inline]
    /// Return an iterator of edges represented as pairs (FROM, TO).
    ///
    /// The default implementation iterates through the nodes and then
    /// iterates through their children.  If the implementation has a
    /// more efficient method, overwrite this method.
    fn edges(&self) -> Box<dyn Iterator<Item = (usize, usize)> + '_> {
        Box::new(self.nodes().flat_map(|node| {
            self.children_of(node)
                // If this node is invalid, this means the
                // implementation of `nodes` is wrong, so it is
                // appropriate to panic here.
                .unwrap()
                .map(move |child| (node, child))
        }))
    }

    #[inline]
    /// Return true if and only if the node is in the graph.
    fn has_node(&self, node_id: usize) -> bool {
        (0..self.nodes_len()).contains(&node_id)
    }

    /// Return the number of "children" of a node, or an error if the
    /// node is not a member of the graph.
    fn degree(&self, node_id: usize) -> Result<usize, Error>;

    /// Return a boolean indicating if the node has no children, or an
    /// error if the node is not a member of the graph.
    fn is_empty_node(&self, node_id: usize) -> Result<bool, Error>;

    /// Return true if and only if there is an edge from the source to
    /// the target.
    ///
    /// Return an error if either the source or the target is an
    /// invalid node.
    fn has_edge(&self, source: usize, target: usize) -> Result<bool, Error>;

    /// Output the edges into a graphviz file.
    fn print_viz(&self, filename: &str) -> Result<(), std::io::Error> {
        let preamble = "digraph nfa {
    fontname=\"Helvetica,Arial,sans-serif\"
    node [fontname=\"Helvetica,Arial,sans-serif\"]
    edge [fontname=\"Helvetica,Arial,sans-serif\"]
    rankdir=LR;\n";

        let mut post = String::new();

        use std::fmt::Write as FWrite;

        for (source, target) in self.edges() {
            let _ = writeln!(post, "{source} -> {target}");
        }

        post.push_str("}\n");

        let result = format!("{preamble}{post}");

        let filename = format!("output/{filename}");

        if std::fs::metadata(&filename).is_ok() {
            std::fs::remove_file(&filename)?;
        }

        let mut file = std::fs::File::options()
            .write(true)
            .create(true)
            .open(filename)?;

        use std::io::Write;

        file.write_all(result.as_bytes())
    }

    /// Returns whether or not the graph contains cycles.
    ///
    /// If, and only if, the graph contains invalid nodes, an error
    /// will be signalled.
    fn contains_cycles(&self) -> Result<bool, Error> {
        use std::collections::HashSet;

        let mut seen_nodes: HashSet<usize> = HashSet::with_capacity(self.nodes_len());

        for node in self.nodes() {
            if seen_nodes.contains(&node) {
                continue;
            }

            let mut edges_seen_nodes: HashSet<usize> = HashSet::with_capacity(self.nodes_len());

            let mut stack = Vec::with_capacity(self.nodes_len());
            stack.push(node);

            while let Some(top) = stack.pop() {
                if edges_seen_nodes.contains(&top) {
                    // a cycle is found
                    return Ok(true);
                }

                edges_seen_nodes.insert(top);

                let mut local_stack: Vec<usize> = self.children_of(top)?.collect();

                local_stack.reverse();

                stack.extend(local_stack);
            }

            seen_nodes.extend(edges_seen_nodes);
        }

        Ok(false)
    }

    /// Replace the contents of the graph by a builder.
    fn replace_by_builder(&mut self, builder: impl Builder<Result = Self>);
}

/// A graph that can be extended, but not mutated, in the sense that
/// existing nodes and edges will not be modified nor removed, but new
/// nodes can be added.  The index of the new node will be returned.
///
/// Implementations can choose to keep a set of sets of edges, so that
/// new nodes will not have duplicate edge sets.  In this case, the
/// returned new node index is not necessarily equal to
/// self.nodes_len() - 1, and hence the return type is designed in
/// this way.
pub trait ExtGraph: Graph {
    /// Add a new node with `edges`.
    ///
    /// If an edge from `edges` points to a non-existent node, return
    /// an error.
    fn extend(&mut self, edges: impl IntoIterator<Item = usize>) -> Result<usize, Error>;
}

/// The type of labels should be comparable and hashable.
pub trait GraphLabel:
    Hash + Eq + PartialEq + Clone + Copy + Ord + PartialOrd + Display + Debug
{
}

impl<T: Hash + Eq + PartialEq + Clone + Copy + Ord + PartialOrd + Display + Debug> GraphLabel
    for T
{
}

/// We need both the node index of a parent and the edge index of the
/// child that points to this parent.
#[derive(Debug, Copy, Clone, Eq, PartialEq, Ord, PartialOrd, Hash)]
pub struct Parent(usize, usize);

impl Parent {
    /// Return the index of the parent node.
    #[inline]
    pub fn node(&self) -> usize {
        self.0
    }

    /// Return the index of the edge that points to the child.
    #[inline]
    pub fn edge(&self) -> usize {
        self.1
    }

    /// Construct a parent strucure.
    #[inline]
    pub fn new(node: usize, edge: usize) -> Self {
        Self(node, edge)
    }
}

/// A parents-knowing graph can return an iterator of parents for any
/// node.
pub trait ParentsGraph: Graph {
    /// The type of an iterator that goes through the parents of a
    /// node.
    type Iter<'a>: Iterator<Item = Parent> + 'a
    where
        Self: 'a;

    /// Return an iterator of parents for a node.
    fn parents_of(&self, node_id: usize) -> Result<<Self as ParentsGraph>::Iter<'_>, Error>;

    /// We need to be able to retrieve the `n`-the child, for the edge
    /// index to be of any use.
    fn nth_child(&self, node_id: usize, n: usize) -> Result<usize, Error>;

    /// Convert an edge to a `Parent` construct.
    fn edge_to_parent(&self, source: usize, target: usize) -> Result<Option<Parent>, Error>;
}

/// An /exended/ graph in the sense that it offers the ability to
/// "redirect" children of a node to another node.
pub trait RedirectGraph: Graph {
    /// Replace the edge that points from `node_id` to the
    /// `child_index`-th child by a new edge that points to
    /// `new_child`.
    fn redirect(
        &mut self,
        node_id: usize,
        child_index: usize,
        new_child: usize,
    ) -> Result<(), Error>;
}

/// A labelled graph is just a graph with labels associated to
/// vertices and / or edges.
///
/// This trait defines what the package needs out of a labelled graph.
///
/// Any implementation should be able to handle a set of types for
/// labels, so this trait is generic over the label type.
pub trait LabelGraph<T: GraphLabel>: Graph {
    /// A type that iterates through the node indices.
    type Iter<'a>: Iterator<Item = usize> + 'a
    where
        Self: 'a;

    // TODO: Add a type that iterates through children and labels of
    // children simultaneously.  This can reduce the number of bounds
    // checking.

    /// A type that iterates through labels.
    type LabelIter<'a>: Iterator<Item = (&'a T, <Self as LabelGraph<T>>::Iter<'a>)> + 'a
    where
        Self: 'a,
        T: 'a;

    /// A type that iterates over labels of an edge.
    type EdgeLabelIter<'a>: Iterator<Item = T> + 'a
    where
        Self: 'a,
        T: 'a;

    /// Query the graph for a label, and return the node index if
    /// found.
    ///
    /// The default implementation always returns `None`.
    #[inline]
    fn query_label(&self, _label: T) -> Option<usize> {
        None
    }

    #[inline]
    /// Return the label of a vertex or an error if the node is
    /// invalid.
    ///
    /// The default implementation always returns `None` for a valid
    /// node.
    fn vertex_label(&self, node_id: usize) -> Result<Option<T>, Error> {
        if self.has_node(node_id) {
            Ok(None)
        } else {
            Err(Error::IndexOutOfBounds(node_id, self.nodes_len()))
        }
    }

    /// Return the label of an edge or an error if some node is
    /// invalid.
    fn edge_label(&self, source: usize, target: usize) -> Result<Self::EdgeLabelIter<'_>, Error>;

    /// Return an iterator of edges out of a node, whose associated
    /// label is as given.
    ///
    /// The efficiency of this method matters in implementations.
    fn find_children_with_label(
        &self,
        node_id: usize,
        label: &T,
    ) -> Result<<Self as LabelGraph<T>>::Iter<'_>, Error>;

    /// Return an iterator of labels of edges out of a node.
    ///
    /// The efficiency of this method matters in implementations.
    fn labels_of(&self, node_id: usize) -> Result<Self::LabelIter<'_>, Error>;

    /// Return true if and only if the node has an edge with the given
    /// label and target.
    fn has_edge_label(&self, node_id: usize, label: &T, target: usize) -> Result<bool, Error>;
}

/// A labelled graph that can be extended, but not mutated, in the
/// sense that existing nodes and edges will not be modified nor
/// removed, but new nodes can be added.  The index of the new node
/// will be returned.
///
/// Implementations can choose to keep a set of sets of edges, so that
/// new nodes will not have duplicate edge sets.  In this case, the
/// returned new node index is not necessarily equal to
/// self.nodes_len() - 1, and hence the return type is designed in
/// this way.
pub trait LabelExtGraph<T: GraphLabel>: LabelGraph<T> {
    /// Add a new node with `edges`.
    ///
    /// If an edge from `edges` points to a non-existent node, return
    /// an error.
    fn extend(&mut self, edges: impl IntoIterator<Item = (T, usize)>) -> Result<usize, Error>;
}

#[cfg(test)]
mod test_cycle_detection {
    use super::{builder::Builder, labelled::DLGBuilder, Graph};

    #[test]
    fn test() -> Result<(), Box<dyn std::error::Error>> {
        let mut builder: DLGBuilder<usize> = DLGBuilder::default();

        // Add five nodes
        builder.add_vertex();
        builder.add_vertex();
        builder.add_vertex();
        builder.add_vertex();
        builder.add_vertex();

        // 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 }, i)?;
        }

        let graph = builder.build_ref();

        assert!(!graph.contains_cycles()?);

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

        let graph = builder.build();

        assert!(!graph.contains_cycles()?);

        Ok(())
    }
}