spokes 0.3.0

#![warn(clippy::pedantic)]
#![deny(missing_docs)]

//! Network and Network Flow Optimization Tools
//!
//! # Introduction
//!
//! The following example is based on the following graph
//! ![An example graph](https://upload.wikimedia.org/wikipedia/commons/5/57/Dijkstra_Animation.gif)
//! sourced from [Wikipedia][https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm].
//!
//! Here, the goal is to find the [shortest path tree](https://en.wikipedia.org/wiki/Shortest-path_tree) rooted at node 0.
//! In the example, it is verified the distance from node 0 to node 4 is 20.
//!
//! ```
//! use spokes::{Network, algorithms::{dijkstra_shortest_path, Distance}, ArcStorage};
//!
//! let mut network: Network<usize, (), u16> = Network::new();
//! network.add_nodes((0..6).map(|i| (i, ())));
//! network.add_arcs([
//!     (0, 1, 7), (1, 0, 7),
//!     (0, 5, 14), (5, 0, 14),
//!     (0, 2, 9), (2, 0, 9),
//!     (1, 2, 10), (2, 1, 10),
//!     (1, 3, 15), (3, 1, 15),
//!     (2, 5, 2), (5, 2, 2),
//!     (2, 3, 11), (3, 2, 11),
//!     (3, 4, 6), (4, 3, 6),
//!     (4, 5, 9), (5, 4, 9),
//! ]);
//!
//! let shortest_path_tree = dijkstra_shortest_path(&network, 0);
//!
//! assert_eq!(shortest_path_tree.node(&4), Some(&Distance::Finite(20)));
//!
//! let mut expected_network: Network<usize, Distance<u16>, ()> = Network::new();
//!
//! expected_network.add_nodes([
//!     (0, Distance::Finite(0)),
//!     (1, Distance::Finite(7)),
//!     (2, Distance::Finite(9)),
//!     (3, Distance::Finite(20)),
//!     (4, Distance::Finite(20)),
//!     (5, Distance::Finite(11)),
//! ]);
//!
//! expected_network.add_arcs([
//!     (1, 0),
//!     (2, 0),
//!     (3, 2),
//!     (5, 2),
//!     (4, 5),
//! ]);
//!
//! assert_eq!(shortest_path_tree, expected_network);
//! ```

pub mod algorithms;
pub mod arc_storage;
pub mod datasets;
pub mod node_storage;
pub mod search;

mod arc_info;
use std::{
    collections::{HashMap, HashSet},
    fmt::Display,
    hash::Hash,
    marker::PhantomData,
    ops::Index,
};

pub use arc_storage::{ArcStorage, HashMapStorage};
use search::{BfsIter, DfsIter, Direction};

use crate::{
    algorithms::{Cyclic, topological_sorting},
    node_storage::NodeStorage,
};

pub use self::arc_info::ArcInfo;

/// A representation of a network with node and arc attributes
pub struct Network<
    I,
    NodeAttr,
    ArcAttr,
    NodeStore = HashMap<I, NodeAttr>,
    ArcStore = HashMapStorage<I, ArcAttr>,
> where
    NodeStore: NodeStorage<I, NodeAttr>,
    ArcStore: ArcStorage<I, ArcAttr>,
{
    _phantom_aa: PhantomData<ArcAttr>,
    _phantom_na: PhantomData<NodeAttr>,
    _phantom_i: PhantomData<I>,
    nodes: NodeStore,
    arc_store: ArcStore,
}

impl<I, NodeAttr, ArcAttr, NodeStore, ArcStore> Clone
    for Network<I, NodeAttr, ArcAttr, NodeStore, ArcStore>
where
    NodeStore: NodeStorage<I, NodeAttr> + Clone,
    ArcStore: ArcStorage<I, ArcAttr> + Clone,
    ArcAttr: Clone,
    NodeAttr: Clone,
{
    fn clone(&self) -> Self {
        Self {
            _phantom_aa: self._phantom_aa,
            _phantom_na: self._phantom_na,
            _phantom_i: PhantomData,
            nodes: self.nodes.clone(),
            arc_store: self.arc_store.clone(),
        }
    }
}

impl<I, NodeAttr, ArcAttr, NodeStore, ArcStore> PartialEq
    for Network<I, NodeAttr, ArcAttr, NodeStore, ArcStore>
where
    NodeStore: NodeStorage<I, NodeAttr> + PartialEq,
    ArcStore: ArcStorage<I, ArcAttr> + PartialEq,
    ArcAttr: PartialEq,
    NodeAttr: PartialEq,
{
    fn eq(&self, other: &Self) -> bool {
        self.nodes == other.nodes && self.arc_store == other.arc_store
    }
}

impl<I, NA, AA, NodeStore, ArcStore> Default for Network<I, NA, AA, NodeStore, ArcStore>
where
    NodeStore: NodeStorage<I, NA> + Default,
    ArcStore: ArcStorage<I, AA> + Default,
{
    fn default() -> Self {
        Self {
            _phantom_aa: PhantomData,
            _phantom_na: PhantomData,
            _phantom_i: PhantomData,
            nodes: Default::default(),
            arc_store: Default::default(),
        }
    }
}

impl<I, NA, AA, NodeStore, ArcStore> std::fmt::Debug for Network<I, NA, AA, NodeStore, ArcStore>
where
    NodeStore: NodeStorage<I, NA> + std::fmt::Debug,
    ArcStore: ArcStorage<I, AA> + std::fmt::Debug,
{
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        f.debug_struct("Network")
            .field("nodes", &self.nodes)
            .field("arc_store", &self.arc_store)
            .finish()
    }
}

impl<I, NA, AA, NodeStore, ArcStore> Network<I, NA, AA, NodeStore, ArcStore>
where
    NodeStore: NodeStorage<I, NA> + Default,
    ArcStore: ArcStorage<I, AA> + Default,
{
    /// Create a new, empty network.
    #[must_use]
    pub fn new() -> Self {
        Self::default()
    }
}

impl<I, NodeAttr, ArcAttr, NodeStore, ArcStore> Network<I, NodeAttr, ArcAttr, NodeStore, ArcStore>
where
    NodeStore: NodeStorage<I, NodeAttr>,
    ArcStore: ArcStorage<I, ArcAttr>,
{
}

impl<I, NodeAttr, ArcAttr, NodeStore, ArcStore> Network<I, NodeAttr, ArcAttr, NodeStore, ArcStore>
where
    NodeStore: NodeStorage<I, NodeAttr>,
    ArcStore: ArcStorage<I, ArcAttr>,
{
    /// Get a reference to the network's arc store.
    #[must_use]
    pub fn arc_store(&self) -> &ArcStore {
        &self.arc_store
    }

    /// Return the number of nodes in the network.
    pub fn n_nodes(&self) -> usize {
        self.nodes.n_nodes()
    }

    /// Add a node to the network.
    ///
    /// This will return the node attributes for a replaced node.
    pub fn add_node(&mut self, id: I, attributes: NodeAttr) -> Option<NodeAttr> {
        self.nodes.add_node(id, attributes)
    }

    /// Convert the network into it's constituent parts.
    pub fn into_parts(self) -> (NodeStore, ArcStore) {
        (self.nodes, self.arc_store)
    }

    /// Create a [`Network`] from node and arc storage.
    pub fn from_parts(nodes: NodeStore, arc_store: ArcStore) -> Self {
        Self {
            _phantom_na: PhantomData,
            _phantom_aa: PhantomData,
            _phantom_i: PhantomData,
            nodes,
            arc_store,
        }
    }

    /// Add nodes from an iterator.
    pub fn add_nodes<T: IntoIterator<Item = (I, NodeAttr)>>(&mut self, from: T) {
        from.into_iter().for_each(|(id, attr)| {
            self.add_node(id, attr);
        });
    }

    /// Remove a node.
    ///
    /// If the node is a part of an arc, the arc will be removed as well.
    pub fn remove_node(&mut self, id: &I) -> Option<NodeAttr> {
        self.arc_store.remove_arcs_with_node(id);
        self.nodes.remove_node(id)
    }

    /// Test if a given node id is within the network
    pub fn contains_node(&self, id: &I) -> bool {
        self.nodes.contains_node(id)
    }

    /// Access a particular node's attributes.
    pub fn node(&self, id: &I) -> Option<&NodeAttr> {
        self.nodes.node(id)
    }

    /// Access a particular node's attributes, mutibly.
    pub fn node_mut(&mut self, id: &I) -> Option<&mut NodeAttr> {
        self.nodes.node_mut(id)
    }

    /// Return an iterator through the nodes and their attributes
    pub fn iter_nodes(&self) -> impl Iterator<Item = (&I, &NodeAttr)> {
        self.nodes.iter_nodes()
    }

    /// Return an iterator that performs a breadth first search of the network starting from
    /// `start_id`.
    pub fn bfs<'a>(
        &'a self,
        start_id: &'a I,
        direction: Direction,
    ) -> BfsIter<'a, I, ArcAttr, ArcStore> {
        BfsIter::new(&self.arc_store, start_id, direction)
    }

    /// Return an iterator that performs a depth first search of the network starting from
    /// `start_id`.
    pub fn dfs<'a>(
        &'a self,
        start_id: &'a I,
        direction: Direction,
    ) -> DfsIter<'a, I, ArcAttr, ArcStore> {
        DfsIter::new(&self.arc_store, start_id, direction)
    }

    /// Consume this network and transform it's nodes with a Fn.
    pub fn map_nodes<F, NewNodeAttr, NewNodeStore>(
        self,
        f: F,
    ) -> Network<I, NewNodeAttr, ArcAttr, NewNodeStore, ArcStore>
    where
        F: Fn((I, NodeAttr)) -> (I, NewNodeAttr),
        NewNodeStore: NodeStorage<I, NewNodeAttr> + std::iter::FromIterator<(I, NewNodeAttr)>,
        NodeStore: IntoIterator<Item = (I, NodeAttr)>,
    {
        Network::from_parts(self.nodes.into_iter().map(f).collect(), self.arc_store)
    }

    /// Consume this network and transform it's arcs with a Fn.
    pub fn map_arcs<F, NewArcAttr, NewArcStore>(
        self,
        f: F,
    ) -> Network<I, NodeAttr, NewArcAttr, NodeStore, NewArcStore>
    where
        F: Fn(ArcInfo<I, ArcAttr>) -> ArcInfo<I, NewArcAttr>,
        NewArcStore: ArcStorage<I, NewArcAttr> + FromIterator<ArcInfo<I, NewArcAttr>>,
        ArcStore: IntoIterator<Item = ArcInfo<I, ArcAttr>>,
    {
        Network::from_parts(self.nodes, self.arc_store.into_iter().map(f).collect())
    }

    /// Consume a network and transform it's nodes and arcs with Fns.
    pub fn map_nodes_and_arcs<FN, FA, NewNodeAttr, NewArcAttr, NewNodeStore, NewArcStore>(
        self,
        f_nodes: FN,
        f_arcs: FA,
    ) -> Network<I, NewNodeAttr, NewArcAttr, NewNodeStore, NewArcStore>
    where
        FN: Fn((I, NodeAttr)) -> (I, NewNodeAttr),
        FA: Fn(ArcInfo<I, ArcAttr>) -> ArcInfo<I, NewArcAttr>,
        NodeStore: IntoIterator<Item = (I, NodeAttr)>,
        ArcStore: IntoIterator<Item = ArcInfo<I, ArcAttr>>,
        NewNodeStore: NodeStorage<I, NewNodeAttr> + std::iter::FromIterator<(I, NewNodeAttr)>,
        NewArcStore: ArcStorage<I, NewArcAttr> + FromIterator<ArcInfo<I, NewArcAttr>>,
    {
        Network::from_parts(
            self.nodes.into_iter().map(f_nodes).collect(),
            self.arc_store.into_iter().map(f_arcs).collect(),
        )
    }

    /// Return a topological sorting of the indices for this network
    ///
    /// # Errors
    /// If the network has a cycle this will return `Err(Cyclic)`.
    pub fn topological_sorting(&self) -> Result<Vec<I>, Cyclic>
    where
        I: Eq + Hash + Clone,
    {
        topological_sorting(self)
    }

    /// Calculate the generations from this network
    ///
    /// # Example
    /// For the network:
    /// ```text
    ///           ┌───┐
    ///           │ 8 │
    ///           └───┘
    ///             │
    ///             │
    ///             ▼
    /// ┌───┐     ┌───┐
    /// │ 9 │ ──▶ │ 0 │
    /// └───┘     └───┘
    ///             │
    ///             │
    ///             ▼
    /// ┌───┐     ┌───┐     ┌───┐
    /// │ 5 │ ◀── │ 1 │ ──▶ │ 6 │
    /// └───┘     └───┘     └───┘
    ///   │         │         │
    ///   │         │         │
    ///   │         ▼         ▼
    ///   │       ┌───┐     ┌───┐
    ///   │       │ 2 │     │ 7 │
    ///   │       └───┘     └───┘
    ///   │         │         │
    ///   │         │         │
    ///   │         ▼         │
    ///   │       ┌───┐       │
    ///   └─────▶ │ 3 │       │
    ///           └───┘       │
    ///             │         │
    ///             │         │
    ///             ▼         │
    ///           ┌───┐       │
    ///           │ 4 │ ◀─────┘
    ///           └───┘
    /// ```
    /// ```
    /// use spokes::*;
    /// let mut net: Network<usize, (), ()> = Network::new();
    ///
    /// net.add_nodes((0..10).map(|i| (i, ())));
    /// net.add_arcs([
    ///     (9, 0),
    ///     (8, 0),
    ///     (0, 1),
    ///     (1, 5),
    ///     (1, 6),
    ///     (1, 2),
    ///     (6, 7),
    ///     (2, 3),
    ///     (5, 3),
    ///     (3, 4),
    ///     (7, 4),
    /// ]);
    ///
    /// let layers = net.generations()
    ///     .unwrap()
    ///     .into_iter()
    ///     .map(|x| {
    ///             let mut xs = x.into_iter().copied().collect::<Vec<usize>>();
    ///             xs.sort();
    ///             xs
    ///     })
    ///     .collect::<Vec<Vec<usize>>>();
    /// assert_eq!(
    ///     layers,
    ///     [
    ///         vec![8, 9],
    ///         vec![0],
    ///         vec![1],
    ///         vec![2, 5, 6],
    ///         vec![3, 7],
    ///         vec![4],
    ///     ]
    /// );
    /// ```
    ///
    /// # Errors
    /// If there is a cycle in the given network, this will return `Err(Cyclic)`.
    ///
    /// # Panics
    /// This will panic if the `ArcStore` is broken.
    pub fn generations(&self) -> Result<Vec<HashSet<&I>>, Cyclic>
    where
        I: Eq + Hash,
    {
        let mut generations: Vec<HashSet<&I>> = vec![];

        let mut indegrees = HashMap::new();
        let mut zero_indegrees = HashSet::new();

        self.nodes.iter_nodes().for_each(|(i, _attributes)| {
            let indegree = self.reverse_arcs(i).count();
            if indegree > 0 {
                indegrees.insert(i, indegree);
            } else {
                zero_indegrees.insert(i);
            }
        });

        while !zero_indegrees.is_empty() {
            let this_generation = std::mem::take(&mut zero_indegrees);
            for node in &this_generation {
                self.forward_arcs(node).for_each(|arc| {
                    let child_indegrees = indegrees
                        .get_mut(arc.head())
                        .expect("Child should be in the indegrees map");
                    *child_indegrees -= 1;

                    if *child_indegrees == 0 {
                        zero_indegrees.insert(arc.head());
                        indegrees.remove(arc.head());
                    }
                });
            }
            generations.push(this_generation);
        }

        if indegrees.is_empty() {
            Ok(generations)
        } else {
            Err(Cyclic)
        }
    }

    /// Return the number of arcs in this network
    pub fn m_arcs(&self) -> usize {
        self.arc_store.m_arcs()
    }

    /// Add an arc to the network.
    ///
    /// # Errors
    /// If the given arc refers to a missing node, an `Err(NoSuchNode)` is returned.
    pub fn add_arc<T: Into<ArcInfo<I, ArcAttr>>>(&mut self, arc: T) -> Result<(), NoSuchNode<I>> {
        let arc = arc.into();

        if !self.contains_node(&arc.tail) {
            Err(NoSuchNode(arc.tail))
        } else if !self.contains_node(&arc.head) {
            Err(NoSuchNode(arc.head))
        } else {
            self.arc_store.add_arc(arc);
            Ok(())
        }
    }

    /// Add multiple arcs to this network
    ///
    /// # Errors
    /// If an arc is encountered which refers to a non-existant node, this will return an
    /// `Err(NoSuchNode)`.
    pub fn add_arcs<T: Into<ArcInfo<I, ArcAttr>>, It: IntoIterator<Item = T>>(
        &mut self,
        iter: It,
    ) -> Result<(), NoSuchNode<I>> {
        for arc in iter {
            self.add_arc(arc)?;
        }
        Ok(())
    }

    /// Remove an arc from the network
    pub fn remove_arc(&mut self, tail: &I, head: &I) -> Option<ArcAttr> {
        self.arc_store.remove_arc(tail, head)
    }

    /// Remove multiple arcs from the network
    pub fn remove_arcs<'a, It>(&'a mut self, iter: It)
    where
        It: IntoIterator<Item = (&'a I, &'a I)>,
    {
        for (tail, head) in iter {
            self.arc_store.remove_arc(tail, head);
        }
    }

    /// Return an iterator of  references to arcs within this network
    pub fn arc_iter<'a>(&'a self) -> impl Iterator<Item = &'a ArcInfo<I, ArcAttr>> + 'a
    where
        ArcAttr: 'a,
        I: 'a,
    {
        self.arc_store.arc_iter()
    }

    /// Return an iterator of mutable references to arcs within this network
    pub fn arc_iter_mut<'a>(&'a mut self) -> impl Iterator<Item = &'a mut ArcInfo<I, ArcAttr>> + 'a
    where
        ArcAttr: 'a,
        I: 'a,
    {
        self.arc_store.arc_iter_mut()
    }

    /// Iterate over arcs originating from the given node.
    pub fn forward_arcs<'a>(
        &'a self,
        node: &'a I,
    ) -> impl Iterator<Item = &'a ArcInfo<I, ArcAttr>> + 'a
    where
        ArcAttr: 'a,
        I: 'a,
    {
        self.arc_store.forward_arcs(node)
    }

    /// Iterate over arcs terminating at the given node.
    pub fn reverse_arcs<'a>(
        &'a self,
        node: &'a I,
    ) -> impl Iterator<Item = &'a ArcInfo<I, ArcAttr>> + 'a
    where
        ArcAttr: 'a,
        I: 'a,
    {
        self.arc_store.reverse_arcs(node)
    }

    /// get a reference to an arc.
    pub fn arc(&self, tail: I, head: I) -> Option<&ArcAttr> {
        self.arc_store.arc(tail, head)
    }

    /// Get a mutable refernce to an arc
    pub fn arc_mut(&mut self, tail: I, head: I) -> Option<&mut ArcAttr> {
        self.arc_store.arc_mut(tail, head)
    }

    /// Check if an arc exists
    pub fn contains_arc(&self, tail: I, head: I) -> bool {
        self.arc_store.contains_arc(tail, head)
    }

    /// Check if there are arcs originating from this node.
    pub fn has_forward_arcs(&self, node: &I) -> bool {
        self.arc_store.has_forward_arcs(node)
    }

    /// Check if there are arcs terminating at this node.
    pub fn has_reverse_arcs(&self, node: &I) -> bool {
        self.arc_store.has_reverse_arcs(node)
    }
}

/// Error value when attempting to reference a node that does not exist in the network.
#[derive(Debug)]
pub struct NoSuchNode<I>(I);

impl<I> Display for NoSuchNode<I>
where
    I: Display,
{
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "No node corresponds to id '{0}'", self.0)
    }
}

/// Temporary structure used to access a network's nodes
pub struct NodeAccessor<'a, I, NodeAttr, ArcAttr, NodeStore, ArcStore>
where
    ArcStore: ArcStorage<I, ArcAttr>,
    NodeStore: NodeStorage<I, NodeAttr>,
{
    network: &'a Network<I, NodeAttr, ArcAttr, NodeStore, ArcStore>,
}

impl<I, NodeAttr, ArcAttr, NodeStore, ArcStore> Index<&I>
    for NodeAccessor<'_, I, NodeAttr, ArcAttr, NodeStore, ArcStore>
where
    ArcStore: ArcStorage<I, ArcAttr>,
    NodeStore: NodeStorage<I, NodeAttr>,
{
    type Output = NodeAttr;

    fn index(&self, index: &I) -> &Self::Output {
        self.network.nodes.node(index).unwrap()
    }
}