graph_generators/
lib.rs

1extern crate rand;
2
3use rand::{Rng};
4
5pub struct Graph {
6    pub nodes: Vec<usize>,
7    pub edges: Vec<(usize, usize)>,
8}
9
10impl Graph {
11    pub fn new() -> Graph {
12        Graph {
13            nodes: Vec::new(),
14            edges: Vec::new(),
15        }
16    }
17
18    pub fn add_node(&mut self) -> usize {
19        let node_id = self.nodes.len();
20        self.nodes.push(node_id);
21        node_id
22    }
23
24    pub fn add_edge(&mut self, edge: (usize, usize)) {
25        match edge {
26            (src, dst) => {
27                assert!(src < self.nodes.len());
28                assert!(dst < self.nodes.len());
29                self.edges.push(edge);
30            }
31        }
32    }
33
34    pub fn node_count(&self) -> usize { self.nodes.len() }
35    pub fn edge_count(&self) -> usize { self.edges.len() }
36}
37
38
39/// Generate a random, scale-free graph according to the
40/// Barabási–Albert preferential attachment model.
41///
42/// rng: Random number generator to use.
43/// n: Total number of nodes.
44/// m: Number of edges to existing nodes for each newly added node.
45///
46/// TODO: Allow generation of undirected graphs.
47///
48pub fn barabasi_albert_graph<R:Rng>(rng: &mut R, n: usize, m: usize) -> Graph {
49    assert!(n > m);
50    assert!(m >= 1);
51
52    let mut g = Graph::new();
53
54    let mut repeated_nodes = Vec::new();
55    let mut targets = Vec::new();
56
57    // create m initial nodes.
58    for _ in 0..m {
59        targets.push(g.add_node());
60    }
61
62    for _ in m..n {
63        // Invariant.
64        assert!(targets.len() == m);
65
66        let node = g.add_node();
67
68        // from new node, draw `m` connections to the `targets`.
69        for &target in &targets[..] {
70            g.add_edge((node, target));
71            repeated_nodes.push(target);
72            repeated_nodes.push(node);
73        }
74
75        // select `m` nodes randomly as new targets for next round.
76        targets = rand::sample(rng, repeated_nodes.iter().cloned(), m);
77    }
78
79    return g;
80}
81
82fn _test_barabasi_albert(n: usize, m: usize) {
83    let mut rng = rand::thread_rng();
84    let g = barabasi_albert_graph(&mut rng, n, m);
85    assert_eq!(n, g.node_count());
86    assert_eq!((n-m)*m, g.edge_count());
87}
88#[test]
89fn test_barabasi_albert() {
90    _test_barabasi_albert(100, 2);
91    _test_barabasi_albert(100, 3);
92    _test_barabasi_albert(200, 5);
93}
graph_generators/lib.rs

graph_generators/
lib.rs
