wolf-graph 0.1.0

use std::marker::PhantomData;

use anyhow::{Result, bail};

use crate::{DFSVisitor, DepthFirstSearch, EdgeID, Error, NodeID, Nodes, VisitableGraph};

/// A trait for a graph that supports checking whether it is a tree.
pub trait IsTree {
    type Graph: VisitableGraph;

    fn is_tree(&self, root: impl AsRef<NodeID>) -> bool;

    fn check_is_tree(&self, root: impl AsRef<NodeID>) -> Result<()> {
        if !self.is_tree(root) {
            bail!(Error::NotATree);
        }
        Ok(())
    }
}

impl<G> IsTree for G
where
    G: DepthFirstSearch<G, bool> + VisitableGraph,
{
    type Graph = G;

    fn is_tree(&self, root: impl AsRef<NodeID>) -> bool {
        let root = root.as_ref();
        if self.is_empty() {
            return false;
        }
        let mut visitor = IsTreeVisitor::new(root.clone());
        self.depth_first_search_opt(&mut visitor, &Nodes::from([root.clone()]), false, None::<EdgeID>).unwrap()
    }
}

pub struct IsTreeVisitor<Graph> {
    root: NodeID,
    graph: PhantomData<Graph>,
}

impl<Graph> IsTreeVisitor<Graph>
where
    Graph: VisitableGraph,
{
    pub fn new(root: NodeID) -> Self {
        Self {
            root,
            graph: PhantomData,
        }
    }
}

impl<Graph> DFSVisitor for IsTreeVisitor<Graph>
where
    Graph: VisitableGraph,
{
    type Graph = Graph;
    type Output = bool;

    fn start_node(&mut self, _graph: &Self::Graph, node: &NodeID) -> Result<Option<bool>> {
        Ok(if node == &self.root { None } else { Some(false) })
    }

    fn back_edge(&mut self, _graph: &Self::Graph, _edge: &EdgeID) -> Result<Option<bool>> {
        Ok(Some(false))
    }

    fn forward_or_cross_edge(&mut self, _graph: &Self::Graph, _edge: &EdgeID) -> Result<Option<bool>> {
        Ok(Some(false))
    }

    fn finish(&mut self, _graph: &Self::Graph) -> Result<bool> {
        Ok(true)
    }
}