fera_graph/algs/
cycles.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//! Cycles related algorithms, including testing if a graph is acyclic.
6
7use prelude::*;
8use props::Color;
9use traverse::*;
10
11pub trait Cycles: Incidence {
12    fn is_acyclic(&self) -> bool
13    where
14        Self: VertexList + WithVertexProp<Color>,
15    {
16        let mut acyclic = true;
17        self.dfs(IsAcyclic(&mut acyclic)).run();
18        acyclic
19    }
20
21    fn is_dag(&self) -> bool
22    where
23        Self: VertexList + WithVertexProp<Color>,
24    {
25        let mut dag = true;
26        self.dfs(IsDag(&mut dag)).run();
27        dag
28    }
29}
30
31impl<G: Incidence> Cycles for G {}
32
33pub struct IsAcyclic<'a>(pub &'a mut bool);
34
35impl<'a, G: WithEdge> Visitor<G> for IsAcyclic<'a> {
36    fn start(&mut self, _g: &G) -> Control {
37        *self.0 = true;
38        Control::Continue
39    }
40
41    fn discover_back_edge(&mut self, _g: &G, _e: Edge<G>) -> Control {
42        *self.0 = false;
43        Control::Break
44    }
45}
46
47pub struct IsDag<'a>(pub &'a mut bool);
48
49impl<'a, G: WithEdge> Visitor<G> for IsDag<'a> {
50    fn start(&mut self, _g: &G) -> Control {
51        *self.0 = true;
52        Control::Continue
53    }
54
55    fn discover_edge(&mut self, g: &G, e: Edge<G>) -> Control {
56        *self.0 &= g.orientation(e).is_directed();
57        continue_if(*self.0)
58    }
59
60    fn discover_back_edge(&mut self, _g: &G, _e: Edge<G>) -> Control {
61        *self.0 = false;
62        Control::Break
63    }
64}
fera_graph/algs/cycles.rs

fera_graph/algs/
cycles.rs
