Introduction
Counting the number of triangles in an undirected graph is a tricky question. It seems easy when we read it. But finding the proper logic and implementing it is hard to crack.
This article will discuss the solution to the problem of counting the number of triangles in an undirected graph. We will use a trace of the graph as adjacency and bitset and adjacency list approach to finding the problem's solution.
Now let’s see the problem statement of this approach.
Problem Statement
Given an Undirected simple graph, We need to find how many triangles it can have.
Sample Examples
Example 1:
Input:
Output:
Explanation: The above example has four triangles. They are (0,2,4), (0,1,3), (1,2,3), (0,2,4).
Example 2:
Input:
Output:
Explanation: The above example has six triangles. They are (0,1,3), (1,2,3), (0,2,4), (0,1,2) (0,3,4), (2,3,4).
Trace of Graph as Adjacency Matrix Approach
We will use a trace of the graph as an adjacency matrix. This will help us find the solution to the problem, count the number of triangles in an undirected graph. The trace of a matrix A is the sum of the elements on the main diagonal. The sum of a matrix's eigenvalues also equals the matrix's trace.
Let’s see the algorithm of this approach.
Algorithm
- Let A be the adjacency matrix that represents the graph.
- If we calculate A3. The number of triangles in the undirected graph equals to trace(A3) / 6.
- Here trace(A) is the sum of the elements on the main diagonal of the matrix A.
- And the trace of a graph is represented as adjacency matrix A[G][G] is,
- We will use the following formula to find the trace of matrices:
trace(A[G][G]) = A[0][0] + A[1][1] + .... + A[G-1][G-1]
Number of triangles = trace(A3) / 6
You can also read Detect cycle in an undirected graph here.
Implementation in C++
#include <bits/stdc++.h>
using namespace std;
#define FAST ios_base::sync_with_stdio(false); cin.tie(NULL);
#define G 4
//----------------Utility function for matrix multiplication----------------//
void multiplymatrices(int A[][G], int B[][G], int C[][G])
{
for (int i = 0; i < G; i++)
{
for (int j = 0; j < G; j++)
{
C[i][j] = 0;
for (int k = 0; k < G; k++)
C[i][j] += A[i][k]*B[k][j];
}
}
}
//----------------Utility function to calculate trace of a matrix----------------//
int Trace(int graph[][G])
{
int traceofmatrix = 0;
for (int i = 0; i < G; i++)
traceofmatrix += graph[i][i];
return traceofmatrix;
}
//----------------Utility function for calculating the number of triangles----------------//
int numoftriangle(int graph[][G])
{
// To Store graph 2
int adj2[G][G];
// To Store graph 3
int adj3[G][G];
for (int i = 0; i < G; ++i)
for (int j = 0; j < G; ++j)
adj2[i][j] = adj3[i][j] = 0;
// adj2 is graph 2, now printMatrix(adj2);
multiplymatrices(graph, graph, adj2);
// after this multiplication adj3 is
multiplymatrices(graph, adj2, adj3);
int traceofmatrix = Trace(adj3);
return traceofmatrix / 6;
}
//---------------------------Main Function---------------------------//
int main()
{
FAST;
int graph[G][G] = {{0, 1, 1, 0},
{1, 0, 1, 1},
{1, 1, 0, 1},
{0, 1, 1, 0}
};
printf("Total number of Triangle in Graph : %d\n",
numoftriangle(graph));
return 0;
}
Output:
Time Complexity
The time complexity of the above-used approach is O(V3). As here most time-consuming part is the multiplication of the matrix, which contains three nested for loops.
Space Complexity
The time complexity of the above-used approach is O(V2). It is because we are storing a matrix of size V*V.