/* Matrix Math in Java */

import java.lang.Math;   // needed for random numbers.

/* Matrices are represented as two-dimensional arrays.  We shall confine
   ourselfs to square (NXN) matrices for simplicity.  All binary relations
   that has the same domain as range are square matrices */

public class mmx
{
static  matrix madd(matrix A, matrix B)
    {   int i, j;	// loop counters
 	matrix C = new matrix(A.size);  
        for (i=0;i<A.size;i++)
	  for(j=0;j<A.size;j++)
	    C.m[i][j] = A.m[i][j] + B.m[i][j];
        return C;
    }

// mmult assumes both matrices are square and of the same dimensions  
static  matrix mmult(matrix A, matrix B)
    {   int i, j, k;	// loop counters
        int ax; 	// accumulator for matrix multiplication
	matrix C = new matrix(A.size);
	for (i=0;i<A.size;i++)
	  for(j=0;j<A.size;j++)
	    { 
	      ax = 0; 	// reset accumulator
	      for(k=0;k<A.size;k++)
		ax = ax + (A.m[i][k] * B.m[k][j]);
	      C.m[i][j] = ax;
	    }	
	return C;
    }

// mcomp just calls mmult, then binarize the matrix.
static  matrix mcomp(matrix A, matrix B)   // binary matrix composition
    {   matrix C;
        C = mmult(A,B);
	C.binarize();
        return C;
    }

// finds transitive closure: A+AXA+AXAXA+...
static  matrix transclosure(matrix M)
    {   int i;	// loop counter
	matrix AX = M;     // accumulator matrix
        for(i=0;i<M.size;i++)
	  {  
	     AX = madd(AX, mcomp(AX,M));
             AX.binarize();
          }
	return AX;
    }

// determines if there are cycles in a graph:
static  boolean cyclic(matrix A)
    {	int i = 0;
        matrix B = transclosure(A);  
        boolean ax = false;
	while ((i<A.size) && (!ax)) 
	   { ax = ax || (B.m[i][i] == 1);  i++; }
        return ax;
    }

	       
public static void main(String[] args)
{  matrix A, B, C;

   A = new matrix(4);

   A.m[0][1]=1;
   A.m[0][3]=1;
   A.m[1][2]=1;
   A.m[1][3]=1;
   A.m[2][1]=1;
   A.m[2][3]=1;
   A.m[3][1]=1;

   A.printmatrix();

   B = mmult(A,A);
   B.printmatrix();

   B = mmult(B,A);
   B.printmatrix();
   
   System.out.println("the transclosure:\n");
   transclosure(A).printmatrix();
/*
   A = new matrix(3);
   A.m[0][0] = 1;
   A.m[0][1] = 1;
   A.m[1][0] =1 ;
   A.m[1][1] = 1;
   A.m[2][2] = 1;
  
   B = new matrix(3);
   B.m[0][0] = 1;
   B.m[1][1] = 1;
   B.m[1][2] = 1;
   B.m[2][1] = 1;
   B.m[2][2] = 1;

   A.printmatrix();
   B.printmatrix();
 
   System.out.println("matrix A o B:\n");
   mcomp(A,B).printmatrix();

   A = new matrix(3);
   B = new matrix(3);

   A. randomize();
   B. randomize();
System.out.println("matrix A:\n");
   A.printmatrix();
System.out.println("matrix B:\n");
   B.printmatrix();

   C = mmult(A,B);
System.out.println("matrix AXB:\n");
   C.printmatrix();

System.out.println("matrix transclosure(A):\n");
   transclosure(A).printmatrix();


   B = new matrix(5);
   B.m[0][2] = 1;    // all other entries are 0's by default.
   B.m[1][4] = 1;
   B.m[2][4] = 1;
   B.m[4][3] = 1;
System.out.println("Really Sparse Matrix:\n");
   B.printmatrix();
   B = transclosure(B);
System.out.println("Transitive closure not as sparse as before:\n");
   B.printmatrix();


*/
}	     


}  // end of main class mmx


class matrix
{
  int[][] m;   // The matrix itself.
  int size;  

  matrix(int dimension) { m = new int[dimension][dimension];
			  size = dimension; }

  void printmatrix()
    {   int i, j;	// loop counters
	for (i=0;i<size;i++)
          { for(j=0;j<size;j++)   // print ith row
		System.out.print(m[i][j] + "  ");
	    System.out.println("");    // print cr between rows
	  }
        System.out.println(""); // extra cr when done
    }

  void reset()        // resets all matrix cells to 0
     {  int i, j;
	for (i=0;i<size;i++)
	  for(j=0;j<size;j++)
	      m[i][j] = 0;
     }

  void randomize()    // puts random numbers in the matrix
    {   int i, j;
	for (i=0;i<size;i++)
	  for(j=0;j<size;j++)
	      m[i][j] = (int) (Math.random() * 4);
/* (int) (Math.random() * 3) returns random number between 0 and 2 */
    }

/* binarize flattens everything to 0 or 1: */
  void binarize()
    {   int i, j;
	for (i=0;i<size;i++)
	  for(j=0;j<size;j++)
	    if (m[i][j] > 0) m[i][j] = 1; else m[i][j] = 0;
    }

  boolean equals(matrix A)
    {   int i, j;
	boolean ax = true;
	for (i=0;i<size;i++)
	  for(j=0;j<size;j++)
		{ ax = ax && (m[i][j] == A.m[i][j]);
 		  if (!(ax)) { i = size; j = size; }  // terminate loop
                }
	return ax;
    }

}