Count triangles in a graph

Medium

Problem

Count the triangles (sets of three mutually connected vertices) in a graph given as an adjacency matrix. Note the directed and undirected counts differ in how duplicates are divided out.

Example 1

Input:  undirected [[0,1,1,0], [1,0,1,1], [1,1,0,1], [0,1,1,0]]
Output: 2

{0,1,2} and {1,2,3}.

Also asked as: Number of Triangles in a Directed and Undirected Graph

Test cases

Case 1

Input:    [[0,1,1,0],[1,0,1,1],[1,1,0,1],[0,1,1,0]]
Expected: 2

Case 2

Input:    [[0,1,1,1],[1,0,1,1],[1,1,0,1],[1,1,1,0]]
Expected: 4

Case 3

Input:    [[0,1,1],[1,0,1],[1,1,0]]
Expected: 1

Case 4

Input:    [[0,1],[1,0]]
Expected: 0

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Trace of A³ / adjacency-matrix cubing

Time O(V³)Space O(V²)

The number of closed walks of length 3 is trace(A³). Divide by 6 for an undirected graph, by 3 for a directed one.

function countTriangles(A, directed = false) {
const n = A.length;
const mul = (X, Y) => {
const Z = Array.from({ length: n }, () => new Array(n).fill(0));
for (let i = 0; i < n; i++)
for (let k = 0; k < n; k++)
if (X[i][k]) for (let j = 0; j < n; j++) Z[i][j] += X[i][k] * Y[k][j];
return Z;
};
const A3 = mul(mul(A, A), A);
let trace = 0;
for (let i = 0; i < n; i++) trace += A3[i][i];
return trace / (directed ? 3 : 6);
}