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
let V = 4 ; function multiply ( A , B , C ) { for ( let i = 0 ; i < V ; i ++ ) { for ( let j = 0 ; j < V ; j ++ ) { C [ i ] [ j ] = 0 ; for ( let k = 0 ; k < V ; k ++ ) C [ i ] [ j ] += A [ i ] [ k ] * B [ k ] [ j ] ; } } } function getTrace ( graph ) { let trace = 0 ; for ( let i = 0 ; i < V ; i ++ ) trace += graph [ i ] [ i ] ; return trace ; } function triangleInGraph ( graph ) { let aux2 = new Array ( V ) ; let aux3 = new Array ( V ) ; for ( let i = 0 ; i < V ; ++ i ) { aux2 [ i ] = new Array ( V ) ; aux3 [ i ] = new Array ( V ) ; for ( let j = 0 ; j < V ; ++ j ) { aux2 [ i ] [ j ] = aux3 [ i ] [ j ] = 0 ; } } multiply ( graph , graph , aux2 ) ; multiply ( graph , aux2 , aux3 ) ; let trace = getTrace ( aux3 ) ; return ( trace / 6 ) ; } let graph = [ [ 0 , 1 , 1 , 0 ] , [ 1 , 0 , 1 , 1 ] , [ 1 , 1 , 0 , 1 ] , [ 0 , 1 , 1 , 0 ] ] ; document . write ( " " + triangleInGraph ( graph ) ) ;