cnetworks 0.7.0

/*!
Breadth-first search module.

This module implements multiple functions based on the [breadth-first
search](https://en.wikipedia.org/wiki/Breadth-first_search) algorithm.
*/

use crate::{cn, Network};
use std::collections::VecDeque as Queue;

/// Indicates whether the [`traverse`] search should continue.
pub const CONTINUE: bool = true;

/// Indicates whether the [`traverse`] search should stop.
pub const STOP: bool = false;

/// The custom breadth-first search tree network model.
pub const TREE_MODEL: &str = "_CN_BFS_TREE";

/// The shortest path in the breadth-first search tree, ie. the edges walked **from** target **to**
/// root.
///
/// The **distance** between two nodes is therefore exactly the length of this vector. A path of
/// `None` means there does not exist a path from `root` to `target`.
///
/// # Examples
/// If nodes form a simple, linear chain of length 5:
///
/// `0 <-> 1 <-> 2 <-> 3 <-> 4`
///
/// the search starts at node `0` and targets `4`, then the edges walked will be
///
/// `(4, 3), (3, 2), (2, 1), (1, 0)`
///
/// then it's [`Path`] will be
///
/// ```
/// # fn main() {
/// # fn _doc_path() -> Option<Vec<(usize, usize)>> {
/// Some(vec![(4, 3),(3, 2),(2, 1)])
/// # }}
/// ```
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Path(Option<Vec<(usize, usize)>>);

impl Path {
    /// Return a vector of nodes visited by the path, ie. ones which lay on the path.
    pub fn visited(&self) -> Option<Vec<usize>> {
        let inner = self.0.as_ref()?;
        let mut nodes: Vec<usize> = inner.iter().map(|(start, _end)| *start).collect();
        if let Some((_prev, last)) = inner.last() {
            nodes.push(*last);
        }
        Some(nodes)
    }

    /// Return an immutable reference to the wrapped data structure.
    pub fn as_vec(&self) -> Option<&Vec<(usize, usize)>> {
        self.0.as_ref()
    }

    /// Calculate common length of two paths.
    ///
    /// **Warning:** it is assumed that the paths have a common "endpoint" **AND** are situated in
    /// a tree. Don't rely on it *too* much.
    pub(crate) fn common_len(&self, other: &Path) -> Option<usize> {
        let (longer, shorter) = if self.as_vec()?.len() > other.as_vec()?.len() {
            (self.as_vec()?, other.as_vec()?)
        } else {
            (other.as_vec()?, self.as_vec()?)
        };
        let mut i = 0;
        while longer.len() - i > shorter.len() {
            i += 1;
        }
        for (step, (edge1, edge2)) in longer[i..].iter().zip(shorter.iter()).enumerate() {
            if edge1 == edge2 {
                return Some(shorter.len() - step);
            }
        }
        Some(0)
    }
}

#[test]
fn test_visited() {
    let p = Path(Some(vec![(5, 4), (4, 3), (3, 2), (2, 1), (1, 0)]));
    assert_eq!(p.visited().unwrap(), vec![5, 4, 3, 2, 1, 0]);

    let p = Path(Some(vec![(6, 3)]));
    assert_eq!(p.visited().unwrap(), vec![6, 3]);

    let p = Path(Some(vec![]));
    assert_eq!(p.visited().unwrap(), vec![]);
}

#[test]
fn test_common_len() {
    let pa = Path(Some(vec![(5, 4), (4, 3), (3, 2), (2, 1), (1, 0)]));
    assert_eq!(pa.common_len(&pa), Some(pa.as_vec().unwrap().len()));

    let pb = Path(Some(vec![(6, 3), (3, 2), (2, 1), (1, 0)]));
    assert_eq!(pa.common_len(&pb), Some(3));

    let pa = Path(Some(vec![(5, 4), (4, 3), (3, 2), (2, 1), (1, 0)]));
    let pb = Path(Some(vec![(7, 6), (6, 3), (3, 2), (2, 1), (1, 0)]));
    assert_eq!(pa.common_len(&pb), Some(3));
}

#[test]
fn test_flatten() {
    let p = Path(Some(vec![(5, 4), (4, 3), (3, 2), (2, 1), (1, 0)]));
    assert_eq!(p.visited().unwrap(), vec![5, 4, 3, 2, 1, 0]);

    let p = Path(Some(vec![(6, 3)]));
    assert_eq!(p.visited().unwrap(), vec![6, 3]);

    let p = Path(Some(vec![]));
    assert_eq!(p.visited().unwrap(), vec![]);
}

/// Perform a breadth-first search over the network, starting with root and looking for target.
/// Returns distance (ie. number of edges) from root to target or `None` if no path is found.
///
/// Returns [`cn::Err::NoSuchNode`] if the root or target nodes do not exist.
///
/// # Examples
/// ```
/// # use cnetworks::*;
/// # use std::error::Error;
/// # fn main() -> Result<(), Box<dyn Error>> {
/// let net = Network::new(100, Model::ER { p: 0.05, whole: false }, Weight::default());
/// match bfs::distance(&net, 1, 3)? {
///     Some(d) => println!("Distance between 1 and 3: {}", d),
///     None => println!("No path from 1 to 3 found!"),
/// }
/// # Ok(())
/// # }
/// ```
pub fn distance(net: &Network, root: usize, target: usize) -> cn::Result<Option<usize>> {
    if !net.exists(target) {
        return Err(cn::Err::NoSuchNode(target));
    }
    let mut distance = None;
    traverse(net, root, |current, _, depth, _| {
        if current == target {
            distance = Some(depth);
            STOP
        } else {
            CONTINUE
        }
    })?;
    Ok(distance)
}

/// Perform a breadth-first search over the network, starting with root and looking for target.
/// Returns the [`Path`] from target to root.
///
/// Returns [`cn::Err::NoSuchNode`] if the root or target nodes do not exist.
///
/// # Examples
/// ```
/// # use cnetworks::*;
/// # use std::error::Error;
/// # fn main() -> Result<(), Box<dyn Error>> {
/// let net = Network::new(100, Model::ER { p: 0.05, whole: false }, Weight::default());
/// match bfs::path(&net, 1, 3)?.as_vec() {
///     Some(p) =>  {
///         println!("Path from 3 to 1:");
///         println!("{:?}", p);
///     },
///     None => println!("No path from 1 to 3 was found!"),
/// }
/// # Ok(())
/// # }
/// ```
pub fn path(net: &Network, root: usize, target: usize) -> cn::Result<Path> {
    Ok(path_many(net, root, &[target])?[target].clone())
}

/// Like [`distance`], but with multiple targets. Returns a [`cn::VecMap`] of (target, distance) pairs.
/// If some target is not in the map it cannot be reached from `root`.
///
/// Returns [`cn::Err::NoSuchNode`] if the root or any of the target nodes do not exist and
/// [`cn::Err::NoTarget`] if the `targets` slice is empty.
///
///
/// # Examples
/// ```
/// # use cnetworks::*;
/// # use std::error::Error;
/// # fn main() -> Result<(), Box<dyn Error>> {
/// let net = Network::new(100, Model::ER { p: 0.05, whole: false }, Weight::default());
/// for (target, distance) in bfs::distance_many(&net, 1, &[2, 3])?.iter() {
///     println!("Distance from 1 to {} is {}", target, distance);
/// }
/// # Ok(())
/// # }
/// ```
pub fn distance_many(
    net: &Network,
    root: usize,
    targets: &[usize],
) -> cn::Result<cn::VecMap<usize>> {
    if targets.is_empty() {
        return Err(cn::Err::NoTarget);
    }
    let mut target_map: cn::VecSet = cn::VecSet::default();
    // Check if the targets are valid nodes
    for &t in targets {
        if !net.exists(t) {
            return Err(cn::Err::NoSuchNode(t));
        }
        target_map.insert(t);
    }
    let mut results: cn::VecMap<usize> = cn::VecMap::default();
    traverse(net, root, |current, _, depth, _| {
        if target_map.remove(current) {
            results.insert(current, depth);
        }
        if target_map.is_empty() {
            STOP
        } else {
            CONTINUE
        }
    })?;
    Ok(results)
}

/// Returns `true` if there exists a path from `root` to `target`.
///
/// Returns [`cn::Err::NoSuchNode`] if the root or the target nodes do not exist.
///
/// # Examples
/// ```
/// # use cnetworks::*;
/// # use std::error::Error;
/// # fn main() -> Result<(), Box<dyn Error>> {
/// let net = Network::new(100, Model::ER { p: 0.05, whole: true }, Weight::default());
/// assert!(bfs::reach(&net, 4, 2).unwrap());
/// # Ok(())
/// # }
/// ```
pub fn reach(net: &Network, root: usize, target: usize) -> cn::Result<bool> {
    if !net.exists(target) {
        return Err(cn::Err::NoSuchNode(target));
    }
    let mut reaches = false;
    traverse(net, root, |current, _, _, _| {
        if current == target {
            reaches = true;
            STOP
        } else {
            CONTINUE
        }
    })?;
    Ok(reaches)
}

/// Like [`reach`], but with multiple targets. Returns a [`Vec`] of reached targets.
///
/// Returns [`cn::Err::NoSuchNode`] if the root or any of the target nodes do not exist and
/// [`cn::Err::NoTarget`] if the `targets` slice is empty.
///
/// # Examples
/// ```
/// # use cnetworks::*;
/// # use std::error::Error;
/// # fn main() -> Result<(), Box<dyn Error>> {
/// let net = Network::new(100, Model::ER { p: 0.05, whole: true }, Weight::default());
/// let found = bfs::reach_many(&net, 4, &[2,3]).unwrap();
/// assert!(found.iter().collect::<Vec<_>>() == vec![2,3]
///     || found.iter().collect::<Vec<_>>() == vec![3,2]
/// );
/// # Ok(())
/// # }
/// ```
pub fn reach_many(net: &Network, root: usize, targets: &[usize]) -> cn::Result<cn::VecSet> {
    if targets.is_empty() {
        return Err(cn::Err::NoTarget);
    }
    let mut target_map: cn::VecSet = cn::VecSet::default();
    // Check if the targets are valid nodes
    for &t in targets {
        if !net.exists(t) {
            return Err(cn::Err::NoSuchNode(t));
        }
        target_map.insert(t);
    }
    let mut results: cn::VecSet = cn::VecSet::default();
    traverse(net, root, |current, _, _, _| {
        if target_map.remove(current) {
            results.insert(current);
        }
        if target_map.is_empty() {
            STOP
        } else {
            CONTINUE
        }
    })?;
    Ok(results)
}

/// Like [`path`], but with multiple targets. Returns a [`cn::VecMap`] of (target, [`Path`]) pairs.
///
/// Returns [`cn::Err::NoSuchNode`] if the root or any of the target nodes do not exist and
/// [`cn::Err::NoTarget`] if the `targets` slice is empty.
///
/// # Examples
/// ```
/// # use cnetworks::*;
/// # use std::error::Error;
/// # fn main() -> Result<(), Box<dyn Error>> {
/// let net = Network::new(100, Model::ER { p: 0.05, whole: false }, Weight::default());
/// for (target, path) in bfs::path_many(&net, 1, &[2, 3])?.iter() {
///     match path.as_vec() {
///         Some(p) => {
///             println!("Path from {} to 1:", target);
///             println!("{:?}", p);
///         },
///         None => println!("Cannot reach {} from 1", target),
///     }
/// }
/// # Ok(())
/// # }
/// ```
pub fn path_many(net: &Network, root: usize, targets: &[usize]) -> cn::Result<cn::VecMap<Path>> {
    if targets.is_empty() {
        return Err(cn::Err::NoTarget);
    }
    let mut target_map: cn::VecSet = cn::VecSet::default();
    // Check if the target and root are valid nodes
    for &t in targets {
        if !net.exists(t) {
            return Err(cn::Err::NoSuchNode(t));
        }
        target_map.insert(t);
    }
    // (node, parent) map, used to climb up the tree
    let mut discovered: cn::VecMap<Option<usize>> = cn::VecMap::default();
    let mut results: cn::VecMap<Path> = cn::VecMap::default();
    traverse(net, root, |current, parent, _, _| {
        discovered.insert(current, parent);
        if target_map.remove(current) {
            // Climb up the parents to the root and record path
            let mut path = Vec::new();
            let mut up_the_tree = parent;
            let mut prev = current;
            loop {
                match up_the_tree {
                    Some(p) => {
                        path.push((prev, p));
                        prev = p;
                        up_the_tree = discovered[p];
                    }
                    None => {
                        // Reached the root - record target's path and continue on
                        results.insert(current, Path(Some(path)));
                        break;
                    }
                }
            }
        }
        if target_map.is_empty() {
            STOP
        } else {
            CONTINUE
        }
    })?;
    for not_found in target_map.indexes() {
        results.insert(not_found, Path(None));
    }
    Ok(results)
}

/// Traverse the `net` starting at `root` and executing `on_step` at every queue pop.
///
/// The `on_step` closure is called exactly once for every visited node, providing access to
/// current node, it's parent (`None` if it's the root), it's depth (distance from the root) and a
/// [`cn::VecMap`] of previously visited nodes. The map contains `Some(())` at already seen indexes
/// and `None` at those not seen yet.
///
/// If the `on_step` closure returns `false` (or the alias `bfs::STOP`) the search will be terminated.
/// If it returns `true` (or the alias `bfs::CONTINUE`) the search will continue to the next step.
///
/// Returns [`cn::Err::NoSuchNode`] if the root node does not exist.
///
/// # Examples
/// ```
/// # use cnetworks::*;
/// # use std::error::Error;
/// # fn main() -> Result<(), Box<dyn Error>> {
/// let net = Network::new(100, Model::ER { p: 0.05, whole: false }, Weight::default());
/// bfs::traverse(
///     &net,
///     1,
///     |current: usize, parent: Option<usize>, depth: usize, seen: &cn::VecMap<()>| {
///         println!(
///             "Visiting {} at depth {}, which has {:?} as parent.",
///             current, depth, parent
///         );
///         assert!(seen.contains(current));
///         if let Some(p) = parent {
///             assert!(seen.contains(p));
///         }
///         bfs::CONTINUE
///     },
/// )?;
/// # Ok(())
/// # }
/// ```
pub fn traverse<F: FnMut(usize, Option<usize>, usize, &cn::VecMap<()>) -> bool>(
    net: &Network,
    root: usize,
    mut on_step: F,
) -> cn::Result<()> {
    // Check if the root is valid
    if !net.exists(root) {
        return Err(cn::Err::NoSuchNode(root));
    }
    // Seen those already
    let mut seen: cn::VecMap<()> = cn::VecMap::with_capacity(net.size());
    seen.insert(root, ());
    // Those need visiting
    let mut to_visit: Queue<(usize, Option<usize>, usize)> = Queue::new();
    to_visit.push_back((root, None, 0));

    while let Some((current, parent, depth)) = to_visit.pop_front() {
        if on_step(current, parent, depth, &seen) == STOP {
            break;
        }
        for &i in net.links_of(current).unwrap().keys() {
            if seen.insert(i, ()).is_none() {
                to_visit.push_back((i, Some(current), depth + 1));
            }
        }
    }
    Ok(())
}

/// Build a **breadth-first search tree** from the network, starting from `root`.
///
/// The returned [`Network`] is a **spanning** tree of the **connected subgraph** to which the `root`
/// belongs.
pub fn tree(net: &Network, root: usize) -> cn::Result<Network> {
    let mut tree = Network::default();
    tree.set_model(TREE_MODEL);
    // It's better to store the nodes here and attach them later
    traverse(net, root, |current, parent, _, _| {
        tree.attach(current).unwrap();
        if let Some(parent) = parent {
            tree.link(current, parent).unwrap();
        }
        CONTINUE
    })
    .unwrap();
    Ok(tree)
}

/// Same as [`tree`], but the resulting tree includes **only** paths from `root` to the specified
/// `targets`.
///
/// It is therefore **not** a spanning tree. If there is no path from one of the `targets` to
/// `root`, such target will **not** be present in the tree.
pub fn tree_active(net: &Network, root: usize, targets: &[usize]) -> cn::Result<Network> {
    let paths = path_many(net, root, targets)?;
    let mut tree = Network::default();
    tree.set_model(TREE_MODEL);
    tree.attach(root).unwrap();
    for (_target, path) in paths.iter() {
        if let Some(path) = path.visited() {
            if !path.is_empty() {
                tree.attach_skip(&path);
                for (&prev, &next) in path.iter().zip(path[1..].iter()) {
                    tree.link(prev, next).unwrap();
                }
            }
        }
    }
    Ok(tree)
}

/// Explore the network starting with `root`, finding all nodes for which the path from `root` to
/// `node` exists (the **explored**) and those for which it does not (the **unexplored**).
///
/// Returns a pair of [`cn::VecSet`] s: one with the explored nodes (including the root) and another
/// with the unexplored.
///
/// Returns [`cn::Err::NoSuchNode`] if the root does not exist.
///
/// # Examples
/// ```
/// # use cnetworks::*;
/// let net = Network::new(100, Model::ER { p: 0.05, whole: false }, Weight::default());
/// let (exp, unexp) = bfs::explore(&net, 1).unwrap();
/// println!("Available from 1: {:?}", exp);
/// println!("Unavailable from 1: {:?}", unexp);
/// ```
pub fn explore(net: &Network, root: usize) -> cn::Result<(cn::VecSet, cn::VecSet)> {
    let mut discovered: cn::VecSet = cn::VecSet::default();
    // Gather the undiscovered nodes
    traverse(net, root, |current, _, _, _| {
        discovered.insert(current);
        CONTINUE
    })?;
    let undiscovered: cn::VecSet = net
        .nodes()
        .filter(|index| !discovered.contains(*index))
        .collect();
    Ok((discovered, undiscovered))
}