search

python-graphblas / graphblas-algorithms

Graph algorithms written in GraphBLAS
Apache License 2.0
74 stars 4 forks source link

Add `triangles` #3

Closed eriknw closed 2 years ago

eriknw commented 2 years ago

I think the tests could be improved. Some of the NetworkX tests get coverage, but only compare to 0 triangles. Also, we should test more with self-edges.

There may be better ways to compute triangles for:

There are a lot of different ways to compute triangles, so this could be explored further in the future. I hope the current PR is competitive.

eriknw commented 2 years ago

Triangle counting raises the inevitable question: how should we handle properties (such as has_self_edges) and cached computation such as lower and upper triangles? I say "inevitable", because we encountered the same issues in metagraph and LAGraph.

For now, they are passed as arguments to functions and computed if necessary.