Number of Triangles in an Undirected Graph | Number of vertices in the graph ; Utility function for matrix multiplication ; Utility function to calculate trace of a matrix ( sum ofdiagnonal elements ) ; Utility function for calculating number of triangles in graph ; To Store graph ^ 2 ; To Store graph ^ 3 ; Initialising aux matrices with 0 ; aux2 is graph ^ 2 now printMatrix ( aux2 ) ; after this multiplication aux3 is graph ^ 3 printMatrix ( aux3 ) ; Driver Code
V = 4 NEW_LINE def multiply ( A , B , C ) : NEW_LINE INDENT global V NEW_LINE for i in range ( V ) : NEW_LINE INDENT for j in range ( V ) : NEW_LINE INDENT C [ i ] [ j ] = 0 NEW_LINE for k in range ( V ) : NEW_LINE INDENT C [ i ] [ j ] += A [ i ] [ k ] * B [ k ] [ j ] NEW_LINE DEDENT DEDENT DEDENT DEDENT def getTrace ( graph ) : NEW_LINE INDENT global V NEW_LINE trace = 0 NEW_LINE for i in range ( V ) : NEW_LINE INDENT trace += graph [ i ] [ i ] NEW_LINE DEDENT return trace NEW_LINE DEDENT def triangleInGraph ( graph ) : NEW_LINE INDENT global V NEW_LINE aux2 = [ [ None ] * V for i in range ( V ) ] NEW_LINE aux3 = [ [ None ] * V for i in range ( V ) ] NEW_LINE for i in range ( V ) : NEW_LINE INDENT for j in range ( V ) : NEW_LINE INDENT aux2 [ i ] [ j ] = aux3 [ i ] [ j ] = 0 NEW_LINE DEDENT DEDENT multiply ( graph , graph , aux2 ) NEW_LINE multiply ( graph , aux2 , aux3 ) NEW_LINE trace = getTrace ( aux3 ) NEW_LINE return trace // 6 NEW_LINE DEDENT graph = [ [ 0 , 1 , 1 , 0 ] , [ 1 , 0 , 1 , 1 ] , [ 1 , 1 , 0 , 1 ] , [ 0 , 1 , 1 , 0 ] ] NEW_LINE print ( " Total ▁ number ▁ of ▁ Triangle ▁ in ▁ Graph ▁ : " , triangleInGraph ( graph ) ) NEW_LINE