centrality.rs

//  Copyright (C) 2017-2018  The Duniter Project Developers.
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU Affero 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 Affero General Public License for more details.
//
// You should have received a copy of the GNU Affero General Public License
// along with this program.  If not, see <https://www.gnu.org/licenses/>.

//! Provide a trait and implementations to find paths between nodes.

use data::NodeId;
use data::WebOfTrust;
use std::collections::{HashMap, VecDeque};

/// Find paths between 2 nodes of a `WebOfTrust`.
pub trait CentralitiesCalculator<T: WebOfTrust> {
    /// Compute betweenness centrality of all members.
    fn betweenness_centralities(&self, wot: &T) -> Vec<u64>;
    /// Compute stress centrality of all members.
    fn stress_centralities(&self, wot: &T) -> Vec<f64>;
}

/// A new "rusty-er" implementation of `WoT` path finding.
#[derive(Debug, Clone, Copy)]
pub struct UlrikBrandesCentralityCalculator;

impl<T: WebOfTrust> CentralitiesCalculator<T> for UlrikBrandesCentralityCalculator {
    fn betweenness_centralities(&self, wot: &T) -> Vec<u64> {
        let wot_size = wot.size();
        let mut centralities = vec![0.0; wot_size];
        let enabled = wot.get_enabled();

        for s in enabled.clone() {
            let mut stack: Vec<NodeId> = Vec::with_capacity(wot_size);
            let mut p: HashMap<NodeId, Vec<NodeId>> = HashMap::with_capacity(wot_size);
            let mut sigma = vec![0.0; wot_size];
            let mut d: Vec<isize> = vec![-1; wot_size];
            let mut q: VecDeque<NodeId> = VecDeque::with_capacity(wot_size);

            sigma[s.0] = 1.0;
            d[s.0] = 0;
            q.push_back(s);
            while !q.is_empty() {
                let v = q.pop_front().unwrap();
                stack.push(v);
                for w in wot.get_links_source(v).expect("v don't have any source !") {
                    if d[w.0] < 0 {
                        q.push_back(w);
                        d[w.0] = d[v.0] + 1;
                    }
                    if d[w.0] == d[v.0] + 1 {
                        sigma[w.0] = sigma[w.0] + sigma[v.0];
                        if p.contains_key(&w) {
                            p.get_mut(&w).unwrap().push(v);
                        } else {
                            p.insert(w, vec![v]);
                        }
                    }
                }
            }
            let mut gamma = vec![0.0; wot_size];
            while !stack.is_empty() {
                let w = stack.pop().unwrap();
                if p.contains_key(&w) {
                    for v in p.get(&w).expect("Not found w in p !") {
                        if enabled.contains(&w) {
                            gamma[v.0] =
                                gamma[v.0] + ((sigma[v.0] / sigma[w.0]) * (1.0 + gamma[w.0]));
                        } else {
                            gamma[v.0] = gamma[v.0] + ((sigma[v.0] / sigma[w.0]) * gamma[w.0]);
                        }
                    }
                }
                if w != s {
                    centralities[w.0] = centralities[w.0] + gamma[w.0];
                }
            }
        }
        centralities.into_iter().map(|c| c as u64).collect()
    }
    fn stress_centralities(&self, _wot: &T) -> Vec<f64> {
        unimplemented!()
    }
}