fso_graph/
triangle_count.rs

1use crate::{prelude::*, DEFAULT_PARALLELISM};
2
3use log::info;
4use num_format::{Locale, ToFormattedString};
5
6use std::sync::atomic::AtomicU64;
7use std::thread::available_parallelism;
8use std::{sync::atomic::Ordering, time::Instant};
9
10const CHUNK_SIZE: usize = 64;
11
12pub fn relabel_graph<NI, G, EV>(graph: &mut G)
13where
14    NI: Idx,
15    G: RelabelByDegreeOp<NI, EV>,
16{
17    let start = Instant::now();
18    graph.make_degree_ordered();
19    info!("Relabeled graph in {:?}", start.elapsed());
20}
21
22pub fn global_triangle_count<NI, G>(graph: &G) -> u64
23where
24    NI: Idx,
25    G: Graph<NI> + UndirectedNeighbors<NI> + Sync,
26{
27    let start = Instant::now();
28
29    let next_chunk = Atomic::new(NI::zero());
30    let total_triangles = AtomicU64::new(0);
31
32    std::thread::scope(|s| {
33        let num_threads = available_parallelism().map_or(DEFAULT_PARALLELISM, |p| p.get());
34
35        for _ in 0..num_threads {
36            s.spawn(|| {
37                let mut triangles = 0;
38
39                loop {
40                    let start = NI::fetch_add(&next_chunk, NI::new(CHUNK_SIZE), Ordering::AcqRel);
41                    if start >= graph.node_count() {
42                        break;
43                    }
44
45                    let end = (start + NI::new(CHUNK_SIZE)).min(graph.node_count());
46
47                    for u in start.range(end) {
48                        for &v in graph.neighbors(u) {
49                            if v > u {
50                                break;
51                            }
52
53                            let mut it = put_back_iterator(graph.neighbors(u));
54
55                            for &w in graph.neighbors(v) {
56                                if w > v {
57                                    break;
58                                }
59                                while let Some(x) = it.next() {
60                                    if x >= &w {
61                                        if x == &w {
62                                            triangles += 1;
63                                        }
64                                        it.put_back(x);
65                                        break;
66                                    }
67                                }
68                            }
69                        }
70                    }
71                }
72                total_triangles.fetch_add(triangles, Ordering::AcqRel);
73            });
74        }
75    });
76
77    let tc = total_triangles.load(Ordering::SeqCst);
78
79    info!(
80        "Computed {} triangles in {:?}",
81        tc.to_formatted_string(&Locale::en),
82        start.elapsed()
83    );
84
85    tc
86}
87
88#[cfg(test)]
89mod tests {
90    use super::*;
91    use crate::prelude::{CsrLayout, GraphBuilder, UndirectedCsrGraph};
92
93    #[test]
94    fn test_tc_two_components() {
95        let gdl = "(a)-->()-->()<--(a),(b)-->()-->()<--(b)";
96
97        let graph: UndirectedCsrGraph<usize> = GraphBuilder::new()
98            .csr_layout(CsrLayout::Deduplicated)
99            .gdl_str::<usize, _>(gdl)
100            .build()
101            .unwrap();
102
103        assert_eq!(global_triangle_count(&graph), 2);
104    }
105
106    #[test]
107    fn test_tc_connected_triangles() {
108        let gdl = "(a)-->()-->()<--(a),(a)-->()-->()<--(a)";
109
110        let graph: UndirectedCsrGraph<usize> = GraphBuilder::new()
111            .csr_layout(CsrLayout::Deduplicated)
112            .gdl_str::<usize, _>(gdl)
113            .build()
114            .unwrap();
115
116        assert_eq!(global_triangle_count(&graph), 2);
117    }
118
119    #[test]
120    fn test_tc_diamond() {
121        let gdl = "(a)-->(b)-->(c)<--(a),(b)-->(d)<--(c)";
122
123        let graph: UndirectedCsrGraph<usize> = GraphBuilder::new()
124            .csr_layout(CsrLayout::Deduplicated)
125            .gdl_str::<usize, _>(gdl)
126            .build()
127            .unwrap();
128
129        assert_eq!(global_triangle_count(&graph), 2);
130    }
131}
fso_graph/triangle_count.rs

fso_graph/
triangle_count.rs
