====== Counting triangles ======

10. april 2014

{{notes:pics:triangles.jpg?400}}

T = A<sup>T</sup>, S = A + T

Each triangle appears exactly once in AAA + AAT + TAT + TAA = AAS + TAS = SAS
<code>
def VecSum(a,b):
   n = len(a)
   c = [0 for i in range(n)]
   for i in range(n): c[i] = a[i]+b[i]
   return(c)

def MatList(M,names=None):
   n = len(M)
   for i in range(n):
      if names==None: print('[',i+1,') =',M[i])
      else: print('[',names[i],') = ',M[i])

def MatTrans(A):
   nr = len(A); nc = len(A[0])
   T = [[ 0 for i in range(nr)] for j in range(nc)]
   for u in range(nr):
      for v in range(nc):
         T[v][u] = A[u][v]
   return(T)

def MatSym(A):
   nr = len(A); nc = len(A[0])
   if nr!=nc: return(None)
   B = [[ 0 for i in range(nr)] for j in range(nr)]
   for u in range(nr-1):
      for v in range(u+1,nr):
         B[u][v] = A[u][v]+A[v][u]
         B[v][u] = B[u][v]
   return(B)

def MatBin(A):
   nr = len(A); nc = len(A[0])
   B = [[ 0 for i in range(nc)] for j in range(nr)]
   for u in range(nr):
      for v in range(nc):
         B[u][v] = int(A[u][v]>0)
   return(B) 

def MatSetDiag(A,const):
   nr = len(A); nc = len(A[0])    
   if nr!=nc: return(None)
   B = A
   for u in range(nr): B[u][u] = const
   return(B)

def MatSum(A,B):
   nra = len(A); nca = len(A[0]); nrb = len(B); ncb = len(B[0]);
   if nra!=nrb: return(None)
   if nca!=ncb: return(None)
   C = [[ 0 for i in range(nca)] for j in range(nra)]
   for u in range(nra):
      for v in range(nca):
         C[u][v] = A[u][v]+B[u][v]
   return(C)

def MatProd(A,B):
   nra = len(A); nca = len(A[0]); nrb = len(B); ncb = len(B[0]);
   if nca!=nrb: return(None)
   C = [[ 0 for i in range(ncb)] for j in range(nra)]
   for u in range(nra):
      for v in range(ncb):
         s = 0 
         for t in range(nca):
            s = s+A[u][t]*B[t][v]
         C[u][v] = s
   return(C)

def MatProdDiag(A,B):
   nra = len(A); nca = len(A[0]); nrb = len(B); ncb = len(B[0]);
   if nca!=nrb: return(None)
   if nra!=ncb: return(None)
   x = [ 0 for u in range(nra)] 
   for u in range(nra):
      s = 0 
      for v in range(nca):
         s = s+A[u][v]*B[v][u]
      x[u] = s
   return(x)


A = [[ 0 for i in range(7)] for j in range(7)]
A[1][0] = 1; A[1][3] = 1; A[1][2] = 1; A[2][1] = 1
A[2][5] = 1; A[3][0] = 1; A[3][2] = 1; A[3][4] = 1
A[3][6] = 1; A[3][5] = 1; A[4][0] = 1; A[4][1] = 1
A[4][3] = 1; A[4][5] = 1; A[5][4] = 1; A[5][6] = 1
A[6][2] = 1

print("matrix A"); MatList(A)
T = MatTrans(A)
print("transposed A"); MatList(T)
S = MatSym(A); 
print("symmetric A"); MatList(S)
Q = MatProd(T,A); P = MatProd(A,A)
print("matrix TA"); MatList(Q)
print("matrix AA"); MatList(P)
print("matrix A"); MatList(A)
tl = MatProdDiag(P,S)
print("left  =",tl)
tr = MatProdDiag(S,Q)
print("right =",tr)
print("total =",VecSum(tl,tr))

ta = MatProdDiag(P,A); print("AAA =",ta)
tb = MatProdDiag(P,T); print("AAT =",tb)
tc = MatProdDiag(A,Q); print("ATA =",tc)
td = MatProdDiag(T,Q); print("TTA =",td)
print("tri =",VecSum(VecSum(ta,tb),VecSum(tc,td)))
</code>

{{notes:pics:testa.png?400}}

{{tq:pics:count.pdf|Picture of the test graph}}

<code>
matrix A
[ 1 ) = [0, 0, 0, 0, 0, 0, 0]
[ 2 ) = [1, 0, 1, 1, 0, 0, 0]
[ 3 ) = [0, 1, 0, 0, 0, 1, 0]
[ 4 ) = [1, 0, 1, 0, 1, 1, 1]
[ 5 ) = [1, 1, 0, 1, 0, 1, 0]
[ 6 ) = [0, 0, 0, 0, 1, 0, 1]
[ 7 ) = [0, 0, 1, 0, 0, 0, 0]
transposed A
[ 1 ) = [0, 1, 0, 1, 1, 0, 0]
[ 2 ) = [0, 0, 1, 0, 1, 0, 0]
[ 3 ) = [0, 1, 0, 1, 0, 0, 1]
[ 4 ) = [0, 1, 0, 0, 1, 0, 0]
[ 5 ) = [0, 0, 0, 1, 0, 1, 0]
[ 6 ) = [0, 0, 1, 1, 1, 0, 0]
[ 7 ) = [0, 0, 0, 1, 0, 1, 0]
symmetric A
[ 1 ) = [0, 1, 0, 1, 1, 0, 0]
[ 2 ) = [1, 0, 2, 1, 1, 0, 0]
[ 3 ) = [0, 2, 0, 1, 0, 1, 1]
[ 4 ) = [1, 1, 1, 0, 2, 1, 1]
[ 5 ) = [1, 1, 0, 2, 0, 2, 0]
[ 6 ) = [0, 0, 1, 1, 2, 0, 1]
[ 7 ) = [0, 0, 1, 1, 0, 1, 0]
matrix TA
[ 1 ) = [3, 1, 2, 2, 1, 2, 1]
[ 2 ) = [1, 2, 0, 1, 0, 2, 0]
[ 3 ) = [2, 0, 3, 1, 1, 1, 1]
[ 4 ) = [2, 1, 1, 2, 0, 1, 0]
[ 5 ) = [1, 0, 1, 0, 2, 1, 2]
[ 6 ) = [2, 2, 1, 1, 1, 3, 1]
[ 7 ) = [1, 0, 1, 0, 2, 1, 2]
matrix AA
[ 1 ) = [0, 0, 0, 0, 0, 0, 0]
[ 2 ) = [1, 1, 1, 0, 1, 2, 1]
[ 3 ) = [1, 0, 1, 1, 1, 0, 1]
[ 4 ) = [1, 2, 1, 1, 1, 2, 1]
[ 5 ) = [2, 0, 2, 1, 2, 1, 2]
[ 6 ) = [1, 1, 1, 1, 0, 1, 0]
[ 7 ) = [0, 1, 0, 0, 0, 1, 0]
matrix SA
[ 1 ) = [3, 1, 2, 2, 1, 2, 1]
[ 2 ) = [2, 3, 1, 1, 1, 4, 1]
[ 3 ) = [3, 0, 4, 2, 2, 1, 2]
[ 4 ) = [3, 3, 2, 3, 1, 3, 1]
[ 5 ) = [3, 0, 3, 1, 4, 2, 4]
[ 6 ) = [3, 3, 2, 2, 1, 4, 1]
[ 7 ) = [1, 1, 1, 0, 2, 2, 2]
matrix A
[ 1 ) = [0, 0, 0, 0, 0, 0, 0]
[ 2 ) = [1, 0, 1, 1, 0, 0, 0]
[ 3 ) = [0, 1, 0, 0, 0, 1, 0]
[ 4 ) = [1, 0, 1, 0, 1, 1, 1]
[ 5 ) = [1, 1, 0, 1, 0, 1, 0]
[ 6 ) = [0, 0, 0, 0, 1, 0, 1]
[ 7 ) = [0, 0, 1, 0, 0, 0, 0]
tri = [4, 6, 5, 14, 9, 7, 3] 

AAA = [0, 2, 2, 3, 2, 2, 1]
AAT = [0, 2, 0, 6, 4, 0, 0]
ATA = [0, 2, 1, 4, 2, 2, 1]
TTA = [4, 0, 2, 1, 1, 3, 1]
tri = [4, 6, 5, 14, 9, 7, 3]
</code>