rs-graph 0.7.0

/*
 * Copyright (c) 2017 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::{IndexGraph, IndexDigraph};
use vec::NodeVec;
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) -> NodeVec<'g, G, Option<G::Edge>>
    where G: IndexGraph<'g>
{
    let mut preds = nodevec![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) -> NodeVec<'g, G, Option<G::Edge>>
    where G: IndexDigraph<'g>
{
    let mut preds = nodevec![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
}