Skip to content

Instantly share code, notes, and snippets.

@sbromberger
Created July 13, 2020 22:24
Show Gist options
  • Save sbromberger/c2d4d5a343b4a51e4df0107e9b338de8 to your computer and use it in GitHub Desktop.
Save sbromberger/c2d4d5a343b4a51e4df0107e9b338de8 to your computer and use it in GitHub Desktop.
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
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment