Resolve "impl distance variant of stress centrality algo"

Closes #65 (closed)

wotb/operations/centrality.rs

@@ -25,9 +25,11 @@ pub trait CentralitiesCalculator<T: WebOfTrust> {
     fn betweenness_centralities(&self, wot: &T) -> Vec<u64>;
     /// Compute stress centrality of all members.
     fn stress_centralities(&self, wot: &T) -> Vec<u64>;
+    /// Compute distance stress centrality of all members.
+    fn distance_stress_centralities(&self, wot: &T, step_max: usize) -> Vec<u64>;
 }
 
-/// A new "rusty-er" implementation of `WoT` path finding.
+/// An implementation based on "Ulrik brandes" algo.
 #[derive(Debug, Clone, Copy)]
 pub struct UlrikBrandesCentralityCalculator;
 
@@ -138,4 +140,59 @@ impl<T: WebOfTrust> CentralitiesCalculator<T> for UlrikBrandesCentralityCalculat
         }
         centralities.into_iter().map(|c| c as u64).collect()
     }
+    fn distance_stress_centralities(&self, wot: &T, step_max: usize) -> Vec<u64> {
+        let wot_size = wot.size();
+        let mut centralities = vec![0.0; wot_size];
+        let enabled_nodes = wot.get_enabled();
+
+        // The source of any path belongs to enabled_nodes
+        for s in enabled_nodes.clone() {
+            let mut stack: Vec<NodeId> = Vec::with_capacity(wot_size);
+            let mut paths: 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);
+                if d[v.0] < step_max as isize {
+                    for w in wot.get_links_source(v).expect("v don't have any source !") {
+                        // w found for the first time ?
+                        if d[w.0] < 0 {
+                            q.push_back(w);
+                            d[w.0] = d[v.0] + 1;
+                        }
+                        // Shortest path to w via v
+                        if d[w.0] == d[v.0] + 1 {
+                            sigma[w.0] += sigma[v.0];
+                            paths.entry(w).or_insert_with(Vec::new).push(v);
+                        }
+                    }
+                }
+            }
+            let mut delta = vec![0.0; wot_size];
+            // stack returns vertices in order of non-increasing distance from s
+            while !stack.is_empty() {
+                let w = stack.pop().unwrap();
+                if paths.contains_key(&w) {
+                    for v in paths.get(&w).expect("Not found w in p !") {
+                        if enabled_nodes.contains(&w) {
+                            delta[v.0] += sigma[v.0] * (1.0 + (delta[w.0] / sigma[w.0]));
+                        } else {
+                            // If w not in enabled_nodes, no path can end at w
+                            delta[v.0] += sigma[v.0] * (delta[w.0] / sigma[w.0]);
+                        }
+                    }
+                }
+                if w != s {
+                    centralities[w.0] += delta[w.0];
+                }
+            }
+        }
+        centralities.into_iter().map(|c| c as u64).collect()
+    }
 }