fera_graph/traverse/
dfs.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
5use params::*;
6use prelude::*;
7use props::{Color, IgnoreWriteProp};
8use traverse::*;
9
10use std::iter;
11
12pub trait Dfs: WithEdge {
13    fn dfs<V>(
14        &self,
15        vis: V,
16    ) -> DfsAlg<&Self, V, AllVertices<Self>, NewVertexProp<Self, Color>, Owned<DfsStack<Self>>>
17    where
18        V: Visitor<Self>,
19    {
20        DfsAlg(
21            self,
22            vis,
23            AllVertices(self),
24            NewVertexProp(self, Color::White),
25            Owned(DfsStack::<Self>::new()),
26        )
27    }
28}
29
30impl<G: WithEdge> Dfs for G {}
31
32generic_struct! {
33    #[must_use = "call .run() to execute the algorithm"]
34    pub struct DfsAlg(graph, visitor, roots, color, stack)
35}
36
37impl<'a, G, V, R, C, S> DfsAlg<&'a G, V, R, C, S> {
38    pub fn run(self) -> Control
39    where
40        G: Incidence,
41        V: Visitor<G>,
42        R: IntoIterator<Item = Vertex<G>>,
43        C: ParamDerefMut,
44        C::Target: VertexPropMut<G, Color>,
45        S: ParamDerefMut<Target = DfsStack<'a, G>>,
46    {
47        let DfsAlg(g, mut vis, roots, color, stack) = self;
48        return_unless!(vis.start(g));
49        let mut color = color.build();
50        let mut stack = stack.build();
51        for v in roots {
52            if color[v] == Color::White {
53                color[v] = Color::Gray;
54                stack.push((G::edge_none(), v, g.out_edges(v)));
55                return_unless!(vis.discover_root_vertex(g, v));
56                return_unless!(vis.discover_vertex(g, v));
57                return_unless!(dfs_visit(g, &mut *color, &mut *stack, &mut vis));
58                return_unless!(vis.finish_root_vertex(g, v));
59            }
60        }
61        vis.finish(g)
62    }
63
64    pub fn root(self, root: Vertex<G>) -> DfsAlg<&'a G, V, iter::Once<Vertex<G>>, C, S>
65    where
66        G: WithVertex,
67    {
68        self.roots(iter::once(root))
69    }
70
71    pub fn ignore_color_changes(self) -> DfsAlg<&'a G, V, R, Owned<IgnoreWriteProp<Color>>, S>
72    where
73        G: WithVertex,
74    {
75        let color = Owned(self.0.vertex_prop(Color::White));
76        self.color(color)
77    }
78}
79
80pub fn dfs_visit<'a, G, C, V>(
81    g: &'a G,
82    color: &mut C,
83    stack: &mut DfsStack<'a, G>,
84    vis: &mut V,
85) -> Control
86where
87    G: Incidence,
88    C: VertexPropMut<G, Color>,
89    V: Visitor<G>,
90{
91    'out: while let Some((from, u, mut inc)) = stack.pop() {
92        while let Some(e) = inc.next() {
93            let v = g.target(e);
94            if g.orientation(e).is_undirected() && color[v] == Color::Black
95                || G::edge_some(e) == from
96            {
97                continue;
98            }
99            return_unless!(vis.discover_edge(g, e));
100            match color[v] {
101                Color::White => {
102                    color[v] = Color::Gray;
103                    stack.push((from, u, inc));
104                    stack.push((e.into(), v, g.out_edges(v)));
105                    return_unless!(vis.discover_tree_edge(g, e));
106                    return_unless!(vis.discover_vertex(g, v));
107                    continue 'out;
108                }
109                Color::Gray => {
110                    return_unless!(vis.discover_back_edge(g, e));
111                }
112                Color::Black => {
113                    return_unless!(vis.discover_cross_or_forward_edge(g, e));
114                }
115            }
116            return_unless!(vis.finish_edge(g, e));
117        }
118        color[u] = Color::Black;
119        return_unless!(vis.finish_vertex(g, u));
120        if let Some(from) = from.into_option() {
121            return_unless!(vis.finish_tree_edge(g, from));
122            return_unless!(vis.finish_edge(g, from));
123        }
124    }
125    Control::Continue
126}
127
128pub type DfsStack<'a, G> = Vec<(OptionEdge<G>, Vertex<G>, OutEdgeIter<'a, G>)>;
129
130// Tests
131
132#[cfg(test)]
133mod tests {
134    use fera_fun::vec;
135    use prelude::*;
136    use traverse::TraverseEvent::*;
137    use traverse::*;
138
139    fn new() -> StaticGraph {
140        //    1
141        //  / | \         4
142        // 0  |  3      /   \
143        //  \ | /      5 --- 6
144        //    2
145        graph!(
146            7,
147            (0, 1),
148            (0, 2),
149            (1, 2),
150            (1, 3),
151            (2, 3),
152            (4, 5),
153            (4, 6),
154            (5, 6)
155        )
156    }
157
158    #[test]
159    fn events() {
160        let g = new();
161        let v = vec(g.vertices());
162        let e = |x: usize, y: usize| g.edge_by_ends(v[x], v[y]);
163        let expected = vec![
164            Start,
165            DiscoverRootVertex(0),
166            DiscoverVertex(0),
167            DiscoverEdge(e(0, 1)),
168            DiscoverTreeEdge(e(0, 1)),
169            DiscoverVertex(1),
170            DiscoverEdge(e(1, 2)),
171            DiscoverTreeEdge(e(1, 2)),
172            DiscoverVertex(2),
173            DiscoverEdge(e(2, 0)),
174            DiscoverBackEdge(e(2, 0)),
175            FinishEdge(e(2, 0)),
176            DiscoverEdge(e(2, 3)),
177            DiscoverTreeEdge(e(2, 3)),
178            DiscoverVertex(3),
179            DiscoverEdge(e(3, 1)),
180            DiscoverBackEdge(e(3, 1)),
181            FinishEdge(e(3, 1)),
182            FinishVertex(3),
183            FinishTreeEdge(e(2, 3)),
184            FinishEdge(e(2, 3)),
185            FinishVertex(2),
186            FinishTreeEdge(e(1, 2)),
187            FinishEdge(e(1, 2)),
188            FinishVertex(1),
189            FinishTreeEdge(e(0, 1)),
190            FinishEdge(e(0, 1)),
191            FinishVertex(0),
192            FinishRootVertex(0),
193            DiscoverRootVertex(4),
194            DiscoverVertex(4),
195            DiscoverEdge(e(4, 5)),
196            DiscoverTreeEdge(e(4, 5)),
197            DiscoverVertex(5),
198            DiscoverEdge(e(5, 6)),
199            DiscoverTreeEdge(e(5, 6)),
200            DiscoverVertex(6),
201            DiscoverEdge(e(6, 4)),
202            DiscoverBackEdge(e(6, 4)),
203            FinishEdge(e(6, 4)),
204            FinishVertex(6),
205            FinishTreeEdge(e(5, 6)),
206            FinishEdge(e(5, 6)),
207            FinishVertex(5),
208            FinishTreeEdge(e(4, 5)),
209            FinishEdge(e(4, 5)),
210            FinishVertex(4),
211            FinishRootVertex(4),
212            Finish,
213        ];
214
215        let mut v = vec![];
216        g.recursive_dfs(OnTraverseEvent(|evt| v.push(evt))).run();
217        assert_eq!(expected, v);
218
219        v.clear();
220        g.dfs(OnTraverseEvent(|evt| v.push(evt))).run();
221        assert_eq!(expected, v);
222    }
223}
fera_graph/traverse/dfs.rs

fera_graph/traverse/
dfs.rs
