A triangle in a graph is a set of three vertices all connected together. Finding, counting, and/or listing triangles in very large graphs is both of theoretical interest (as a natural and simple algorithmic question) and of practical impact (it is used in motif discovery and clustering coefficient computations in complex networks).

I propose in:
Main-memory Triangle Computations for Very Large (Sparse (Power-Law)) Graphs , Theoretical Computer Science (TCS) 407 (1-3), pages 458-473, 2008,
a survey of existing methods, and new contributions to the field. In this paper, my concern is both theoretical asymptotic complexity of algorithms and their practical usability (concerning both time and space requirements, and implementation).

This page provides an implementation of the main algorithms discussed in this paper. It is provided 'as is', with absolutely no warranty. It is written in C, designed for use on Unix/Linux systems, but it should be easily portable to any platform.

You may use and distribute this code, provided that you cite the paper above and this web page. You may also write me an e-mail (matthieu.latapy@lip6.fr) if you find it useful, if you find a bug, or have any improvement.

Download: README file and C source code