1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96

/*
 * Copyright (c) 2017, 2018 Frank Fischer <frank-fischer@shadow-soft.de>
 *
 * This program is free software: you can redistribute it and/or
 * modify it under the terms of the GNU General Public License as
 * published by the Free Software Foundation, either version 3 of the
 * License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see  <http://www.gnu.org/licenses/>
 */

//! Breath-first-search algorithms.

use graph::{IndexDigraph, IndexGraph, IndexNodeVec};
use std::collections::VecDeque;

/// Do a breath-first-search on an undirected graph starting in `u`.
///
/// The function returns the incoming edge of each node.
///
/// # Example
///
/// ```
/// use rs_graph::{LinkedListGraph, Graph, IndexGraph, classes, bfs};
///
/// let g: LinkedListGraph = classes::peterson();
/// let u = g.id2node(0);
/// let tree = bfs::undirected(&g, u);
///
/// let dist = |mut v| {
///     let mut d = 0;
///     while let Some(e) = tree[v] {
///         let (x,y) = g.enodes(e);
///         d += 1;
///         v = if x == v { y } else { x };
///     }
///     d
/// };
/// let dists: Vec<_> = g.nodes().map(|v| dist(v)).collect();
/// assert!(tree[u].is_none());
/// assert_eq!(dists.iter().filter(|&&d| d == 0).count(), 1);
/// assert_eq!(dists.iter().filter(|&&d| d == 1).count(), 3);
/// assert_eq!(dists.iter().filter(|&&d| d == 2).count(), 6);
/// ```
pub fn undirected<'g, G>(g: &'g G, u: G::Node) -> IndexNodeVec<'g, G, Option<G::Edge>>
where
    G: IndexGraph<'g>,
{
    let mut preds = idxnodevec![g; None];
    let mut q = VecDeque::new();

    q.push_back(u);

    while let Some(v) = q.pop_front() {
        for (e, w) in g.neighs(v) {
            if w != u && preds[w].is_none() {
                preds[w] = Some(e);
                q.push_back(w);
            }
        }
    }

    preds
}

/// Do a breath-first-search on an directed graph starting in `u`.
///
/// The search traverses edges only in forward direction.
///
/// The function returns the incoming edge of each node.
pub fn directed<'g, G>(g: &'g G, u: G::Node) -> IndexNodeVec<'g, G, Option<G::Edge>>
where
    G: IndexDigraph<'g>,
{
    let mut preds = idxnodevec![g; None];
    let mut q = VecDeque::new();

    q.push_back(u);

    while let Some(v) = q.pop_front() {
        for (e, w) in g.outedges(v) {
            if w != u && preds[w].is_none() {
                preds[w] = Some(e);
                q.push_back(w);
            }
        }
    }

    preds
}