leiden-rs 0.7.0

High-performance Leiden community detection algorithm for graphs in 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
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

//! Adapter for converting a [`gryf::Graph`] into a [`crate::graph::GraphData`].

use gryf::core::{
    base::NeighborReference,
    id::{IdType, IntegerIdType},
    marker::{Directed, Direction, Undirected},
    GraphBase, GraphRef, Neighbors, VertexSet,
};

use crate::error::Result;
use crate::graph::GraphDataBuilder;

/// Convert a gryf undirected graph into a [`crate::graph::GraphData`].
pub fn from_gryf<V, E, G>(
    graph: &gryf::Graph<V, E, Undirected, G>,
) -> Result<crate::graph::GraphData>
where
    E: Into<f64> + Copy,
    G: GraphBase<VertexId: IntegerIdType, EdgeType = Undirected>
        + Neighbors
        + VertexSet
        + GraphRef<V, E>,
{
    let n = graph.vertex_count();
    let mut builder = GraphDataBuilder::new(n);

    for vertex_id in graph.vertices_by_id() {
        let u = vertex_id.as_usize();
        for neighbor in graph.neighbors_undirected(vertex_id) {
            let v = neighbor.id().as_ref().as_usize();
            if v < u {
                continue;
            }
            let edge_ref = neighbor.edge();
            let weight: f64 = graph
                .edge(edge_ref.as_ref())
                .map(|e| (*e).into())
                .unwrap_or(1.0);

            if !(weight.is_finite() && weight >= 0.0) {
                return Err(crate::error::LeidenError::InvalidEdgeWeight { weight });
            }

            builder.add_edge(u, v, weight)?;
        }
    }

    builder.build()
}

/// Convert a gryf directed graph into a [`crate::graph::GraphData`].
///
/// Iterates out-edges of each vertex so that each directed edge is added
/// exactly once to the CSR representation.
pub fn from_gryf_directed<V, E, G>(
    graph: &gryf::Graph<V, E, Directed, G>,
) -> Result<crate::graph::GraphData>
where
    E: Into<f64> + Copy,
    G: GraphBase<VertexId: IntegerIdType, EdgeType = Directed>
        + Neighbors
        + VertexSet
        + GraphRef<V, E>,
{
    let n = graph.vertex_count();
    let mut builder = GraphDataBuilder::new(n).directed();

    for vertex_id in graph.vertices_by_id() {
        let u = vertex_id.as_usize();
        for neighbor in graph.neighbors_directed(vertex_id, Direction::Outgoing) {
            let v = neighbor.id().as_ref().as_usize();
            let edge_ref = neighbor.edge();
            let weight: f64 = graph
                .edge(edge_ref.as_ref())
                .map(|e| (*e).into())
                .unwrap_or(1.0);

            if !(weight.is_finite() && weight >= 0.0) {
                return Err(crate::error::LeidenError::InvalidEdgeWeight { weight });
            }

            builder.add_edge(u, v, weight)?;
        }
    }

    builder.build()
}