wolf_graph/algo/
is_tree.rs

1use std::marker::PhantomData;
2
3use anyhow::{Result, bail};
4
5use crate::{DFSVisitor, DepthFirstSearch, EdgeID, Error, NodeID, Nodes, VisitableGraph};
6
7/// A trait for a graph that supports checking whether it is a tree.
8pub trait IsTree {
9    type Graph: VisitableGraph;
10
11    fn is_tree(&self, root: impl AsRef<NodeID>) -> bool;
12
13    fn check_is_tree(&self, root: impl AsRef<NodeID>) -> Result<()> {
14        if !self.is_tree(root) {
15            bail!(Error::NotATree);
16        }
17        Ok(())
18    }
19}
20
21impl<G> IsTree for G
22where
23    G: DepthFirstSearch<G, bool> + VisitableGraph,
24{
25    type Graph = G;
26
27    fn is_tree(&self, root: impl AsRef<NodeID>) -> bool {
28        let root = root.as_ref();
29        if self.is_empty() {
30            return false;
31        }
32        let mut visitor = IsTreeVisitor::new(root.clone());
33        self.depth_first_search_opt(&mut visitor, &Nodes::from([root.clone()]), false, None::<EdgeID>).unwrap()
34    }
35}
36
37pub struct IsTreeVisitor<Graph> {
38    root: NodeID,
39    graph: PhantomData<Graph>,
40}
41
42impl<Graph> IsTreeVisitor<Graph>
43where
44    Graph: VisitableGraph,
45{
46    pub fn new(root: NodeID) -> Self {
47        Self {
48            root,
49            graph: PhantomData,
50        }
51    }
52}
53
54impl<Graph> DFSVisitor for IsTreeVisitor<Graph>
55where
56    Graph: VisitableGraph,
57{
58    type Graph = Graph;
59    type Output = bool;
60
61    fn start_node(&mut self, _graph: &Self::Graph, node: &NodeID) -> Result<Option<bool>> {
62        Ok(if node == &self.root { None } else { Some(false) })
63    }
64
65    fn back_edge(&mut self, _graph: &Self::Graph, _edge: &EdgeID) -> Result<Option<bool>> {
66        Ok(Some(false))
67    }
68
69    fn forward_or_cross_edge(&mut self, _graph: &Self::Graph, _edge: &EdgeID) -> Result<Option<bool>> {
70        Ok(Some(false))
71    }
72
73    fn finish(&mut self, _graph: &Self::Graph) -> Result<bool> {
74        Ok(true)
75    }
76}
wolf_graph/algo/is_tree.rs

wolf_graph/algo/
is_tree.rs
