# Number of Triangles in Directed and Undirected Graphs

Given a Graph, count number of triangles in it. The graph is can be directed or undirected.

Example:

Input: digraph[V][V] = { {0, 0, 1, 0},
{1, 0, 0, 1},
{0, 1, 0, 0},
{0, 0, 1, 0}
};
Output: 2
directed graph.

We have discussed a method based on graph trace that works for undirected graphs. In this post a new method is discussed with that is simpler and works for both directed and undirected graphs.

The idea is to use three nested loops to consider every triplet (i, j, k) and check for the above condition (there is an edge from i to j, j to k and k to i)
However in an undirected graph, the triplet (i, j, k) can be permuted to give six combination (See previous post for details). Hence we divide the total count by 6 to get the actual number of triangles.
In case of directed graph, the number of permutation would be 3 (as order of nodes becomes relevant). Hence in this case the total number of triangles will be obtained by dividing total count by 3. For example consider the directed graph given below

Following is the implementation.

## C/C++

 // C++ program to count triangles // in a graph. The program is for // adjacency matrix representation // of the graph. #include    // Number of vertices in the graph #define V 4    using namespace std;    // function to calculate the // number of triangles in a // simple directed/undirected  // graph. isDirected is true if // the graph is directed, its // false otherwise int countTriangle(int graph[V][V],                    bool isDirected) {     // Initialize result     int count_Triangle = 0;        // Consider every possible     // triplet of edges in graph     for (int i = 0; i < V; i++)     {         for (int j = 0; j < V; j++)         {             for (int k = 0; k < V; k++)             {                // check the triplet if                // it satisfies the condition                if (graph[i][j] && graph[j][k]                                 && graph[k][i])                   count_Triangle++;              }         }     }        // if graph is directed ,      // division is done by 3,     // else division by 6 is done     isDirected? count_Triangle /= 3 :                 count_Triangle /= 6;        return count_Triangle; }    //driver function to check the program int main() {     // Create adjacency matrix     // of an undirected graph     int graph[][V] = { {0, 1, 1, 0},                        {1, 0, 1, 1},                        {1, 1, 0, 1},                        {0, 1, 1, 0}                      };        // Create adjacency matrix     // of a directed graph     int digraph[][V] = { {0, 0, 1, 0},                         {1, 0, 0, 1},                         {0, 1, 0, 0},                         {0, 0, 1, 0}                        };        cout << "The Number of triangles in undirected graph : "          << countTriangle(graph, false);     cout << " The Number of triangles in directed graph : "          << countTriangle(digraph, true);        return 0; }

## Java

 // Java program to count triangles // in a graph.  The program is // for adjacency matrix // representation of the graph. import java.io.*;    class GFG {        // Number of vertices in the graph     int V = 4;        // function to calculate the number     // of triangles in a simple     // directed/undirected graph. isDirected     // is true if the graph is directed,     // its false otherwise.     int countTriangle(int graph[][],                        boolean isDirected)    {        // Initialize result        int count_Triangle = 0;           // Consider every possible        // triplet of edges in graph        for (int i = 0; i < V; i++)        {            for (int j = 0; j < V; j++)            {                for (int k=0; k

## Python

 # Python program to count triangles in a graph.  The program is # for adjacency matrix representation of the graph.       # function to calculate the number of triangles in a simple # directed/undirected graph. # isDirected is true if the graph is directed, its false otherwise def countTriangle(g, isDirected):     nodes = len(g)     count_Triangle = 0 #Initialize result     # Consider every possible triplet of edges in graph     for i in range(nodes):         for j in range(nodes):             for k in range(nodes):                 # check the triplet if it satisfies the condition                 if( i!=j and i !=k and j !=k and                          g[i][j] and g[j][k] and g[k][i]):                     count_Triangle += 1     # if graph is directed , division is done by 3     # else division by 6 is done     return count_Triangle/3 if isDirected else count_Triangle/6    # Create adjacency matrix of an undirected graph graph = [[0, 1, 1, 0],        [1, 0, 1, 1],        [1, 1, 0, 1],        [0, 1, 1, 0 ]] # Create adjacency matrix of a directed graph digraph = [[0, 0, 1, 0],              [1, 0, 0, 1],           [0, 1, 0, 0],           [0, 0, 1, 0 ]]    print ("The Number of triangles in undirected graph : %d" %countTriangle(graph, False))    print ("The Number of triangles in directed graph : %d" %countTriangle(digraph, True))    # This code is contributed by Neelam Yadav

## C#

 // C# program to count triangles in a graph. // The program is for adjacency matrix // representation of the graph. using System;    class GFG {            // Number of vertices in the graph     const int V = 4;            // function to calculate the     // number of triangles in a     // simple directed/undirected      // graph. isDirected is true if     // the graph is directed, its     // false otherwise     static int countTriangle(int[,] graph,                      bool isDirected)     {         // Initialize result         int count_Triangle = 0;                // Consider every possible         // triplet of edges in graph         for (int i = 0; i < V; i++)         {             for (int j = 0; j < V; j++)             {                 for (int k = 0; k < V; k++)                 {                 // check the triplet if                 // it satisfies the condition                 if (graph[i,j] != 0 &&                     graph[j,k] != 0 &&                       graph[k,i] != 0 )                     count_Triangle++;                 }             }         }                // if graph is directed ,          // division is done by 3,         // else division by 6 is done         if(isDirected != false)             count_Triangle =                          count_Triangle / 3 ;         else             count_Triangle =                           count_Triangle / 6;                return count_Triangle;     }            // Driver function to check the program     static void Main()          {                    // Create adjacency matrix         // of an undirected graph         int[,] graph = new int[4,4] {                              {0, 1, 1, 0},                             {1, 0, 1, 1},                              {1, 1, 0, 1},                              {0, 1, 1, 0}                          };                // Create adjacency matrix         // of a directed graph         int[,] digraph = new int [4,4] {                             {0, 0, 1, 0},                             {1, 0, 0, 1},                             {0, 1, 0, 0},                             {0, 0, 1, 0}                         };                                                                      Console.Write("The Number of triangles"                     + " in undirected graph : "                 + countTriangle(graph, false));                            Console.Write(" The Number of "          + "triangles in directed graph : "             + countTriangle(digraph, true));     } }    // This code is contributed by anuj_67

## PHP



Output:

The Number of triangles in undirected graph : 2
The Number of triangles in directed graph : 2

Comparison of this approach with previous approach:

• No need to calculate Trace.
• Matrix- multiplication is not required.
• Auxiliary matrices are not required hence optimized in space.
• Works for directed graphs.

• The time complexity is O(n3) and can’t be reduced any further.

## tags:

Graph triangle Graph