raphtory 0.17.0

raphtory, a temporal graph library
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
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

use crate::{
    algorithms::layout::NodeVectors,
    db::api::state::{GenericNodeState, TypedNodeState},
    prelude::{GraphViewOps, NodeViewOps},
};
use glam::Vec2;
use quad_rand::RandomRange;
use raphtory_api::core::entities::GID;
use rayon::prelude::*;
use serde::{Deserialize, Serialize};

#[derive(Clone, PartialEq, Serialize, Deserialize, Debug, Default)]
pub struct CoordinateState {
    coordinates: [f32; 2],
}

/// Return the position of the nodes after running Fruchterman Reingold algorithm on the `graph`
pub fn fruchterman_reingold_unbounded<'graph, G: GraphViewOps<'graph>>(
    g: &G,
    iter_count: u64,
    scale: f32,
    node_start_size: f32,
    cooloff_factor: f32,
    dt: f32,
) -> TypedNodeState<'graph, CoordinateState, G> {
    let mut positions = init_positions(g, node_start_size);
    let mut velocities = init_velocities(g);

    for _index in 0..iter_count {
        positions = update_positions(&positions, &mut velocities, g, scale, cooloff_factor, dt);
    }

    let res: Vec<_> = g
        .nodes()
        .par_iter()
        .map(|node| positions.get(&node.id()).unwrap().to_array())
        .collect();

    TypedNodeState::new(GenericNodeState::new_from_eval(g.clone(), res, None))
}

fn update_positions<'graph, G: GraphViewOps<'graph>>(
    old_positions: &NodeVectors,
    velocities: &mut NodeVectors,
    graph: &G,
    scale: f32,
    cooloff_factor: f32,
    dt: f32,
) -> NodeVectors {
    let mut new_positions: NodeVectors = NodeVectors::default();

    for (id, old_position) in old_positions {
        // force that will be applied to the node
        let mut force = Vec2::ZERO;

        force += compute_repulsion(id, scale, old_positions);
        force += compute_attraction(id, scale, old_positions, graph);

        let velocity = velocities.get_mut(id).unwrap();

        *velocity += force * dt;
        *velocity *= cooloff_factor;

        let new_position = *old_position + *velocity * dt;
        new_positions.insert(id.clone(), new_position);
    }
    new_positions
}

fn compute_repulsion(id: &GID, scale: f32, old_positions: &NodeVectors) -> Vec2 {
    let mut force = Vec2::ZERO;
    let position = old_positions.get(id).unwrap();

    for (alt_id, alt_position) in old_positions {
        if alt_id != id {
            force += -((scale * scale) / position.distance(*alt_position))
                * unit_vector(*position, *alt_position);
        }
    }

    force
}

fn compute_attraction<'graph, G: GraphViewOps<'graph>>(
    id: &GID,
    scale: f32,
    old_positions: &NodeVectors,
    graph: &G,
) -> Vec2 {
    let mut force = Vec2::ZERO;
    let node = graph.node(id).unwrap();
    let position = old_positions.get(id).unwrap();

    for alt_node in node.neighbours() {
        let alt_position = old_positions.get(&alt_node.id()).unwrap();
        force += (position.distance_squared(*alt_position) / scale)
            * unit_vector(*position, *alt_position);
    }

    force
}

fn unit_vector(a: Vec2, b: Vec2) -> Vec2 {
    (b - a).normalize_or_zero()
}

fn init_velocities<'graph, G: GraphViewOps<'graph>>(graph: &G) -> NodeVectors {
    graph
        .nodes()
        .iter()
        .map(|node| (node.id(), Vec2::ZERO))
        .collect()
}

fn init_positions<'graph, G: GraphViewOps<'graph>>(graph: &G, node_start_size: f32) -> NodeVectors {
    let half_node_start_width = node_start_size / 2.0;
    graph
        .nodes()
        .iter()
        .map(|node| {
            let position = Vec2::new(
                RandomRange::gen_range(-half_node_start_width, half_node_start_width),
                RandomRange::gen_range(-half_node_start_width, half_node_start_width),
            );
            (node.id(), position)
        })
        .collect()
}