Number of Triangles in an Undirected Graph

Given an Undirected simple graph, We need to find how many triangles it can have. For example below graph have 2 triangles in it.

Let A[][] be adjacency matrix representation of graph. If we calculate A³, then the number of triangle in Undirected Graph is equal to trace(A³) / 6. Where trace(A) is the sum of the elements on the main diagonal of matrix A.

Trace of a graph represented as adjacency matrix A[V][V] is,
trace(A[V][V]) = A[0][0] + A[1][1] + .... + A[V-1][V-1]

Count of triangles = trace(A³) / 6

Below is implementation of above formula.

C++

// A C++ program for finding 
// number of triangles in an 
// Undirected Graph. The program 
// is for adjacency matrix 
// representation of the graph 
#include <bits/stdc++.h> 
using namespace std; 
  
// Number of vertices in the graph 
#define V 4 
  
//  Utility function for matrix 
// multiplication 
void multiply(int A[][V], int B[][V], int C[][V]) 
{ 
    for (int i = 0; i < V; i++) 
    { 
        for (int j = 0; j < V; j++) 
        { 
            C[i][j] = 0; 
            for (int k = 0; k < V; k++) 
                C[i][j] += A[i][k]*B[k][j]; 
        } 
    } 
} 
  
// Utility function to calculate 
// trace of a matrix (sum of 
// diagnonal elements) 
int getTrace(int graph[][V]) 
{ 
    int trace = 0; 
    for (int i = 0; i < V; i++) 
        trace += graph[i][i]; 
    return trace; 
} 
  
//  Utility function for calculating 
// number of triangles in graph 
int triangleInGraph(int graph[][V]) 
{ 
    // To Store graph^2 
    int aux2[V][V]; 
  
    // To Store graph^3 
    int aux3[V][V]; 
  
    //  Initialising aux 
    // matrices with 0 
    for (int i = 0; i < V; ++i) 
        for (int j = 0; j < V; ++j) 
            aux2[i][j] = aux3[i][j] = 0; 
  
    // aux2 is graph^2 now  printMatrix(aux2); 
    multiply(graph, graph, aux2); 
  
    // after this multiplication aux3 is 
    // graph^3 printMatrix(aux3); 
    multiply(graph, aux2, aux3); 
  
    int trace = getTrace(aux3); 
    return trace / 6; 
} 
  
// driver code 
int main() 
{ 
  
    int graph[V][V] = {{0, 1, 1, 0}, 
                       {1, 0, 1, 1}, 
                       {1, 1, 0, 1}, 
                       {0, 1, 1, 0} 
                      }; 
  
    printf("Total number of Triangle in Graph : %d
", 
            triangleInGraph(graph)); 
    return 0; 
} 

Java

// Java program to find number 
// of triangles in an Undirected 
// Graph. The program is for 
// adjacency matrix representation 
// of the graph 
import java.io.*; 
  
class Directed 
{ 
    // Number of vertices in 
    // the graph 
    int V = 4; 
   
   //  Utility function for 
   // matrix multiplication 
   void multiply(int A[][], int B[][], 
                            int C[][]) 
   { 
       for (int i = 0; i < V; i++) 
       { 
           for (int j = 0; j < V; j++) 
           { 
               C[i][j] = 0; 
               for (int k = 0; k < V;  
                                   k++) 
               { 
                   C[i][j] += A[i][k]* 
                              B[k][j]; 
               } 
           } 
       } 
   } 
   
   // Utility function to calculate 
   // trace of a matrix (sum of 
   // diagnonal elements) 
   int getTrace(int graph[][]) 
   { 
       int trace = 0; 
  
       for (int i = 0; i < V; i++) 
       { 
           trace += graph[i][i]; 
       } 
       return trace; 
   } 
   
   // Utility function for 
   // calculating number of 
   // triangles in graph 
   int triangleInGraph(int graph[][]) 
   { 
       // To Store graph^2 
       int[][] aux2 = new int[V][V];   
  
       // To Store graph^3 
       int[][] aux3 = new int[V][V]; 
   
       // Initialising aux matrices 
       // with 0 
       for (int i = 0; i < V; ++i) 
       { 
           for (int j = 0; j < V; ++j) 
           { 
               aux2[i][j] = aux3[i][j] = 0; 
           } 
       } 
   
       // aux2 is graph^2 now 
       // printMatrix(aux2) 
       multiply(graph, graph, aux2); 
   
       // after this multiplication aux3 
       // is graph^3 printMatrix(aux3) 
       multiply(graph, aux2, aux3); 
   
       int trace = getTrace(aux3); 
  
       return trace / 6; 
   } 
   
   // Driver code 
   public static void main(String args[]) 
   { 
       Directed obj = new Directed(); 
         
       int graph[][] = { {0, 1, 1, 0}, 
                         {1, 0, 1, 1}, 
                         {1, 1, 0, 1}, 
                         {0, 1, 1, 0} 
                       }; 
  
       System.out.println("Total number of Triangle in Graph : "+ 
              obj.triangleInGraph(graph)); 
   } 
} 
  
// This code is contributed by Anshika Goyal. 

Python3

# A Python3 program for finding number of  
# triangles in an Undirected Graph. The  
# program is for adjacency matrix  
# representation of the graph  
  
# Utility function for matrix  
# multiplication  
def multiply(A, B, C): 
    global V 
    for i in range(V): 
        for j in range(V): 
            C[i][j] = 0
            for k in range(V): 
                C[i][j] += A[i][k] * B[k][j] 
  
# Utility function to calculate  
# trace of a matrix (sum of  
# diagnonal elements)  
def getTrace(graph): 
    global V 
    trace = 0
    for i in range(V): 
        trace += graph[i][i]  
    return trace 
  
# Utility function for calculating  
# number of triangles in graph  
def triangleInGraph(graph): 
    global V 
      
    # To Store graph^2  
    aux2 = [[None] * V for i in range(V)] 
  
    # To Store graph^3  
    aux3 = [[None] * V for i in range(V)] 
  
    # Initialising aux  
    # matrices with 0 
    for i in range(V): 
        for j in range(V): 
            aux2[i][j] = aux3[i][j] = 0
  
    # aux2 is graph^2 now printMatrix(aux2)  
    multiply(graph, graph, aux2)  
  
    # after this multiplication aux3 is  
    # graph^3 printMatrix(aux3)  
    multiply(graph, aux2, aux3)  
  
    trace = getTrace(aux3)  
    return trace // 6
  
# Driver Code 
  
# Number of vertices in the graph  
V = 4
graph = [[0, 1, 1, 0],  
         [1, 0, 1, 1],  
         [1, 1, 0, 1],  
         [0, 1, 1, 0]] 
  
print("Total number of Triangle in Graph :", 
                    triangleInGraph(graph)) 
  
# This code is contributed by PranchalK 

C#

// C# program to find number 
// of triangles in an Undirected 
// Graph. The program is for 
// adjacency matrix representation 
// of the graph 
using System; 
  
class GFG 
{ 
// Number of vertices  
// in the graph 
int V = 4; 
  
// Utility function for 
// matrix multiplication 
void multiply(int [,]A, int [,]B, 
                        int [,]C) 
{ 
    for (int i = 0; i < V; i++) 
    { 
        for (int j = 0; j < V; j++) 
        { 
            C[i, j] = 0; 
            for (int k = 0; k < V;  
                              k++) 
            { 
                C[i, j] += A[i, k]* 
                           B[k, j]; 
            } 
        } 
    } 
} 
  
// Utility function to  
// calculate trace of  
// a matrix (sum of  
// diagnonal elements) 
int getTrace(int [,]graph) 
{ 
    int trace = 0; 
  
    for (int i = 0; i < V; i++) 
    { 
        trace += graph[i, i]; 
    } 
    return trace; 
} 
  
// Utility function for 
// calculating number of 
// triangles in graph 
int triangleInGraph(int [,]graph) 
{ 
    // To Store graph^2 
    int[,] aux2 = new int[V, V];  
  
    // To Store graph^3 
    int[,] aux3 = new int[V, V]; 
  
    // Initialising aux matrices 
    // with 0 
    for (int i = 0; i < V; ++i) 
    { 
        for (int j = 0; j < V; ++j) 
        { 
            aux2[i, j] = aux3[i, j] = 0; 
        } 
    } 
  
    // aux2 is graph^2 now 
    // printMatrix(aux2) 
    multiply(graph, graph, aux2); 
  
    // after this multiplication aux3 
    // is graph^3 printMatrix(aux3) 
    multiply(graph, aux2, aux3); 
  
    int trace = getTrace(aux3); 
  
    return trace / 6; 
} 
  
// Driver code 
public static void Main() 
{ 
    GFG obj = new GFG(); 
          
    int [,]graph = {{0, 1, 1, 0}, 
                    {1, 0, 1, 1}, 
                    {1, 1, 0, 1}, 
                    {0, 1, 1, 0}}; 
  
    Console.WriteLine("Total number of " +  
                   "Triangle in Graph : "+ 
              obj.triangleInGraph(graph)); 
} 
} 
  
// This code is contributed by anuj_67. 

Output:

Total number of Triangle in Graph : 2

How does this work?
If we compute Aⁿ for an adjacency matrix representation of graph, then a value Aⁿ[i][j] represents number of distinct walks between vertex i to j in graph. In A³, we get all distinct paths of length 3 between every pair of vertices.

A triangle is a cyclic path of length three, i.e. begins and ends at same vertex. So A³[i][i] represents a triangle beginning and ending with vertex i. Since a triangle has three vertices and it is counted for every vertex, we need to divide result by 3. Furthermore, since the graph is undirected, every triangle twice as i-p-q-j and i-q-p-j, so we divide by 2 also. Therefore, number of triangles is trace(A³) / 6.

Time Complexity:
The time complexity of above algorithm is O(V³) where V is number of vertices in the graph, we can improve the performance to O(V^2.8074) using Strassen’s matrix multiplication algorithm.

References:
http://www.d.umn.edu/math/Technical%20Reports/Technical%20Reports%202007-/TR%202012/yang.pdf
Number of Triangles in Directed and Undirected Graphs

Number of Triangles in an Undirected Graph

C++

Java

Python3

C#

tags:

leave a comment

0 Comments

Subscribe to Our Newsletter

Top Followed books