foo.rs

pub fn triangles<V>(g: &StaticGraph<V>) -> usize where V: SimpleVertex {
    let mut dodg: Vec<Vec<V>> = Vec::with_capacity(g.nv());

    let mut degrees = vec![V::zero(); g.nv()];
    let mut ntri = 0usize;

    // let z:Vec<V> = g.vertices().collect();
    // println!("minvert = {:?}, maxvert = {:?}", z.iter().min(), z.iter().max());
    for u in g.vertices() {
        let degu = g.outdegree(u);
        degrees[u.as_()] = degu;
        let vvec = g.outneighbors(u).into_iter().filter(|v| {
            let degv = g.outdegree(**v);
            degv > degu || (degv == degu && **v > u)
        }).cloned().collect();
        dodg.push(vvec);
    }

    // println!("len(dodg) = {}", dodg.len());
    for u in g.vertices() {
        let uvec = &dodg[u.as_()];
        let ulen = uvec.len();
        for i in 0..ulen {
            let v = uvec[i];
            let vvec = &dodg[v.as_()];
            for j in (i+1)..ulen {
                let w = uvec[j];
                let wvec = &dodg[w.as_()];
                let w_to_v = degrees[v.as_()] > degrees[w.as_()] || (degrees[v.as_()] == degrees[w.as_()] && v > w);
                if (w_to_v && wvec.binary_search(&v).is_ok()) || (!w_to_v && vvec.binary_search(&w).is_ok()) {
                     ntri += 1;
                }
            }
        }
    }
    ntri
}