rs-graph 0.21.0

/*
 * Copyright (c) 2017 2018, 2020 2021, 2023 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/>
 */

//! Breadth-first search.
//!
//! # Example
//!
//! ```
//! use rs_graph::experimental::graphs::{OutEdges, VecGraph};
//! use rs_graph::experimental::traits::{AdjList, Graph, Digraph};
//! use rs_graph::experimental::algorithms::search::bfs;
//!
//! let edges: Vec<(u32, u32)> = vec![(0, 2), (0, 3), (1, 0), (2, 1), (2, 3), (4, 1)];
//! let g = VecGraph::<u32>::from_edge_list((5, &edges[..])).unwrap();
//!
//! let mut found = false;
//! let mut cnt = 0;
//! let mut dists = vec![usize::MAX; g.num_nodes()];
//! let start = 4_u32;
//! dists[start as usize] = 0;
//! for (u, e) in bfs::start(OutEdges(&g), start) {
//!     dists[u as usize] = dists[g.src(e) as usize] + 1;
//!     cnt += 1;
//! }
//! assert_eq!(cnt, 4);
//! assert_eq!(dists, vec![2, 1, 3, 3, 0]);
//! ```

use crate::experimental::traits::collections::{Queue, Set};
use crate::experimental::traits::AdjList;

use core::hash::Hash;
use std::collections::{HashSet, VecDeque};

/// Start and return a Bfs iterator using default data structures.
///
/// This is a convenience wrapper around [`start_with_data`] using the default
/// data structure ([`HashSet`] and [`VecDeque`]).
///
/// # Parameter
/// - `adj`: adjacency information for the graph
/// - `start`: the node at which the search should start.
pub fn start<A>(adj: A, start: A::Node) -> Bfs<A, HashSet<A::Node>, VecDeque<A::Node>>
where
    A: AdjList,
    A::Node: Clone + Eq + Hash,
{
    start_with_data(adj, start, HashSet::default(), VecDeque::default())
}

/// Start and return a Bfs iterator with user defined data structures.
///
/// The returned iterator traverses the edges in breadth-first order. The
/// iterator returns the next node and its incoming edge.
///
/// Note that the start node is *not* returned by the iterator.
///
/// The algorithm requires node set `S` implementing
/// [`Set<A::Node>`][crate::experimental::traits::collections::Set],
/// and `Q` implementing
/// [`Queue<A::Node>`][crate::experimental::traits::collections::Queue]
/// as internal data structures. The set is used to track visited
/// nodes. The queue is used to handle the nodes in breadth-first
/// order. The data structures can be reused for multiple searches.
///
/// # Parameter
/// - `adj`: adjacency information for the graph
/// - `start`: the node at which the search should start.
/// - `set`: a node set data structure
/// - `queue`: a node queue data structure
///
/// # Example
///
/// ```
/// use rs_graph::LinkedListGraph;
/// use rs_graph::traits::*;
/// use rs_graph::classes;
/// use rs_graph::search::bfs;
/// use std::collections::{HashMap, VecDeque};
///
/// let g: LinkedListGraph = classes::peterson();
/// let mut cnt = 0;
/// for (u, e) in bfs::start_with_data(g.neighbors(), g.id2node(0),
///                                    (HashMap::new(), VecDeque::new()))
/// {
///     assert_ne!(g.node_id(u), 0);
///     cnt += 1;
/// }
/// assert_eq!(cnt, g.num_nodes() - 1);
/// ```
pub fn start_with_data<A, S, Q>(adj: A, start: A::Node, set: S, queue: Q) -> Bfs<A, S, Q>
where
    A: AdjList,
    A::Node: Clone,
    S: Set<A::Node>,
    Q: Queue<A::Node>,
{
    let mut seen = set;
    let mut queue = queue;
    queue.clear();
    seen.clear();

    let current_it = adj.neighs(start.clone());
    seen.insert(start);

    Bfs {
        adj,
        seen,
        queue,
        current_it,
    }
}

/// The breath-first search iterator.
pub struct Bfs<A, S, Q>
where
    A: AdjList,
{
    adj: A,
    seen: S,
    queue: Q,
    current_it: A::NeighIter,
}

impl<A, S, Q> Iterator for Bfs<A, S, Q>
where
    A: AdjList,
    A::Node: Clone + PartialEq,
    S: Set<A::Node>,
    Q: Queue<A::Node>,
{
    type Item = (A::Node, A::Edge);

    fn next(&mut self) -> Option<Self::Item> {
        loop {
            while let Some((e, v)) = self.current_it.next() {
                if v != self.start && self.seen.insert(v.clone()) {
                    self.queue.enqueue(v.clone());
                    return Some((v, e));
                }
            }
            if let Some(u) = self.queue.dequeue() {
                self.current_it = self.adj.neighs(u);
            } else {
                return None;
            }
        }
    }
}