Syntax:
tri_find -i in1 -o out1.file out1.mr
Examples:
tri_find -i mre -o tri.list mtri
Description:
This is a named command which enumerates all the triangles in an undirected graph. A triangle is a set of 3 vertices I,J,K for which the edges IJ, JK, IK all exist. The triangles are found via the MapReduce algorithm of (Cohen) discussed in his paper and in the paper of (Plimpton). Note that even small graphs can have large numbers of triangles if there are very high-degree vertices.
See the named command doc page for various ways in which the -i inputs and -o outputs for a named command can be specified.
In1 stores a set of edges, assumed to have no duplicates or self-edges. This means that either (Vi,Vj) or (Vj,Vi) appears, but not both. Also (Vi,Vi) does not appear. The input is unchanged by this command.
Out1 will store the list of triangles.
Related commands: none
(Cohen) Cohen, "Graph Twiddling in a MapReduce World", Computing in Science and Engineering, 11, 29-41 (2009).
(Plimpton) Plimpton and Devine, "MapReduce in MPI for Large-Scale Graph Algorithms", to appear in Parallel Computing (2011).