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

fera_graph/traverse/
bfs.rs
