1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138

extern crate queues;

use queues::*;
use rand::prelude::*;
use std::collections::HashSet;

use super::Network;
use super::enums::Error;

/// Perform a breadth-first search over the network, starting with root and looking for target.
/// Return a HashSet of all nodes discovered in the process or `None` if the path is not found.
/// Returns `Err` if the root or target nodes do not exist. Panics if the network is corrupted or
/// when the queue operations fail.
/// # Examples
/// ```
/// use cnetworks::*;
/// let net = Network::new(100, Model::ER { p: 0.05, whole: false }, Weight::Constant { c: 1.0});
/// match bfs(&net, 1, 3).expect("Node 1 or 3 does not exist") {
///     Some(n) => println!("Found 3 after discovering {:?}", n),
///     None => println!("No path to 3 found!"),
/// }
/// ```
pub fn bfs(net: &Network, root: usize, target: usize) -> Result<Option<HashSet<usize>>, Error> {
    // Check if the target is valid
    if let None = net.nodes.get(target) {
        return Err(Error::NoSuchNode { idx : target });
    }
    if let None = net.nodes.get(root) {
        return Err(Error::NoSuchNode { idx : root });
    }
    let mut discovered: HashSet<usize> = HashSet::new();
    let mut to_visit: Queue<usize> = Queue::new();
    discovered.insert(root);
    to_visit.add(root).expect("Queue error");
    // Search the network breadth-first
    while to_visit.size() != 0 {
        let current = to_visit.remove().expect("Queue error");
        // Exit condition
        if current == target {
            return Ok(Some(discovered));
        }
        for &i in net.nodes[current].links.keys() {
            if !discovered.contains(&i) {
                discovered.insert(i);
                to_visit.add(i).expect("Queue error");
            }
        }
    }
    // No path from root to target was found
    Ok(None)
}

/// Explore the network with BFS starting with `root`. Return a tuple of two HashSets: one with the
/// explored nodes (including the root) and another with the unexplored. Returns `Err` if the root
/// does not exist. Panics when the network is corrupted or if the queue operations fail.
/// # Examples
/// ```
/// use cnetworks::*;
/// let net = Network::new(100, Model::ER { p: 0.05, whole: false }, Weight::Constant { c: 1.0});
/// let (exp, unexp) = explore(&net, 1).expect("Node 1 does not exist");
/// println!("Available from 1: {:?}", exp);
/// println!("Unavailable from 1: {:?}", unexp);
/// ```
pub fn explore(net: &Network, root: usize) -> Result<(HashSet<usize>, HashSet<usize>), Error> {
    if let None = net.nodes.get(root) {
        return Err(Error::NoSuchNode { idx : root });
    }
    let mut discovered: HashSet<usize> = HashSet::new();
    let mut to_visit: Queue<usize> = Queue::new();
    discovered.insert(root);
    to_visit.add(root).expect("Queue error");
    // Explore the network just like BFS but without specified target
    while to_visit.size() != 0 {
        let current = to_visit.remove().expect("Queue error");
        for &i in net.nodes[current].links.keys() {
            if !discovered.contains(&i) {
                discovered.insert(i);
                to_visit.add(i).expect("Queue error");
            }
        }
    }
    // Gather the undiscovered nodes
    let mut undiscovered: HashSet<usize> = HashSet::new();
    for node in &net.nodes {
        if !discovered.contains(&node.index) {
            undiscovered.insert(node.index);
        }
    }
    Ok((discovered, undiscovered))
}


/// Stitch the network together if it is not whole.
///
/// Connects random elements of smaller clusters to the largest cluster, extending it until it
/// covers the entire network, making the network "whole".
pub fn stitch_together(net: &mut Network) {
    let mut rng = rand::thread_rng();
    // Get the clusters
    let clusters = net.clusters();
    let mut largest = clusters.first().expect("Empty largest cluster").clone();
    for cluster in &clusters[1..] {
        // Connect random node from current cluster to random node from the largest cluster
        let &current = cluster.iter().choose(&mut rng).expect("Empty cluster");
        let &other = largest.iter().choose(&mut rng).expect("Empty largest cluster");
        net.link(current, other).expect("Malformed network");
        // Extend the largest cluster with the just-connected nodes
        largest.extend(cluster.iter());
    }
}

/// Simulate spread of information according to the **susceptible-infected** diffusion model.
///
/// On each time step the nodes for which the `infected` flag is `true` will try to infect
/// their closest neighbors with probability given by connection strength, setting their
/// `infected` flag to `true`.
///
/// Returns the root of the infection.
pub fn spread_si(net: &mut Network, steps: usize) -> usize {
    // Choose random node as origin
    let mut rng = rand::thread_rng();
    let root = net.nodes.choose(&mut rng).expect("Empty network").index;
    net.nodes[root].infected = true;
    for _ in 0..steps {
        // Iterate over the copy of nodes as to not jump start infections
        for node in net.nodes.clone() {
            if node.infected {
                // Try to infect the neighbors
                for (target, weight) in node.links {
                    if rng.gen::<f64>() < weight {
                        net.nodes[target].infected = true;
                    }
                }
            }
        }
    }
    root
}