graphina 0.3.0-alpha.4

A graph data science library for Rust
Documentation 
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

//! Closeness centrality algorithms.
//!
//! This module provides closeness centrality measures.
//!
//! Convention: returns `Result<_, crate::core::error::GraphinaError>` to propagate
//!

use crate::core::error::{GraphinaError, Result};
use crate::core::paths::dijkstra;
use crate::core::types::{BaseGraph, GraphConstructor, NodeMap};

/// Compute closeness centrality for all nodes.
pub fn closeness_centrality<A, W, Ty>(graph: &BaseGraph<A, W, Ty>) -> Result<NodeMap<f64>>
where
    A: Clone,
    W: Copy
        + std::cmp::PartialOrd
        + std::ops::Add<Output = W>
        + std::ops::Sub<Output = W>
        + From<u8>
        + Ord
        + std::fmt::Debug
        + Into<f64>,
    Ty: GraphConstructor<A, W>,
{
    if graph.node_count() == 0 {
        return Err(GraphinaError::invalid_graph("Empty graph"));
    }

    let mut centralities = NodeMap::new();

    for (node, _) in graph.nodes() {
        let dist_map = dijkstra(graph, node)?;
        let mut sum = 0.0;
        let mut count = 0;
        for (other_node, _) in graph.nodes() {
            if node != other_node {
                if let Some(Some(d)) = dist_map.get(&other_node) {
                    let dist_f64: f64 = (*d).into();
                    if dist_f64 > 0.0 && dist_f64.is_finite() {
                        sum += 1.0 / dist_f64;
                        count += 1;
                    }
                }
            }
        }
        if count > 0 {
            centralities.insert(node, sum);
        } else {
            centralities.insert(node, 0.0);
        }
    }

    Ok(centralities)
}