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

//! Generates a graph using the random attachment model
//!
//! This function is a graph generation model based upon:
//! Callaway, Duncan S., et al. "Are randomly grown graphs really random?."
//! Physical Review E 64.4 (2001): 041902.
//!
//! # Examples
//!
//! ```
//! use raphtory::prelude::*;
//! use raphtory::graphgen::random_attachment::random_attachment;
//! let graph = Graph::new();
//! random_attachment(&graph, 1000, 10, None);
//! ```

use super::next_id;
use crate::{
    db::{
        api::{mutation::AdditionOps, view::*},
        graph::graph::Graph,
    },
    prelude::{NodeStateOps, NO_PROPS},
};
use rand::{rngs::StdRng, seq::SliceRandom, SeedableRng};
use raphtory_api::core::storage::timeindex::AsTime;
use tracing::error;

/// Given a graph this function will add a user defined number of nodes, each with a
/// user defined number of edges.
/// This is an iterative algorithm where at each `step` a node is added and its neighbours
/// are chosen from the pool of nodes already within the network.
/// For this model the neighbours are chosen purely at random. This sampling is done
/// without replacement.
///
/// **Note:**  If the provided graph doesnt have enough nodes/edges for the initial sample,
/// the min number of both will be added before generation begins.
///
/// # Arguments
/// * `graph` - The graph you wish to add nodes and edges to
/// * `nodes_to_add` - The amount of nodes you wish to add to the graph (steps)
/// * `edges_per_step` - The amount of edges a joining node should add to the graph
/// * `seed` - (Optional) An array of u8 bytes to be used as the input seed, Default None
/// # Examples
///
/// ```
/// use raphtory::prelude::*;
/// use raphtory::graphgen::random_attachment::random_attachment;
/// let graph = Graph::new();
/// random_attachment(&graph, 1000, 10, None);
/// ```
pub fn random_attachment(
    graph: &Graph,
    nodes_to_add: usize,
    edges_per_step: usize,
    seed: Option<[u8; 32]>,
) {
    let mut rng: StdRng;
    if let Some(seed_value) = seed {
        rng = StdRng::from_seed(seed_value);
    } else {
        rng = StdRng::from_entropy();
    }
    let mut latest_time = graph.latest_time().map_or(0, |t| t.t());
    let mut ids = graph.nodes().id().iter_values().collect::<Vec<_>>();
    let mut max_id = next_id(graph, ids.iter().max().cloned());

    while ids.len() < edges_per_step {
        max_id = next_id(graph, Some(max_id));
        latest_time += 1;
        graph
            .add_node(latest_time, &max_id, NO_PROPS, None)
            .map_err(|err| error!("{:?}", err))
            .ok();
        ids.push(max_id.clone());
    }

    for _ in 0..nodes_to_add {
        let edges = ids.choose_multiple(&mut rng, edges_per_step);
        max_id = next_id(graph, Some(max_id));
        latest_time += 1;
        edges.for_each(|neighbour| {
            graph
                .add_edge(latest_time, &max_id, neighbour, NO_PROPS, None)
                .expect("Not able to add edge");
        });
        ids.push(max_id.clone());
    }
}

#[cfg(test)]
mod random_graph_test {
    use super::*;
    use crate::graphgen::preferential_attachment::ba_preferential_attachment;
    use raphtory_api::core::utils::logging::global_info_logger;
    #[test]
    fn blank_graph() {
        let graph = Graph::new();
        random_attachment(&graph, 100, 20, None);
        assert_eq!(graph.count_edges(), 2000);
        assert_eq!(graph.count_nodes(), 120);
    }

    #[test]
    fn only_nodes() {
        global_info_logger();
        let graph = Graph::new();
        for i in 0..10 {
            graph
                .add_node(i, i as u64, NO_PROPS, None)
                .map_err(|err| error!("{:?}", err))
                .ok();
        }

        random_attachment(&graph, 1000, 5, None);
        assert_eq!(graph.count_edges(), 5000);
        assert_eq!(graph.count_nodes(), 1010);
    }

    #[test]
    fn prior_graph() {
        let graph = Graph::new();
        ba_preferential_attachment(&graph, 300, 7, None);
        random_attachment(&graph, 4000, 12, None);
        assert_eq!(graph.count_edges(), 50106);
        assert_eq!(graph.count_nodes(), 4307);
    }
}