Algorithm: TriangleCount / TriangleList

[mknblch]

TriangleCount counts the number of triangles in a Graph. TriangleList counts the number of triangles per node.

Progress TriangleCount + ClusteringCoefficient

• implement procedure
• tests
• edge case tests
• simple benchmark
• benchmark on bigger graphs
• parallelization
• documentation

[jexp]

@mknblch I would say:

algo.triangles.stream returns the triangles
algo.triangles returns the total count it its statistics, and writes the count per node onto the node into a triangles property

Did you check for any papers on this?
As 3 Nodes participate in triangles we "could" increase the count on all three of them, but then of course would have to track which ones we've already reported on/counted. Not sure if that's too much effort to save 2/3 of the work though?

[mknblch]

I've read some papers on counting triangles in a graph. Some of them depend on a relationExists-logic (which we do not have yet) some do set-operations and some do other weird stuff. The current implementation is oriented at our Graph design including some optimizations i've found in other algorithms (basically to reduce the BFS overhead). I added two Issues (#286, #287) which, if implemented, may allow us to implement a more efficient version of the algorithm.

PS. i'd like to leave the procedure for triangleCOUNT as is since it does not calculate the triangles for a given node but the SUM of all triangles in the graph. Therefore no write-back method exists nor a streaming-method.

Anyway.. i will implement triangleListing (the amount of triangles per node) in algo.triangles.* as you mentioned (including stream and writeback methods)