MR-MPI WWW Site -MR-MPI Documentation - OINK
Documentation - OINK Commands

### tri_find command

**Syntax:**

tri_find -i in1 -o out1.file out1.mr

- in1 = graph edges: Key = Vi Vj, Value = NULL
- out1 = triangles: Key = Vi Vj Vk, Value = NULL

**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).