The code counts triangles exactly, code used for exact counting in the paper "Efficient Triangle Counting in Large Graphs via Degree-based Vertex Partitioning" by Mihail N. Kolountzakis, Gary L. Miller, Richard Peng, Charalampos E. Tsourakakis. Code takes as input a compressed graph, as compressed by Graph-Compression.

• To compile, run g++ -o triExact triExact.cc
• To run, first compress the graph using ./compress < toy.txt > toycompressed.txt, and then ./triExact < toy_compressed.txt
• Toy example

time ./triExact < toy_compressed.txt # of triangles encountered: 20666503

real 0m0.961s user 0m0.834s sys 0m0.108s

• One can compare with the code of M. Latapy available here. time ./tr -c -cc -n 100 < latapy_toy.txt Found 20666503 triangles...

real 0m1.525s user 0m1.476s sys 0m0.020s