icentral-test-insertion 0.1.0

Efficiently insert edges into graphs to evaluate betweenness centrality using advanced hash methodologies.
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
129
130
131

crate::ix!();

pub fn insertion_test_fuad_hash(
    graph:               &mut Graph<GraphHash>,
    num_edges_to_insert: i32) 
-> Result<(),BetweennessCentralityError> 
{
    graph.print_header();

    let mut gh = GraphHash::new_from_graph_ref(
        &*graph, 
        "insertion_test_fuad_hash::graph"
    );

    let mut brandes_time = Duration::from_secs(0);

    let mut tm: Timer = default!();

    let num_iter: usize = gh.num_nodes();

    debug!("Brandes runtime: ");

    tm.start();

    let scores = brandes_bc_hash(&mut gh, None)?;

    tm.stop();

    brandes_time = tm.interval();

    debug!("{:?}", brandes_time);

    debug!("Brandes avg iter time: {:?}", brandes_time / num_iter as u32);

    let mut rand_edge_vec: Vec::<Edge> = vec![];

    debug!("Generating edges...");

    let mut rng = WyRand::default();

    for i in 0..num_edges_to_insert {

        let mut rand_edge: Edge = Edge::default();

        let mut src: NodeId = NodeId::default();
        let mut dst: NodeId = NodeId::default();

        loop {

            let len = graph.num_nodes();

            src = nodeid![rng.generate::<usize>() % len];
            dst = nodeid![rng.generate::<usize>() % len];

            rand_edge.src = src;
            rand_edge.dst = dst;

            if !graph.has_edge(&rand_edge) 
            || rand_edge_vec.iter().find(|x| **x == rand_edge).is_some() {
                break;
            }
        }

        rand_edge_vec.push(rand_edge);
    }

    let mut tot_fuad_time = Duration::from_secs(0);
    let mut tot_speedup:   f64 = 0.0;

    let mut bcc_stat_vec: Vec::<BiconnectedComponentsStat> = vec![];

    for i in 0..rand_edge_vec.len() {

        let mut bcc_stat: BiconnectedComponentsStat = default!();

        let rand_edge: Edge = rand_edge_vec[i];

        debug!(
            "Inserting edge ({}, {}) and updating bc...", 
            rand_edge.src, 
            rand_edge.dst
        );

        tm.start();

        graph.insert_edge_update_bc_experimental(
            &rand_edge, 
            &mut bcc_stat,
            None,
            None,
        );

        tm.stop();

        let mut avg_iter_time_naive = Duration::from_secs(0);

        graph.approx_bcc_iter_tm(
            rand_edge.src, 
            rand_edge.dst, 
            &mut avg_iter_time_naive,
            None,
        );

        tot_fuad_time += tm.interval();

        tot_speedup += brandes_time.div_duration_f64(tm.interval());

        debug!("BiconnectedComponents num nodes:  {}",    bcc_stat.bcc_num_nodes);
        debug!("BiconnectedComponents num edges:  {}",    bcc_stat.bcc_num_edges);
        debug!("Time to update BC:                {:?}",  tm.interval());
        debug!("Speedup:                          {:?}",  brandes_time.div_duration_f64(tm.interval()));
        debug!("BiconnectedComponents num d0 BFS: {}",    bcc_stat.num_d0_iter);
        debug!("BiconnectedComponents d0 time:    {:?}",  bcc_stat.tot_d0_tm / bcc_stat.num_d0_iter as u32);
        debug!("BiconnectedComponents num d1 BFS: {}",    bcc_stat.num_d1_iter);
        debug!("BiconnectedComponents d1 time:    {:?}",  bcc_stat.tot_d1_tm / bcc_stat.num_d1_iter as u32);
        debug!("BiconnectedComponents num d2 BFS: {}",    bcc_stat.num_d2_iter);
        debug!("BiconnectedComponents d2 time:    {:?}",  bcc_stat.tot_d2_tm / bcc_stat.num_d2_iter as u32);
        debug!("avg iter time naive:              {:?}",  avg_iter_time_naive);

        // debug!("BiconnectedComponents bcc find time: {}", bcc_stat.bcc_find_time);
        // debug!("BiconnectedComponents single_source_shortest_paths time: {}", bcc_stat.single_source_shortest_paths_tm);
        bcc_stat_vec.push(bcc_stat);
    }

    // double avg_speedup = (num_edges_to_insert*brandes_time)/tot_fuad_time;
    let avg_speedup: f64 = tot_speedup / num_edges_to_insert as f64;

    debug!("[[Average speedup: {}]]", avg_speedup);

    Ok(())
}