cnetworks 0.7.0

//! Internal module containing the main `Network` graph data structure.

use crate::{bfs, cn, Model, Weight};
use rand::distributions::Alphanumeric;
use rand::prelude::{thread_rng, IteratorRandom, Rng};
use rand_seeder::Seeder;
use rand_xoshiro::Xoshiro256Plus;
use std::hash::{Hash, Hasher};
use std::sync::{LockResult, Mutex, MutexGuard, TryLockResult};

/// `Node` is a single vertex in the graph and an element of the adjacency list.
#[derive(Debug, Clone)]
struct Node(cn::IndexMap<usize, f64>);

impl Default for Node {
    /// Creates a new node with no links.
    fn default() -> Self {
        Node(cn::IndexMap::default())
    }
}

/// `Link` is an internal representation of an edge in the graph.
///
/// The targets are **unordered**, and as such `Link(i, j) == Link(j, i)` and `hash(Link(i, j)) ==
/// hash(Link(j, i))`.
#[derive(Debug, Clone)]
pub struct Link(usize, usize);

impl PartialEq for Link {
    fn eq(&self, other: &Link) -> bool {
        (self.0, self.1) == (other.0, other.1) || (self.0, self.1) == (other.1, other.0)
    }
}

impl Eq for Link {}

impl Hash for Link {
    fn hash<H: Hasher>(&self, state: &mut H) {
        // We achieve unordered hash equality by always hashing the LARGER target first.
        if self.0 >= self.1 {
            self.0.hash(state);
            self.1.hash(state);
        } else {
            self.1.hash(state);
            self.0.hash(state);
        }
    }
}

#[test]
fn test_link_eq_hash() {
    let mut set = cn::IndexSet::default();

    assert_eq!(Link(1, 1), Link(1, 1));
    set.insert(Link(1, 1));
    assert!(set.contains(&Link(1, 1)));
    assert!(set.remove(&Link(1, 1)));

    let l1 = Link(1, 2);
    let l2 = Link(2, 1);
    assert_eq!(l1, l2);

    set.insert(l1);
    assert!(set.contains(&l2));
    assert!(set.remove(&l2));
}

/// `Network` is the main graph data structure. Internally it is represented as an [adjacency
/// list](https://en.wikipedia.org/wiki/Adjacency_list) of node objects.
#[derive(Debug)]
pub struct Network {
    /// The internal adjacency list graph representation.
    nodes: cn::VecMap<Node>,

    /// The internal edge list, useful in some situations.
    links: cn::IndexSet<Link>,

    /// The model used to initialize links between nodes.
    pub(crate) model: Model,

    /// The distribution followed by the link weights.
    weight: Weight,

    /// The network's randomness source
    rng: Mutex<Xoshiro256Plus>,

    /// The [`Network::rng`] seed
    seed: String,
}

impl Network {
    /// Creates a new network of given size and desired model with a random seed. Use
    /// [`Model::None`] if you want a network with no pre-established connections.
    ///
    /// Note that this is equivalent to calling [`Network::with_seed()`] with a random alphanumeric
    /// seed of length 64.
    ///
    /// # Examples
    /// Creating a network of chosen model and random link weight:
    /// ```
    /// # use cnetworks::*;
    /// let net = Network::new(10, Model::ER { p: 0.4, whole: true }, Weight::Uniform);
    /// assert!(net.is_whole());
    /// assert_eq!(net.seed().len(), 64);
    /// assert_eq!(net.size(), 10);
    /// println!("{:?}", net);
    /// ```
    /// Creating a network with no links and establishing them "by hand":
    /// ```
    /// # use cnetworks::*;
    /// # use std::error::Error;
    /// # fn main() -> Result<(), Box<dyn Error>> {
    /// let mut net = Network::new(10, Model::None, Weight::Constant { c: 0.25 });
    /// net.link(1, 2)?;
    /// net.link(4, 7)?;
    /// assert!(!net.is_whole());
    /// assert_eq!(net.get_link(1,2)?, Some(0.25));
    /// assert_eq!(net.get_link(4,7)?, Some(0.25));
    /// println!("{:?}", net);
    /// # Ok(())
    /// # }
    /// ```
    pub fn new(size: usize, model: Model, weight: Weight) -> Self {
        Network::with_seed(
            size,
            model,
            weight,
            &thread_rng()
                .sample_iter(&Alphanumeric)
                .take(64)
                .map(char::from)
                .collect::<String>(),
        )
    }

    /// Same as [`Network::new()`], but with a specified `seed` for the internal random number
    /// generator. This makes the network entirely deterministic, allowing full reproducibility
    /// between simulations.
    ///
    /// # Examples
    /// ```
    /// # use cnetworks::*;
    /// let seed = "Boaty McBoatface";
    /// let net1 = Network::with_seed(10, Model::ER { p: 0.75, whole: false, }, Weight::Uniform, seed);
    /// let net2 = Network::with_seed(10, Model::ER { p: 0.75, whole: false, }, Weight::Uniform, seed);
    /// for node in 0..9 {
    /// assert_eq!(net1.links_of(node), net2.links_of(node));
    /// }
    /// ```
    pub fn with_seed(size: usize, model: Model, weight: Weight, seed: &str) -> Self {
        // Check for value correctness
        if let Weight::Constant { c } = weight {
            if c <= 0. || c > 1. {
                panic!("{}", cn::Err::BadWeight(c));
            }
        }
        // Create the actual network
        let mut net = Network {
            model: model.clone(),
            nodes: cn::VecMap::with_capacity(size),
            links: cn::IndexSet::default(),
            weight,
            rng: Mutex::new(Seeder::from(seed).make_rng()),
            seed: seed.to_string(),
        };
        // Fill in the nodes
        for i in 0..size {
            net.nodes.insert(i, Node::default());
        }
        // Initialize links according to the desired model
        match model {
            Model::ER { p, whole } => Model::init_er(&mut net, p, whole),
            Model::BA { m0, m } => Model::init_ba(&mut net, m0, m),
            Model::Custom(_) | Model::None => (),
        }
        net
    }

    // PROPERTIES
    // ----------

    /// Returns the network size, ie. the total number of nodes.
    pub fn size(&self) -> usize {
        self.nodes.len()
    }

    /// Returns the [`Model`] of the network.
    pub fn model(&self) -> &Model {
        &self.model
    }

    /// Sets the model of the network to [`Model::Custom`] variant with the specified string.
    ///
    /// # Examples
    /// ```
    /// # use cnetworks::*;
    /// let mut net = Network::default();
    /// net.set_model("Custom model name!");
    /// assert_eq!(net.model(), &Model::Custom("Custom model name!".to_string()));
    /// ```
    pub fn set_model(&mut self, name: &str) {
        self.model = Model::Custom(name.to_string());
    }

    /// Get the type of link weight.
    pub fn weight(&self) -> &Weight {
        &self.weight
    }

    /// Get the network-local rng thread seed. This is a random alphanumeric string of length 64,
    /// unless explicitly specified during construcion with [`Network::with_seed()`].
    pub fn seed(&self) -> &str {
        &self.seed
    }

    /// Tries to lock the network-local rng thread from it's [`Mutex`]. This is effectively
    /// calling [`Mutex::try_lock`].
    pub fn rng_lock(&self) -> TryLockResult<MutexGuard<Xoshiro256Plus>> {
        self.rng.try_lock()
    }

    /// Returns the network-local rng thread from it's [`Mutex`], borrowing it mutably. This
    /// effectively calling [`Mutex::get_mut`], and thus borrow-checked at compile time.
    pub fn rng(&mut self) -> LockResult<&mut Xoshiro256Plus> {
        self.rng.get_mut()
    }

    /**
    Scrambles the built-in random number generator with a new random seed. Useful for when a cloned
    network needs a different RNG source.

    # Examples
    ```
    # use cnetworks::*;
    # use rand::prelude::*;
    let net = Network::default();
    let mut net2 = net.clone();

    assert_eq!(net.seed(), net2.seed());
    assert_eq!(net.rng_lock().unwrap().next_u32(), net2.rng_lock().unwrap().next_u32());

    net2.scramble_rng();
    assert_ne!(net.seed(), net2.seed());
    assert_ne!(net.rng_lock().unwrap().next_u32(), net2.rng_lock().unwrap().next_u32());
    ```
    */
    pub fn scramble_rng(&mut self) {
        let seed = thread_rng()
            .sample_iter(&Alphanumeric)
            .take(64)
            .map(char::from)
            .collect::<String>();
        self.seed = seed.clone();
        self.rng = Mutex::new(Seeder::from(seed).make_rng());
    }

    /// Returns iterator with the node indexes.
    ///
    /// The iteration order is **deterministic**, but not stable, as it is deterministaically
    /// perturbed when removing links.
    ///
    /// Keep in mind that it's possible to have a network of nodes with non-sequential and
    /// non-ordered indexes, such as `(0,2,3)`, `(100, 101, 150)` or `(10, 0, 1)` using
    /// [`Network::attach`] and [`Network::`detach`].
    pub fn nodes(&self) -> impl cn::Iter<usize> + '_ {
        self.nodes.indexes()
    }

    /// Returns iterator of links in the network as (first index, second index) pairs. This is
    /// intended mostly for explicit iteration over network links, as using [`Network::get_link`]
    /// or [`Network::links_of`] will be faster than [`Iterator::find`] and others.
    ///
    /// The iteration order is **deterministic**, but not stable, as it is deterministaically
    /// perturbed when removing links.
    ///
    /// # Examples
    /// One common use case is counting edges in the graph.
    /// ```
    /// # use cnetworks::*;
    /// let net = Network::new(100, Model::ER { p: 0.05, whole: true }, Weight::default());
    /// println!("Network has a total of {} links", net.links().count());
    /// ```
    pub fn links(&self) -> impl cn::Iter<(usize, usize)> + '_ {
        self.links.iter().map(|l| (l.0, l.1))
    }

    /// Return `true` if a node with specified `index` exists in the network.
    pub fn exists(&self, index: usize) -> bool {
        self.nodes.contains(index)
    }

    /// Returns `true` if the network is whole, ie. if there is only one component or if the
    /// network is empty.
    pub fn is_whole(&self) -> bool {
        // Empty network is considered whole
        if self.size() == 0 {
            true
        } else {
            // We only need to check if every node is reachable from the first one
            // (and we know there is a first one)
            self.size()
                == bfs::reach_many(
                    self,
                    self.nodes().next().unwrap(),
                    &self.nodes().collect::<Vec<_>>(),
                )
                .unwrap_or_default()
                .len()
        }
    }

    /// Returns the degree of a given `node`, ie. the number of it's closest neighbors.
    ///
    /// Returns [`cn::Err::NoSuchNode`] if specified node does not exist.
    pub fn deg_of(&self, node: usize) -> cn::Result<usize> {
        Ok(self.links_of(node)?.len())
    }

    /// Returns links of a given `node` as [`cn::IndexMap`] of `(target, weight)` pairs.
    ///
    /// Returns [`cn::Err::NoSuchNode`] if specified node does not exist.
    pub fn links_of(&self, node: usize) -> cn::Result<&cn::IndexMap<usize, f64>> {
        match self.nodes.get(node) {
            Some(node) => Ok(&node.0),
            None => Err(cn::Err::NoSuchNode(node)),
        }
    }

    /// Returns the weight of the link between nodes `i` and `j`, `None` if such link does not exist.
    ///
    /// Returns [`cn::Err::LinkToSelf`] if `i` and `j` are the same, [`cn::Err::NoSuchNode`] if
    /// either `i` or `j` does not exist.
    pub fn get_link(&self, i: usize, j: usize) -> cn::Result<Option<f64>> {
        if !self.exists(j) {
            return Err(cn::Err::NoSuchNode(j));
        }
        let link = self.links_of(i)?.get(&j).cloned();
        if i == j {
            return Err(cn::Err::LinkToSelf(i));
        }
        Ok(link)
    }

    /// Returns the number of connected nodes in the network, ie. those for which [`Network::deg_of`] `> 0`.
    pub fn size_connected(&self) -> usize {
        self.nodes()
            .filter(|&node| self.deg_of(node).unwrap() != 0)
            .count()
    }

    /// Returns the arithmetical average of node degrees in the network.
    pub fn deg_avg(&self) -> f64 {
        self.deg_total() as f64 / self.size() as f64
    }

    /// Returns the total degree of the network, ie. sum of degrees over all of the nodes.
    pub fn deg_total(&self) -> usize {
        self.nodes().map(|node| self.deg_of(node).unwrap()).sum()
    }

    /// Returns the histogram of node degrees as a [`cn::VecMap`] of (degree, occurrences) pairs.
    pub fn deg_distr(&self) -> cn::VecMap<usize> {
        let mut bins: cn::VecMap<usize> = cn::VecMap::default();
        for node in self.nodes() {
            let deg = self.deg_of(node).unwrap();
            if let Some(&count) = bins.get(deg) {
                bins.insert(deg, count + 1);
            } else {
                bins.insert(deg, 1);
            }
        }
        bins
    }

    // IN-PLACE MANIPULATION
    // ---------------------

    /// Establishes a link between nodes `i` and `j` using network's weight. Updates the link
    /// weight and returns the old value if it already exist, `None` otherwise.
    ///
    /// Returns [`cn::Err::NoSuchNode`] if `i` and `j` are the same or do not exist.
    pub fn link(&mut self, i: usize, j: usize) -> cn::Result<Option<f64>> {
        let w = match self.weight {
            Weight::Constant { c } => c,
            Weight::Uniform => self.rng().unwrap().gen(),
        };
        self.link_exact(i, j, w)
    }

    /// Establishes a link between nodes `i` and `j` with specified `weight`. Updates the link weight
    /// and returns the old value if it already exist, `None` otherwise.
    ///
    /// Returns [`cn::Err::NoSuchNode`] if `i` and `j` do not exist, [`cn::Err::LinkToSelf`] if they
    /// are the same, [`cn::Err::BadWeight`] the `weight` is not in the range (0, 1].
    pub fn link_exact(&mut self, i: usize, j: usize, weight: f64) -> cn::Result<Option<f64>> {
        // All kinds of input error
        if weight <= 0. || weight > 1. {
            return Err(cn::Err::BadWeight(weight));
        }
        if i == j {
            return Err(cn::Err::LinkToSelf(i));
        }
        match (self.nodes.contains(i), self.nodes.contains(j)) {
            (true, true) => {
                self.links.insert(Link(i, j));
                self.nodes[j].0.insert(i, weight);
                Ok(self.nodes[i].0.insert(j, weight))
            }
            (true, false) => Err(cn::Err::NoSuchNode(j)),
            (false, _) => Err(cn::Err::NoSuchNode(i)),
        }
    }

    /// Unsafely removes a link between nodes `i` and `j`. Does not perform a check whether the
    /// network is still whole. Returns the weight of the removed connection or `None` if the
    /// connection does not exist.
    ///
    /// Returns [`cn::Err::NoSuchNode`] if `i` and `j` do not exist and [`cn::Err::LinkToSelf`] if they
    /// are the same.
    pub fn unlink(&mut self, i: usize, j: usize) -> cn::Result<Option<f64>> {
        if i == j {
            return Err(cn::Err::LinkToSelf(i));
        }
        match (self.nodes.contains(i), self.nodes.contains(j)) {
            (true, true) => {
                self.links.remove(&Link(i, j));
                self.nodes[j].0.remove(&i);
                Ok(self.nodes[i].0.remove(&j))
            }
            (true, false) => Err(cn::Err::NoSuchNode(j)),
            (false, _) => Err(cn::Err::NoSuchNode(i)),
        }
    }

    /// Safely removes a link between nodes `i` and `j`, ensuring the network does not split.
    /// Performs a [breadth-first search](crate::bfs) to check whether the network is still whole.
    /// Returns the weight of removed link, `None` if the link does not exist or cannot be safely
    /// removed.
    ///
    /// Returns [`cn::Err::NoSuchNode`] if `i` and `j` do not exist and [`cn::Err::LinkToSelf`] if they
    /// are the same.
    pub fn unlink_safe(&mut self, i: usize, j: usize) -> cn::Result<Option<f64>> {
        let w = match self.unlink(i, j)? {
            Some(weight) => weight,
            None => return Ok(None),
        };
        if bfs::reach(self, i, j)? {
            Ok(Some(w))
        } else {
            self.link_exact(i, j, w)?;
            Ok(None)
        }
    }

    /// Unsafely disconnects a `node` from the network by removing all of its links. Does not check
    /// if the network is still whole. Returns the removed links as a [`cn::IndexMap`] of (target,
    /// weight) pairs.
    ///
    /// Returns [`cn::Err::NoSuchNode`] if `node` does not exist.
    pub fn disconnect(&mut self, node: usize) -> cn::Result<cn::IndexMap<usize, f64>> {
        if let Some(node_obj) = self.nodes.get_mut(node) {
            let old_links = std::mem::take(&mut node_obj.0);
            for &other in old_links.keys() {
                self.nodes[other].0.remove(&node);
                self.links.remove(&Link(other, node));
            }
            Ok(old_links)
        } else {
            Err(cn::Err::NoSuchNode(node))
        }
    }

    /// Safely disconnects a `node` from the network by removing all of its links. Performs a
    /// [breadth-first search](crate::bfs) to check whether the network is still whole. Returns the
    /// removed links as a [`cn::IndexMap`] of (target, weight) pairs or `None` if `node` cannot be
    /// safely disconnected.
    ///
    /// Returns [`cn::Err::NoSuchNode`] if `node` does not exist.
    pub fn disconnect_safe(&mut self, node: usize) -> cn::Result<Option<cn::IndexMap<usize, f64>>> {
        // Blindly disconnect the requested node
        let links = self.disconnect(node)?;
        // Get a vector of used-to-be-connected nodes
        let link_vec: Vec<_> = links.keys().copied().collect();
        // Check if it's possible to reach all the others from first
        if let Some((first, others)) = link_vec.split_first() {
            if bfs::reach_many(self, *first, others)
                .unwrap_or_default()
                .len()
                != others.len()
            {
                // Not reachable - reestablish links and return None
                for (key, value) in links {
                    self.link_exact(key, node, value)?;
                }
                return Ok(None);
            }
        }
        Ok(Some(links))
    }

    /// Removes **ALL** links in the network.
    ///
    /// Sets the model to [`Model::None`] such that the initial linking process can be conducted
    /// again, eg. with [`Model::init_er`], [`Model::init_ba`] or manually.
    pub fn disconnect_all(&mut self) {
        for node in (&mut self.nodes.as_vec_mut().iter_mut()).flatten() {
            node.0.clear();
        }
        self.links.clear();
        self.model = Model::None;
    }

    /// Attaches a new `node` to the network. The node must be connected to the rest of the network
    /// manually, as no links will be automatically established.
    ///
    /// Returns [`cn::Err::NodeExists`] if there already exists a node with the specified index.
    ///
    /// # Examples
    /// ```
    /// # use cnetworks::*;
    /// let mut net = Network::default();
    /// assert!(net.attach(2).is_ok());
    /// assert!(net.attach(2).is_err());
    /// ```
    pub fn attach(&mut self, node: usize) -> cn::Result<()> {
        if self.exists(node) {
            return Err(cn::Err::NodeExists(node));
        } else {
            self.nodes.insert(node, Node::default());
        }
        Ok(())
    }

    /// Like [`Network::attach`], but attach many nodes skipping over the already-existing ones
    /// instead of raising an error.
    pub fn attach_skip(&mut self, indexes: &[usize]) {
        for &i in indexes {
            if !self.exists(i) {
                self.nodes.insert(i, Node::default());
            }
        }
    }

    /// Completely removes `node` from the network, disconnecting it first.
    ///
    /// Returns [`cn::Err::NoSuchNode`] if node with specified index does not exist.
    ///
    /// # Examples
    /// ```
    /// # use cnetworks::*;
    /// let mut net = Network::default();
    /// assert!(net.detach(2).is_err());
    /// ```
    pub fn detach(&mut self, node: usize) -> cn::Result<()> {
        self.disconnect(node)?;
        self.nodes.remove(node);
        Ok(())
    }

    /// Returns vector of [components](https://en.wikipedia.org/wiki/Component_(graph_theory))
    /// present in the network, ordered largest to smallest.
    ///
    /// # Examples
    /// ```
    /// # use cnetworks::*;
    /// let net = Network::new(100, Model::ER { p: 0.05, whole: false }, Weight::default() );
    /// let components = net.components();
    /// println!("Largest component: {:?}", components.first().expect("No components"));
    /// println!("Smallest component: {:?}", components.last().expect("No components"));
    /// ```
    pub fn components(&self) -> Vec<cn::VecSet> {
        let mut components: Vec<cn::VecSet> = Vec::new();
        if self.size() == 0 {
            return components;
        }
        // Start from a random node
        let root = self.nodes().choose(&mut *self.rng_lock().unwrap()).unwrap();
        let (expl, mut unexpl) = bfs::explore(self, root).unwrap();
        // Add explored to the vector of components
        components.push(expl);
        loop {
            match unexpl.iter().choose(&mut *self.rng_lock().unwrap()) {
                Some(new_root) => {
                    // Establish its component
                    let (cls, _) = bfs::explore(self, new_root).unwrap();
                    // Mark everything in the component as explored
                    for c in cls.iter() {
                        unexpl.remove(c);
                    }
                    components.push(cls);
                }
                // The are no unexplored nodes
                None => {
                    // Order components largest -> smallest
                    components.sort_by_key(|set| -(set.len() as i64));
                    return components;
                }
            }
        }
    }

    /// Transform the network into the largest contained component by removing all nodes **not** in
    /// the largest component. Leaves `self` unchanged if there is no largest component.
    ///
    /// # Examples
    /// ```
    /// # use cnetworks::*;
    /// # use std::error::Error;
    /// # fn main() -> Result<(), Box<dyn Error>> {
    /// let mut net = Network::new(10, Model::None, Weight::default() );
    /// net.link(0, 1)?;
    /// net.link(0, 2)?;
    /// net.link(0, 3)?;
    /// assert_eq!(net.clone().into_largest_component().links().count(), 3);
    /// assert_eq!(net.clone().into_largest_component().size(), 4);
    /// # Ok(())
    /// # }
    /// ```
    pub fn into_largest_component(mut self) -> Self {
        if let Some(largest) = self.components().first() {
            let to_remove: Vec<usize> = self.nodes().filter(|n| !largest.contains(*n)).collect();
            for not_included in to_remove {
                self.nodes.remove(not_included);
            }
        }
        self
    }

    /// Stitches the network together if it is composed of more than one component. Connects random
    /// elements from smaller components to the largest one, extending it until it covers the entire
    /// network.
    ///
    /// # Examples
    /// ```
    /// # use cnetworks::*;
    /// let mut net = Network::new(100, Model::ER { p: 0.0001, whole: false }, Weight::default() );
    /// assert!(!net.is_whole());
    /// assert_ne!(net.components().len(), 1 );
    /// net.stitch_together();
    /// assert!(net.is_whole());
    /// assert_eq!(net.components().len(), 1 );
    /// ```
    pub fn stitch_together(&mut self) {
        let mut components = self.components();
        let (largest, others) = match components.split_first_mut() {
            Some(clst) => clst,
            None => return,
        };
        for component in others {
            // Connect random node from current component to random node from the largest component
            let current = component.iter().choose(&mut *self.rng().unwrap()).unwrap();
            let other = largest.iter().choose(&mut *self.rng().unwrap()).unwrap();
            self.link(current, other).unwrap();
            // Extend the largest component with the just-connected nodes
            for node in component.iter() {
                largest.insert(node);
            }
        }
    }
}

impl Default for Network {
    /// Same as [`Network::new()`] with the following properites:
    ///
    /// - [`Model::None`]
    /// - [`Weight::default()`]
    /// - [`Network::size()`] of 0
    ///
    /// Note that by default the network is empty. Nodes must be manually attached using
    /// [`Network::attach()`] and linked using [`Network::link()`].
    ///
    /// # Examples
    /// Creating a default network and attaching nodes manually
    /// ```
    /// # use cnetworks::*;
    /// # use std::error::Error;
    /// # fn main() -> Result<(), Box<dyn Error>> {
    /// let mut net = Network::default();
    /// assert!(net.is_whole()); // empty network is considered whole
    /// for i in [1,2] {
    ///     net.attach(i)?;
    /// }
    /// net.link(1,2)?;
    /// assert_eq!(net.get_link(1,2), Ok(Some(1.0)));
    /// assert!(net.is_whole());
    /// # Ok(())
    /// # }
    /// ```
    fn default() -> Self {
        Network::new(0, Model::None, Weight::default())
    }
}

impl Clone for Network {
    fn clone(&self) -> Self {
        Network {
            nodes: self.nodes.clone(),
            links: self.links.clone(),
            model: self.model.clone(),
            weight: self.weight.clone(),
            rng: Mutex::new(self.rng.try_lock().unwrap().clone()),
            seed: self.seed.clone(),
        }
    }
}