fera_graph/traverse/
recursive_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 RecursiveDfs: WithEdge {
13    fn recursive_dfs<V>(
14        &self,
15        vis: V,
16    ) -> RecursiveDfsAlg<&Self, V, AllVertices<Self>, NewVertexProp<Self, Color>>
17    where
18        V: Visitor<Self>,
19    {
20        RecursiveDfsAlg(
21            self,
22            vis,
23            AllVertices(self),
24            NewVertexProp(self, Color::White),
25        )
26    }
27}
28
29impl<G: WithEdge> RecursiveDfs for G {}
30
31generic_struct! {
32    #[must_use = "call .run() to execute the algorithm"]
33    pub struct RecursiveDfsAlg(graph, visitor, roots, color)
34}
35
36impl<'a, G, V, R, C> RecursiveDfsAlg<&'a G, V, R, C> {
37    pub fn run(self) -> Control
38    where
39        G: Incidence,
40        V: Visitor<G>,
41        R: IntoIterator<Item = Vertex<G>>,
42        C: ParamDerefMut,
43        C::Target: VertexPropMut<G, Color>,
44    {
45        let RecursiveDfsAlg(g, mut vis, roots, color) = self;
46        return_unless!(vis.start(g));
47        let mut color = color.build();
48        for v in roots {
49            if color[v] == Color::White {
50                color[v] = Color::Gray;
51                return_unless!(vis.discover_root_vertex(g, v));
52                return_unless!(recursive_dfs_visit(
53                    g,
54                    G::edge_none(),
55                    v,
56                    &mut *color,
57                    &mut vis
58                ));
59                return_unless!(vis.finish_root_vertex(g, v));
60            }
61        }
62        vis.finish(g)
63    }
64
65    pub fn root(self, root: Vertex<G>) -> RecursiveDfsAlg<&'a G, V, iter::Once<Vertex<G>>, C>
66    where
67        G: WithVertex,
68    {
69        self.roots(iter::once(root))
70    }
71
72    pub fn ignore_color_changes(self) -> RecursiveDfsAlg<&'a G, V, R, Owned<IgnoreWriteProp<Color>>>
73    where
74        G: WithVertex,
75    {
76        let color = Owned(self.0.vertex_prop(Color::White));
77        self.color(color)
78    }
79}
80
81pub fn recursive_dfs_visit<G, C, V>(
82    g: &G,
83    from: OptionEdge<G>,
84    u: Vertex<G>,
85    color: &mut C,
86    vis: &mut V,
87) -> Control
88where
89    G: Incidence,
90    C: VertexPropMut<G, Color>,
91    V: Visitor<G>,
92{
93    color[u] = Color::Gray;
94    return_unless!(vis.discover_vertex(g, u));
95    for e in g.out_edges(u) {
96        let v = g.target(e);
97        if g.orientation(e).is_undirected() && color[v] == Color::Black || G::edge_some(e) == from {
98            continue;
99        }
100        return_unless!(vis.discover_edge(g, e));
101        match color[v] {
102            Color::White => {
103                return_unless!(vis.discover_tree_edge(g, e));
104                return_unless!(recursive_dfs_visit(g, e.into(), v, color, vis));
105                return_unless!(vis.finish_tree_edge(g, e));
106            }
107            Color::Gray => {
108                return_unless!(vis.discover_back_edge(g, e));
109            }
110            Color::Black => {
111                return_unless!(vis.discover_cross_or_forward_edge(g, e));
112            }
113        }
114        return_unless!(vis.finish_edge(g, e));
115    }
116    color[u] = Color::Black;
117    return_unless!(vis.finish_vertex(g, u));
118    Control::Continue
119}
fera_graph/traverse/recursive_dfs.rs

fera_graph/traverse/
recursive_dfs.rs
