fera_graph/algs/
trees.rs

1// This Source Code Form is subject to the terms of the Mozilla Public
2// License, v. 2.0. If a copy of the MPL was not distributed with this
3// file, You can obtain one at http://mozilla.org/MPL/2.0/.
4
5//! Trees related algortihms, including testing if a graph is a tree.
6
7use prelude::*;
8use props::Color;
9use traverse::*;
10
11pub trait Trees: Incidence {
12    fn is_tree(&self) -> bool
13    where
14        Self: VertexList + EdgeList + WithVertexProp<Color>,
15    {
16        let mut tree = true;
17        self.dfs(IsTree(&mut tree)).run();
18        tree
19    }
20
21    fn tree_diameter(&self) -> Result<usize, ()>
22    where
23        Self: VertexList + EdgeList + WithVertexProp<Color>,
24    {
25        let mut tree = false;
26        let mut dist = 0;
27        let mut v = Self::vertex_none();
28        self.dfs((IsTree(&mut tree), FarthestVertex(&mut v, &mut dist)))
29            .run();
30        if tree {
31            Ok(v.into_option()
32                .map(|r| {
33                    self.dfs(FarthestVertex(&mut Self::vertex_none(), &mut dist))
34                        .root(r)
35                        .run();
36                    dist
37                })
38                .unwrap_or(0))
39        } else {
40            Err(())
41        }
42    }
43}
44
45impl<G: Incidence> Trees for G {}
46
47pub struct IsTree<'a> {
48    tree: &'a mut bool,
49    saw_root: bool,
50}
51
52#[allow(non_snake_case)]
53pub fn IsTree(tree: &mut bool) -> IsTree {
54    IsTree {
55        tree: tree,
56        saw_root: false,
57    }
58}
59
60// FIXME: should not require VertexList and EdgeList, it is just an optimization
61impl<'a, G: VertexList + EdgeList> Visitor<G> for IsTree<'a> {
62    fn start(&mut self, g: &G) -> Control {
63        self.saw_root = false;
64        *self.tree = g.num_vertices() == 0 || g.num_edges() == g.num_vertices() - 1;
65        continue_if(*self.tree)
66    }
67
68    fn discover_back_edge(&mut self, _g: &G, _e: Edge<G>) -> Control {
69        *self.tree = false;
70        Control::Break
71    }
72
73    fn discover_root_vertex(&mut self, _g: &G, _v: Vertex<G>) -> Control {
74        if self.saw_root {
75            *self.tree = false;
76            Control::Break
77        } else {
78            self.saw_root = true;
79            Control::Continue
80        }
81    }
82}
83
84#[cfg(test)]
85mod tests {
86    use super::*;
87    use algs::Distances;
88    use rand::prelude::*;
89
90    #[test]
91    fn tree_diameter() {
92        let mut rng = SmallRng::from_entropy();
93        for n in 1..10 {
94            for _ in 0..20 {
95                let g = StaticGraph::new_random_tree(n, &mut rng);
96                assert_eq!(g.tree_diameter(), Ok(g.diameter()));
97            }
98        }
99
100        for n in 3..30 {
101            for d in 2..n - 1 {
102                let g = StaticGraph::new_random_tree_with_diameter(n, d, &mut rng).unwrap();
103                assert_eq!(Ok(d as usize), g.tree_diameter());
104            }
105        }
106    }
107}
fera_graph/algs/trees.rs

fera_graph/algs/
trees.rs
