graph 0.3.1

use crate::{prelude::*, DEFAULT_PARALLELISM};

use log::info;
use num_format::{Locale, ToFormattedString};

use std::sync::atomic::AtomicU64;
use std::thread::available_parallelism;
use std::{sync::atomic::Ordering, time::Instant};

const CHUNK_SIZE: usize = 64;

pub fn relabel_graph<NI, G, EV>(graph: &mut G)
where
    NI: Idx,
    G: RelabelByDegreeOp<NI, EV>,
{
    let start = Instant::now();
    graph.make_degree_ordered();
    info!("Relabeled graph in {:?}", start.elapsed());
}

pub fn global_triangle_count<NI, G>(graph: &G) -> u64
where
    NI: Idx,
    G: Graph<NI> + UndirectedNeighbors<NI> + Sync,
{
    let start = Instant::now();

    let next_chunk = Atomic::new(NI::zero());
    let total_triangles = AtomicU64::new(0);

    std::thread::scope(|s| {
        let num_threads = available_parallelism().map_or(DEFAULT_PARALLELISM, |p| p.get());

        for _ in 0..num_threads {
            s.spawn(|| {
                let mut triangles = 0;

                loop {
                    let start = NI::fetch_add(&next_chunk, NI::new(CHUNK_SIZE), Ordering::AcqRel);
                    if start >= graph.node_count() {
                        break;
                    }

                    let end = (start + NI::new(CHUNK_SIZE)).min(graph.node_count());

                    for u in start.range(end) {
                        for &v in graph.neighbors(u) {
                            if v > u {
                                break;
                            }

                            let mut it = put_back_iterator(graph.neighbors(u));

                            for &w in graph.neighbors(v) {
                                if w > v {
                                    break;
                                }
                                while let Some(x) = it.next() {
                                    if x >= &w {
                                        if x == &w {
                                            triangles += 1;
                                        }
                                        it.put_back(x);
                                        break;
                                    }
                                }
                            }
                        }
                    }
                }
                total_triangles.fetch_add(triangles, Ordering::AcqRel);
            });
        }
    });

    let tc = total_triangles.load(Ordering::SeqCst);

    info!(
        "Computed {} triangles in {:?}",
        tc.to_formatted_string(&Locale::en),
        start.elapsed()
    );

    tc
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::prelude::{CsrLayout, GraphBuilder, UndirectedCsrGraph};

    #[test]
    fn test_tc_two_components() {
        let gdl = "(a)-->()-->()<--(a),(b)-->()-->()<--(b)";

        let graph: UndirectedCsrGraph<usize> = GraphBuilder::new()
            .csr_layout(CsrLayout::Deduplicated)
            .gdl_str::<usize, _>(gdl)
            .build()
            .unwrap();

        assert_eq!(global_triangle_count(&graph), 2);
    }

    #[test]
    fn test_tc_connected_triangles() {
        let gdl = "(a)-->()-->()<--(a),(a)-->()-->()<--(a)";

        let graph: UndirectedCsrGraph<usize> = GraphBuilder::new()
            .csr_layout(CsrLayout::Deduplicated)
            .gdl_str::<usize, _>(gdl)
            .build()
            .unwrap();

        assert_eq!(global_triangle_count(&graph), 2);
    }

    #[test]
    fn test_tc_diamond() {
        let gdl = "(a)-->(b)-->(c)<--(a),(b)-->(d)<--(c)";

        let graph: UndirectedCsrGraph<usize> = GraphBuilder::new()
            .csr_layout(CsrLayout::Deduplicated)
            .gdl_str::<usize, _>(gdl)
            .build()
            .unwrap();

        assert_eq!(global_triangle_count(&graph), 2);
    }
}