/* 
   Date: 1-30-2004 
   Author: Yong Zhang
   This program is based on graph9nodev3.c.
   This program is used to find a weighted acyclic graph with
   11 vertices that satisfies the following property:
   The distances from any two vertices are all distinct and belong
   to the set {1,...,55}.
   This program can be modified to solve the similar problem for
   a bigger input.

   This is the final version of the program. 
*/

#include <stdio.h>
#include <stdlib.h>

#define FALSE 0
#define TRUE 1
#define ERROR -2

#define DIM 11 /* the dimension of the matrix */
#define PATH 55 /* the number of distinct paths */

#define min(x,y) ((x) < (y) ? (x) : (y))
#define max(x,y) ((x) > (y) ? (x) : (y))

void compute_loop();
int compute_path(int A[DIM][DIM], int B[DIM][DIM]);
int multiply_matrix(int A[DIM][DIM], int B[DIM][DIM]);
int multiply_column(int col_a[DIM], int col_b[DIM]);
int isvalid_matrix(int d[DIM][DIM]);
int nextvalue_matrix(int d[DIM][DIM]);
void copy_matrix(int A[DIM][DIM], int B[DIM][DIM]);
void print_matrix(int d[DIM][DIM]);



/*
 *********************************************************
 *                                                       *
 *   In addition to the above DIM Macro, the following   *
 *   needs to be modified when scale up the program.     *
 *                                                       *
 *********************************************************
*/


/* Here is how we match the position and the ijth entry
   of the matrix.

   The upper triangular of the original matrix:
   (0,0) (0,1) (0,2) (0,3) (0,4) (0,5) (0,6) (0,7) (0,8) (0,9) (0,10)
         (1,1) (1,2) (1,3) (1,4) (1,5) (1,6) (1,7) (1,8) (1,9) (1,10)
               (2,2) (2,3) (2,4) (2,5) (2,6) (2,7) (2,8) (2,9) (2,10)
                     (3,3) (3,4) (3,5) (3,6) (3,7) (3,8) (3,9) (3,10)
                           (4,4) (4,5) (4,6) (4,7) (4,8) (4,9) (4,10)
                                 (5,5) (5,6) (5,7) (5,8) (5,9) (5,10)
                                       (6,6) (6,7) (6,8) (6,9) (6,10)
                                             (7,7) (7,8) (7,9) (7,10)
                                                   (8,8) (8,9) (8,10)
                                                         (9,9) (9,10)
                                                              (10,10)

  and the corresponding position:

  # 0  1  2  3  4  5  6  7  8  9 
    # 10 11 12 13 14 15 16 17 18
       # 19 20 21 22 23 24 25 26
          # 27 28 29 30 31 32 33
             # 34 35 36 37 38 39
                # 40 41 42 43 44
                   # 45 46 47 48
                      # 49 50 51
                         # 52 53
                            # 54
                               #

*/

/* the pos_i and pos_j array serves as a lookup table which maps
   {0,...,54} to i'th entry and j'th entry of the matrix */ 
int pos_i[PATH]={0,0,0,0,0,0,0,0,0,0,1,
	       1,1,1,1,1,1,1,1,2,2,2,
	       2,2,2,2,2,3,3,3,3,3,3,
	       3,4,4,4,4,4,4,5,5,5,5,
	       5,6,6,6,6,7,7,7,8,8,9};
int pos_j[PATH]={1,2,3,4,5,6,7,8,9,10,2,
	       3,4,5,6,7,8,9,10,3,4,5,
	       6,7,8,9,10,4,5,6,7,8,9,
	       10,5,6,7,8,9,10,6,7,8,9,
	       10,7,8,9,10,8,9,10,9,10,10};



/* the num array was used by isvalid_matrix() */
int num[PATH+1];

/* initiate the input matrix */
int m1[DIM][DIM]={
    {0,1,-1,-1,-1,-1,-1,-1,-1,-1,-1},
    {1,0,-1,-1,-1,-1,-1,-1,-1,-1,-1},
    {-1,-1,0,-1,-1,-1,-1,-1,-1,-1,-1},
    {-1,-1,-1,0,-1,-1,-1,-1,-1,-1,-1},
    {-1,-1,-1,-1,0,-1,-1,-1,-1,-1,-1},
    {-1,-1,-1,-1,-1,0,-1,-1,-1,-1,-1},
    {-1,-1,-1,-1,-1,-1,0,-1,-1,-1,-1},
    {-1,-1,-1,-1,-1,-1,-1,0,-1,-1,-1},
    {-1,-1,-1,-1,-1,-1,-1,-1,0,-1,-1},
    {-1,-1,-1,-1,-1,-1,-1,-1,-1,0,-1},
    {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,0}
  }; 


/* in every loop we need to save the intermediate matrix */
int m2[DIM][DIM], m3[DIM][DIM],m4[DIM][DIM],m5[DIM][DIM];
int m6[DIM][DIM], m7[DIM][DIM],m8[DIM][DIM],m9[DIM][DIM];
int m10[DIM][DIM], result[DIM][DIM];

/* these matrices will store the intermediate path matrices calculated from
   the corresponding adjancency matrices */
int m2_path[DIM][DIM], m3_path[DIM][DIM],m4_path[DIM][DIM],m5_path[DIM][DIM];
int m6_path[DIM][DIM], m7_path[DIM][DIM],m8_path[DIM][DIM],m9_path[DIM][DIM];




/* positions of ten edges */
int p1,p2,p3,p4,p5,p6,p7,p8,p9,p10;

/* weights of ten edges */
int v1,v2,v3,v4,v5,v6,v7,v8,v9,v10;


int main(int argc, char *argv[])
{
  int i;

  system("date");

  /* initiate the num array */
  for (i=0;i<PATH+1;i++)
    num[i]=0;

  /* assign the first edge and weight, in fact we don't 
     need to use them, it is included in the input matrix,
     we state them here for the sake of clearance */
  p1=0;
  v1=1;

  /* In fact, p2 only needs to be 1 or 19, v2 is 2. */ 
  p2=1;
  v2=2;

  /* make a new copy of input matrix */
  copy_matrix(m2,m1);

  /* assign v2 to given location p2 */
  m2[0][2]=v2;
  m2[2][0]=v2;

  /* compute all paths */
  compute_path(m2_path,m2);

  /* compute the next possible weight value */
  v3=nextvalue_matrix(m2_path);

  for (p3=1;p3<PATH;p3++)
    {
      int i3,j3;

      /* p3 only needs to be 2,11,19 or 27 */
      if (p3!=2 && p3!=11 && p3!=19 && p3!=27)
	continue;

      /* if we already have a path, then fail */
      i3=pos_i[p3];
      j3=pos_j[p3];
      if (m2_path[i3][j3]>0) 
	continue;

      /* make a new copy of m2 */
      copy_matrix(m3,m2);

      /* assign the third value */
      m3[i3][j3]=v3;
      m3[j3][i3]=v3;

      /* compute all paths */
      if (compute_path(m3_path,m3)==ERROR) 
	continue;

      if ((v4=nextvalue_matrix(m3_path))==ERROR)
	continue;

      if (p3==2)
	{
	  for (p4=1;p4<PATH;p4++)
	    {
	      /* when p3 is 2, p4 can only be 3,12,20,27,34 */
	      if (p4!=3 && p4!=12 && p4!=20 && p4!=27 && p4!=34)
		continue;

	      system("date");
	      printf("p1=%d p2=%d p3=%d p4=%d\n", p1,p2,p3,p4);
	      
	      /* do the rest */
	      compute_loop();
	    }
	}
      else if (p3==11)
	{
	  for (p4=1;p4<PATH;p4++)
	    {
	      /* when p3 is 11, p4 can only be 3,12,20,27,34 */
	    if (p4!=3 && p4!=12 && p4!=20 && p4!=27 && p4!=34)
	      continue;

	    system("date");
	    printf("p1=%d p2=%d p3=%d p4=%d\n", p1,p2,p3,p4);
	  
	    /* do the rest */
	    compute_loop();
	  }
	}
      else if (p3==19)
	{
	  for (p4=1;p4<PATH;p4++)
	    {
	      /* when p3 is 19, p4 can only be 3,12,20,27,34 */
	    if (p4!=3 && p4!=12 && p4!=20 && p4!=27 && p4!=34)
	      continue;
	  
	    system("date");
	    printf("p1=%d p2=%d p3=%d p4=%d\n", p1,p2,p3,p4);

	    /* do the rest */
	    compute_loop();
	  }
	}
      else if (p3==27)
	{
	  for (p4=1;p4<PATH;p4++)
	    {
	      /* when p3 is 27, p4 can only be 2,4,11,13,19,21,28,40 */
	    if (p4!=2 && p4!=4 && p4!=11 && p4!=13 && p4!=19 && p4!=21 && p4!=28 && p4!=40)
	      continue;
	  
	    system("date");
	    printf("p1=%d p2=%d p3=%d p4=%d\n", p1,p2,p3,p4);

	    /* do the rest */
	    compute_loop();
	  }
	}
    }

  system("date");	  
  printf("half\n");

  /* the other value of p2,p2=19, v2 is 2. */ 
  p2=19;
  v2=2;

  /* make a new copy of input matrix */
  copy_matrix(m2,m1);

  /* assign v2 to given location p2 */
  m2[2][3]=v2;
  m2[3][2]=v2;

  /* compute all paths */
  compute_path(m2_path,m2);

  /* when p2=19, v3 has to be 3 */
  v3=nextvalue_matrix(m2_path);

  for (p3=1;p3<PATH;p3++)
    {
      int i3,j3; 

     /* p3 only needs to be 1,3,20,34 */
      if (p3!=1 && p3!=3 && p3!=20 && p3!=34)
	continue;

      /* if we already have a path, then fail */
      i3=pos_i[p3];
      j3=pos_j[p3];
      if (m2_path[i3][j3]>0) 
	continue;

      /* make a new copy of m2 */
      copy_matrix(m3,m2);

      /* assignment the third value */
      m3[i3][j3]=v3;
      m3[j3][i3]=v3;
      
      /* compute all paths */
      if (compute_path(m3_path,m3)==ERROR) 
	continue;

      if ((v4=nextvalue_matrix(m3_path))==ERROR)
	continue;

      if (p3==1)
	{
	  for (p4=1;p4<PATH;p4++)
	    {
	      /* when p3 is 1, p4 can only be 3,12,20,27,34 */
	      if (p4!=3 && p4!=12 && p4!=20 && p4!=27 && p4!=34)
		continue;
	      
	      system("date");
	      printf("p1=%d p2=%d p3=%d p4=%d\n", p1,p2,p3,p4);

	      /* do the rest */
	      compute_loop();
	    }
	}
      else if (p3==3)
	{
	  for (p4=1;p4<PATH;p4++)
	    {
	      /* when p3 is 3, p4 can only be 1,4,10,13,20,21,34,40 */
	    if (p4!=1 && p4!=4 && p4!=10 && p4!=13 && p4!=20 && p4!=21 && p4!=34 && p4!=40)
	      continue;

	    system("date");
	    printf("p1=%d p2=%d p3=%d p4=%d\n", p1,p2,p3,p4);
	  
	    /* do the rest */
	    compute_loop();
	  }
	}
      else if (p3==20)
	{
	  for (p4=1;p4<PATH;p4++)
	    {
	      /* when p3 is 20, p4 can only be 1,2,3,4,21,28,34,40 */ 
	    if (p4!=1 && p4!=2 && p4!=3 && p4!=4 && p4!=21 && p4!=28 && p4!=34 && p4!=40)
	      continue;

	    system("date");
	    printf("p1=%d p2=%d p3=%d p4=%d\n", p1,p2,p3,p4);
	  
	    /* do the rest */
	    compute_loop();
	  }
	}
      else if (p3==34)
	{
	  for (p4=1;p4<PATH;p4++)
	    {
	      /* when p3 is 34, p4 can only be 1,3,5,20,22,35,45 */
	    if (p4!=1 && p4!=3 && p4!=5 && p4!=20 && p4!=22 && p4!=35 && p4!=45)
	      continue;

	    system("date");
	    printf("p1=%d p2=%d p3=%d p4=%d\n", p1,p2,p3,p4);
	  
	    /* do the rest */
	    compute_loop();
	  }
	}
    }
  
  system("date");	  
  printf("done\n");
  
}


/*
  This routine computes all the rest of the loops.
*/
void compute_loop(){
  
  int i4,j4;
  /* if we already have a path, then fail */
  i4=pos_i[p4];
  j4=pos_j[p4];
  if (m3_path[i4][j4]>0) 
    return;

  /* make a new copy of m3 */
  copy_matrix(m4,m3);

  /*assign the fourth value */
  m4[i4][j4]=v4;
  m4[j4][i4]=v4;

  /* compute all paths */
  if (compute_path(m4_path,m4)==ERROR) 
    return;

  /* calculate the next value */
  if ((v5=nextvalue_matrix(m4_path))==ERROR)
    return;

  for (p5=1;p5<PATH;p5++)
    {
      int i5,j5;

      /* make sure p5 is a distinct location */
      if (p5==p2 || p5==p3 || p5==p4) 
	continue;

      /* if we already have a path, then fail */
      i5=pos_i[p5];
      j5=pos_j[p5];
      if (m4_path[i5][j5]>0) 
	continue;
	      
      /* make a new copy of m4 */
      copy_matrix(m5,m4);
	      
      /* assign the fifth value */
      m5[i5][j5]=v5;
      m5[j5][i5]=v5;

      /* compute all paths */
      if (compute_path(m5_path,m5)==ERROR) 
	continue;

      /* calculate the next value */
      if ((v6=nextvalue_matrix(m5_path))==ERROR)
	continue;
	      
      for (p6=1;p6<PATH;p6++)
	{
	  int i6,j6;

	  /* make sure p6 is a distinct location */
	  if (p6==p2 || p6==p3 || p6==p4 || p6==p5) 
	    continue;
		  
	  /* if we already have a path, then fail */
	  i6=pos_i[p6];
	  j6=pos_j[p6];
	  if (m5_path[i6][j6]>0) 
	    continue;
	      
	  /* make a new copy of m5 */
	  copy_matrix(m6,m5);
	      
	  /* assign the sixth value */
	  m6[i6][j6]=v6;
	  m6[j6][i6]=v6;

	  /* compute all paths */
	  if (compute_path(m6_path,m6)==ERROR) 
	    continue;

	  /* calculate the next value */
	  if ((v7=nextvalue_matrix(m6_path))==ERROR)
	    continue;

		  
	  for (p7=1;p7<PATH;p7++)
	    {
	      int i7,j7;

	      /* make sure p7 is a distinct location */
	      if (p7==p2 || p7==p3 || p7==p4 || p7==p5 || p7==p6) 
		continue;

	      /* if we already have a path, then fail */
	      i7=pos_i[p7];
	      j7=pos_j[p7];
	      if (m6_path[i7][j7]>0) 
		continue;
	      
	      /* make a new copy of m6 */
	      copy_matrix(m7,m6);
	      
	      /* assign the seventh value */
	      m7[i7][j7]=v7;
	      m7[j7][i7]=v7;

	      /* compute all paths */
	      if (compute_path(m7_path,m7)==ERROR) 
		continue;

	      /* calculate the next value */
	      if ((v8=nextvalue_matrix(m7_path))==ERROR)
		continue;
		      
	      for (p8=1;p8<PATH;p8++)
		{
		  int i8,j8;

		  /* make sure p8 is a distinct location */
		  if (p8==p2 || p8==p3 || p8==p4 || p8==p5 || p8==p6 || p8==p7) 
		    continue;

		  /* if we already have a path, then fail */
		  i8=pos_i[p8];
		  j8=pos_j[p8];
		  if (m7_path[i8][j8]>0) 
		    continue;
	      
		  /* make a new copy of m7 */
		  copy_matrix(m8,m7);
	      
		  /* assign the eighth value */
		  m8[i8][j8]=v8;
		  m8[j8][i8]=v8;

		  /* compute all paths */
		  if (compute_path(m8_path,m8)==ERROR) 
		    continue;

		  /* calculate the next value */
		  if ((v9=nextvalue_matrix(m8_path))==ERROR)
		    continue;

		  for (p9=1;p9<PATH;p9++)
		    {
		      int i9,j9;

		      /* make sure p9 is a distinct location */
		      if (p9==p2 || p9==p3 || p9==p4 || p9==p5 || p9==p6 || p9==p7 || p9==p8) 
			continue;

		      /* if we already have a path, then fail */
		      i9=pos_i[p9];
		      j9=pos_j[p9];
		      if (m8_path[i9][j9]>0) 
			continue;
	      
		      /* make a new copy of m8 */
		      copy_matrix(m9,m8);
	      
		      /* assign the ninth value */
		      m9[i9][j9]=v9;
		      m9[j9][i9]=v9;

		      /* compute all paths */
		      if (compute_path(m9_path,m9)==ERROR) 
			continue;

		      /* calculate the next value */
		      if ((v10=nextvalue_matrix(m9_path))==ERROR)
			continue;

		      for (p10=1;p10<PATH;p10++)
			{
			  int i10,j10;

			  /* make sure p10 is a distinct location */
			  if (p10==p2 || p10==p3 || p10==p4 || p10==p5 || p10==p6 || p10==p7 || p10==p8 || p10==p9) 
			    continue;

			  /* if we already have a path, then fail */
			  i10=pos_i[p10];
			  j10=pos_j[p10];
			  if (m9_path[i10][j10]>0) 
			    continue;

			  /* make a new copy of m9 */
			  copy_matrix(m10,m9);

			  /* assign the tenth value */
			  m10[i10][j10]=v10;
			  m10[j10][i10]=v10;
			  
			  /* compute all paths */
			  if (compute_path(result,m10)==ERROR)
			    continue;
			  
			  /* check if it is the desired matrix */
			  if (isvalid_matrix(result)) 
			    {
			      printf("found!\n");
			      print_matrix(m10);
			      print_matrix(result);
			      return;
			    }
			}
		    }
		}
	    }
	}
    }
}
	



/*
 *********************************************************
 *                                                       *
 *   Routines that scale up.                             *
 *                                                       *
 *********************************************************
 Note: assign_value() was changed to work with the new 
       lookup table pos_i and pos_j.
*/


/*
  Given the adjancency matrix B as input, this routine will 
  output A the weight of all paths between any two vertices
  using all-pair shortest path algoritm. The return value 
  is used to propagate the error up. If it returns ERROR, 
  there is a cycle in the graph.
*/
int compute_path(int A[DIM][DIM], int B[DIM][DIM])
{
  int i,val;
  copy_matrix(A, B);

  /* multiply matrix DIM-1 times */
  for (i=1;i<DIM;i++)
    {
      val=multiply_matrix(A,B);
      /* if error, then propogate the error up. */
      if (val==ERROR)
	return ERROR;
      else if(val==FALSE)
	break; 
    }

  return TRUE;
}


/*
  Do the matrix multiplication and store the result in A.
  Please note that the multiplication is not the usual
  matrix multiplication. The return value is used to propagate 
  the error up. If it returns ERROR, there is a cycle in the
  graph. If it returns FALSE, no work is done, i.e., A remains
  the same. Otherwise, it returns TRUE.
*/
int multiply_matrix(int A[DIM][DIM], int B[DIM][DIM])
{
  /* declare a tmp matrix to store the result */
  int i,j,tmp[DIM][DIM];

  /* set flag to 0, this flag is to indicate if we did some
   useful work. */
  int flag=FALSE;

  copy_matrix(tmp,A);

  /* calculate the result */
  for (i=0; i<DIM-1; i++)
    for (j=i+1; j<DIM; j++)
      {
	/* since the graph is acyclic, the path between any 
	   two vertices is unique */
	if (tmp[i][j]!=-1) 
	  continue;

	tmp[i][j]=multiply_column(A[i],B[j]);

	/* if error, then propogate the error up, if we did
	 some useful work, set flag to TRUE. */
	if (tmp[i][j]==ERROR) 
	  return ERROR;
	else if(tmp[i][j]!=-1)
	  flag=TRUE;

	tmp[j][i]=tmp[i][j];
      }

  /* copy the result back to A */
  copy_matrix(A,tmp);
  return flag;
}


/*
  This routine is used by multiply_matrix() to calculate
  the multiplication of two rows. (In fact one row and one
  column, but here the matrix is symmetric.)
*/
int multiply_column(int row_a[DIM], int row_b[DIM])
{
  /* initialize result to be some impossible value */
  int i,result=-1;

  /* The multiplication we define is to add the two rows
     component-wise and take the minimum. */
  for (i=0;i<DIM;i++){
    /* If either one is -1, i.e., the two vertices are not 
       connected, then skip. */
    if (row_a[i]<=0 || row_b[i]<=0) continue;

    if (result==-1)
      result=row_a[i]+row_b[i];
    /* if there is a cycle in the graph, return some impossible
       value to indicate error. */
    else
      return ERROR;
  }
  return result;
}


/*
  The routine is used to check if the given matrix is
  what we want, i.e., the upper triangular contains 
  integers from 1 to DIM choose 2.
*/
int isvalid_matrix(int d[DIM][DIM])
{
  int i,j;

  /* initiate the num array first */
  for (i=0;i<PATH+1;i++)
    num[i]=0;

  for (i=0; i<DIM-1; i++)
    for (j=i+1; j<DIM; j++)
      {
	/* if there is no path between i and j, or the weight is bigger
	   desired value, fail */
	if (d[i][j]==-1 || d[i][j]>PATH) return FALSE;
	/* if there are two path of the same weight, fail */
	if (num[d[i][j]]!=0) return FALSE;
	/* otherwise put the weight in the array */
	num[d[i][j]]=d[i][j];
      }  
  return TRUE;
}




/*
  This routine is used to find the next value we should assign
  to the input matrix, which is the smallest integer that
  can not be found in the given matrix. 
*/
int nextvalue_matrix(int d[DIM][DIM])
{
  int i,j;

  /* find the next value, which is the smallest integer that can not
     be found in the tmp matrix */
  /* initiate the num array first */
  for (i=0;i<PATH+1;i++)
    num[i]=0;

  /* put the positive values in d matrix in the num[] array */
  for (i=0; i<DIM-1; i++)
    for (j=i+1; j<DIM; j++)
      {
	if (d[i][j]<0) 
	  continue;
	/* if we found a large path, fail */
	else if (d[i][j]>PATH) 
	  return ERROR;
	/* if we find two paths of the same weight, fail */
	else if (num[d[i][j]]!=0)
	  return ERROR;
	else
	  num[d[i][j]]=d[i][j];
      }

  /* return the smallest integer that is not in the d matrix */
  for (i=2;i<PATH+1;i++)
    {
      if (num[i]==0)
	return i;
    }
  return 0;
}


/*
  Printout the content of the given matrix. Mainly for 
  purpose of debug.
*/
void print_matrix(int d[DIM][DIM])
{ 
  int i,j;
  for (i=0;i<DIM;i++){
    for (j=0;j<DIM;j++)
      printf("%d   ", d[i][j]);
    printf("\n");
  }
  printf("\n");
}


/*
  This routine is used to copy matrix B into matrix A.
*/
void copy_matrix(int A[DIM][DIM], int B[DIM][DIM])
{
  int i,j;
  for (i=0;i<DIM;i++)
    for (j=0;j<DIM;j++)
      A[i][j]=B[i][j];
}