Number of Triangles in a Directed and Undirected Graph

The problem, simply

You get a graph: dots joined by lines. A triangle is three dots where every pair of them is joined. Count how many triangles there are.

There are two versions. With two-way lines (undirected), any three dots that are all joined count once. With one-way arrows (directed), a triangle is a loop a > b > c > a, and each loop counts once.

A story to remember it

Picture it

Examples

Way 1: the simple way

Try every group of three dots and check the lines between them. Store the lines in a table (an adjacency matrix) so each check is instant.

1. Undirected: for every i < j < k, if i-j, j-k and i-k all exist, count one.
2. Directed: for every ordered i, j, k of different dots, if i>j, j>k and k>i all exist, count one. Each loop is found 3 times (starting at each of its corners), so divide by 3.

class TrianglesBrute {
    public static int countUndirected(int[][] adj) {
        int n = adj.length, count = 0;
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)
                for (int k = j + 1; k < n; k++)
                    if (adj[i][j] == 1 && adj[j][k] == 1 && adj[i][k] == 1) count++;
        return count;
    }

    public static int countDirected(int[][] adj) {
        int n = adj.length, count = 0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                for (int k = 0; k < n; k++)
                    if (i != j && j != k && i != k
                        && adj[i][j] == 1 && adj[j][k] == 1 && adj[k][i] == 1) count++;
        return count / 3;          // each loop is seen from all 3 corners
    }
}

How long it takes: three nested loops over the dots, O(V^3). Extra room: the V by V table, O(V^2). For a big graph with few lines, almost all of that work checks pairs that are not even friends.

Way 2: the clever way

Use the shyest kid rule. Order the dots by how many lines they have (their degree), breaking ties by number. Turn every line into an arrow that points from the less popular end to the more popular end. Now every triangle has exactly one corner with two arrows going out, its shyest corner, so it is counted once.

1. Count each dot's lines.
2. Point every line toward the more popular end.
3. For each dot u: put a sticker on every dot its arrows point to.
4. For each such dot v, follow v's arrows. Every dot w you reach that has u's sticker closes a triangle u, v, w.

For one-way arrows the order trick does not apply, because the arrows already have a direction. Instead, for every arrow a > b, look at each arrow b > c and check whether c > a exists, using a set for each dot. Each loop is found once from each of its 3 arrows, so divide by 3.

class Triangles {
    // Undirected: each triangle is counted once, by its shyest corner
    public static long countUndirected(int n, int[][] edges) {
        int[] deg = new int[n];
        for (int[] e : edges) { deg[e[0]]++; deg[e[1]]++; }
        List<List<Integer>> up = new ArrayList<>();
        for (int i = 0; i < n; i++) up.add(new ArrayList<>());
        for (int[] e : edges) {
            int a = e[0], b = e[1];
            boolean aFirst = deg[a] < deg[b] || (deg[a] == deg[b] && a < b);
            if (aFirst) up.get(a).add(b); else up.get(b).add(a);  // point to the more popular end
        }
        int[] sticker = new int[n];
        Arrays.fill(sticker, -1);
        long count = 0;
        for (int u = 0; u < n; u++) {
            for (int v : up.get(u)) sticker[v] = u;      // stamp u's friends
            for (int v : up.get(u))
                for (int w : up.get(v))
                    if (sticker[w] == u) count++;        // u, v, w all know each other
        }
        return count;
    }

    // Directed: count loops a > b > c > a
    public static long countDirected(int n, int[][] edges) {
        List<Set<Integer>> out = new ArrayList<>();
        for (int i = 0; i < n; i++) out.add(new HashSet<>());
        for (int[] e : edges) out.get(e[0]).add(e[1]);
        long count = 0;
        for (int[] e : edges) {
            int a = e[0], b = e[1];
            if (a == b) continue;
            for (int c : out.get(b))
                if (c != a && c != b && out.get(c).contains(a)) count++;
        }
        return count / 3;                                // found once from each of its 3 arrows
    }
}

How long it takes: after the arrows point toward the popular end, every dot has at most about sqrt(2E) arrows going out. A dot with more would need that many even more popular friends, each with at least that many lines, which is more lines than exist. So the undirected count is O(E * sqrt(E)). The directed count is O(E * d), where d is the most arrows leaving one dot. Extra room: the lists and sets, O(V + E).

Another way: the matrix trick

Multiply the adjacency matrix A by itself three times. The number on the diagonal at A^3[i][i] counts the walks of 3 steps that leave dot i and come back to it. In an undirected graph each triangle gives 6 such walks (3 starting corners times 2 directions), so the answer is the diagonal sum divided by 6. In a directed graph each loop gives 3, so divide by 3. This is the classic textbook answer, but it costs O(V^3) with plain multiplication.

class TrianglesMatrix {
    public static int count(int[][] adj, boolean directed) {
        int n = adj.length;
        int[][] a3 = multiply(multiply(adj, adj), adj);
        int trace = 0;
        for (int i = 0; i < n; i++) trace += a3[i][i];   // walks that come home after 3 steps
        return directed ? trace / 3 : trace / 6;
    }

    static int[][] multiply(int[][] a, int[][] b) {
        int n = a.length;
        int[][] c = new int[n][n];
        for (int i = 0; i < n; i++)
            for (int k = 0; k < n; k++)
                if (a[i][k] != 0)
                    for (int j = 0; j < n; j++) c[i][j] += a[i][k] * b[k][j];
        return c;
    }
}

Watch out for

• In the directed version, three dots joined by arrows are not always a loop. 0>1, 1>2, 0>2 is not a triangle there.
• Self loops and repeated lines. Clean the input first, or they create fake triangles.
• Use long for the count. A graph with many lines can have far more triangles than an int holds.
• Fewer than 3 dots means 0 triangles.

What interviewers ask next

• Can you count triangles that touch one given dot? Mark its friends, then count lines between two marked friends.
• How would you do it on a graph too big for one machine? Split the lines by their shyest corner and count each part separately; the degree order keeps the parts balanced.
• Is there anything faster than O(V^3) for dense graphs? Fast matrix multiplication beats it in theory, and bitsets (64 friends per machine word) make the brute force much faster in practice.
• What about the clustering of a social network? It is the number of triangles compared with the number of paths of length 2, so you need exactly this count.

Remember this

Grown-up words: the friendship table is an adjacency matrix, the number of friends is the degree, pointing lines toward the popular end is a degree ordering, the stickers are a marker array, and the diagonal sum of A^3 is the trace.