/*****************************************************************/
/*                                                               */
/* Program to create random directed graphs                      */
/*                                                               */
/* Output of this program is input for the program to create     */
/* directed graphs                                               */
/*                                                               */
/* Author: Frederico R. B. da Cruz                               */
/*         Department of Industrial Engineering and              */
/*         Operations Research                                   */
/*         University of Massachusetts at Amherst                */
/*         USA                                                   */
/*                                                               */
/* E-mail: fcruz@sml1.ecs.umass.edu                              */
/*                                                               */
/* Version: 2.00                                                 */
/*                                                               */
/* Date: Nov./95                                                 */
/*                                                               */
/*****************************************************************/

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

#include "ty.h"
#include "ur.c"


float Distance (float             x1,
                float             y1,
                float             x2,
                float             y2);

int ValidArc   (ListArcPtrType    *AdjaNodInd,
                ArcPtrType        ArcPtr);

int ValidNode  (int               n_Levels,
                ListNodPtrType    *RootNodLev,
                ListNodPtrType    *DemaNodLev,
                NodPtrType        NodPtr);


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

  typedef struct {
                  float    Coord_x;
                  float    Coord_y;
                 } Coordinates;

  Coordinates       *Coords;
  int               *InTree;
  ListArcPtrType    *AdjaNodInd, ListArcPtr, ListArcAux;
  ListNodPtrType    *DemaNodLev, ListNodPtr, ListNodAux;
  ListNodPtrType    *RootNodLev;
  ArcPtrType        *ArcPtr;
  NodPtrType        NodPtr;
  ArcType           Arc;
  int               Seed;
  int               n_Nodes, n_Levels, n_Arcs,
                    *n_RootLevel, *n_DemandLevel;
  int               i, l;

  /*  read data  */
  if ( argc < 5 ) {
    fprintf(ERRFILE,
    "Usage: crg SEED |N| |A| m |R^1| |D^1| ... |R^m| |D^m|\n");
     exit(0);
  }

  sscanf(argv[4], "%d", &n_Levels);
  if ( argc < ( 2 * n_Levels + 5 ) ) {
    fprintf(ERRFILE,
    "Usage: crg SEED |N| |A| m |R^1| |D^1| ... |R^m| |D^m|\n");
     exit(0);
  }

  sscanf(argv[1], "%d", &Seed);
  sscanf(argv[2], "%d", &n_Nodes);
  sscanf(argv[3], "%d", &n_Arcs);
  n_RootLevel = (int *) calloc( n_Levels, sizeof(int) );
  n_DemandLevel = (int *) calloc( n_Levels, sizeof(int) );
  for ( i = 0; i < n_Levels; i++ ) {
      sscanf(argv[2*i+5], "%d", &n_RootLevel[i] );
      sscanf(argv[2*i+6], "%d", &n_DemandLevel[i] );
  }

  if ( n_Arcs < ( 2*(n_Nodes-1) ) )
     n_Arcs = 2*(n_Nodes-1);
  else if ( n_Arcs > ( n_Nodes*(n_Nodes-1) ) )
     n_Arcs = n_Nodes * (n_Nodes-1);

  /*  randomize coodinates  */
  Coords  = (Coordinates *) calloc( n_Nodes, sizeof(Coordinates) );
  InTree = (int *) calloc( n_Nodes, sizeof(int) );
  for ( i = 0; i < n_Nodes; i++ ) {
      Coords[i].Coord_x = 100 * urand( &Seed );
      Coords[i].Coord_y = 100 * urand( &Seed );
      InTree[i]   = NO;
  }

  /*  create a random connected graph  */
  AdjaNodInd = (ListArcPtrType *) calloc( n_Nodes, sizeof(ListArcPtrType) );
  for ( i = 0; i < n_Nodes; i++) { 
      AdjaNodInd[i] = (ListArcPtrType) malloc( sizeof(ListArcType) );
      AdjaNodInd[i]->APtr = NULL;
      AdjaNodInd[i]->Next = NULL;
  }
  Arc.i = ( int ) ( urand( &Seed ) * n_Nodes );
  InTree[Arc.i] = YES;
  for ( i = 0; i < n_Arcs; i += 2 ) {
      if ( i < 2*(n_Nodes-1) ) {
         do {
            Arc.i = ( int ) ( urand( &Seed ) * n_Nodes);
         } while ( InTree[Arc.i] != YES ) ;
         do {
            Arc.j = ( int ) ( urand( &Seed ) * n_Nodes);
         } while ( InTree[Arc.j] != NO );
         InTree[Arc.j] = YES;
      }
      else {
         do {
            Arc.i = ( int ) ( urand( &Seed ) * n_Nodes );
            Arc.j = ( int ) ( urand( &Seed ) * n_Nodes );
         } while ( ValidArc( AdjaNodInd, &Arc ) == NO );
      }

      /*  A = A U (i,j)  */
      ArcPtr = (ArcPtrType *) calloc( 1, sizeof(ArcPtrType) );
      ArcPtr[0] = (ArcPtrType) malloc( sizeof(ArcType) );
      ArcPtr[0]->i = Arc.i;
      ArcPtr[0]->j = Arc.j;
      ArcPtr[0]->fij = Distance(Coords[ArcPtr[0]->i].Coord_x, 
                                Coords[ArcPtr[0]->i].Coord_y,
                                Coords[ArcPtr[0]->j].Coord_x, 
                                Coords[ArcPtr[0]->j].Coord_y );
          /*  find position  */
      ListArcAux = AdjaNodInd[ArcPtr[0]->i];
      while ( ( ListArcAux->Next != NULL ) &&
              ( ListArcAux->Next->APtr[0]->j < ArcPtr[0]->j ) )
            ListArcAux = ListArcAux->Next;
          /*  insert new element  */
      ListArcPtr = (ListArcPtrType) malloc( sizeof(ListArcType) );
      ListArcPtr->APtr = ArcPtr;
      ListArcPtr->Next = ListArcAux->Next;
      ListArcAux->Next = ListArcPtr;

      /*  A = A U (j,i)  */
      ArcPtr = (ArcPtrType *) calloc( 1, sizeof(ArcPtrType) );
      ArcPtr[0] = (ArcPtrType) malloc( sizeof(ArcType) );
      ArcPtr[0]->i = Arc.j;
      ArcPtr[0]->j = Arc.i;
      ArcPtr[0]->fij = Distance(Coords[ArcPtr[0]->i].Coord_x,
                                Coords[ArcPtr[0]->i].Coord_y,
                                Coords[ArcPtr[0]->j].Coord_x,
                                Coords[ArcPtr[0]->j].Coord_y );
          /*  find position  */
      ListArcAux = AdjaNodInd[ArcPtr[0]->i];
      while ( ( ListArcAux->Next != NULL ) &&
              ( ListArcAux->Next->APtr[0]->j < ArcPtr[0]->j ) )
            ListArcAux = ListArcAux->Next;
          /*  insert new element  */
      ListArcPtr = (ListArcPtrType) malloc( sizeof(ListArcType) );
      ListArcPtr->APtr = ArcPtr;
      ListArcPtr->Next = ListArcAux->Next;
      ListArcAux->Next = ListArcPtr;
  }

  /*  initialize arrays  */
  RootNodLev = (ListNodPtrType *) calloc(n_Levels+1, sizeof(ListNodPtrType));
  for ( l = 0; l < n_Levels+1; l++) {
      RootNodLev[l] = (ListNodPtrType) malloc( sizeof(ListNodType) );
      RootNodLev[l]->Next = NULL;
  }
  DemaNodLev = (ListNodPtrType *) calloc(n_Levels, sizeof(ListNodPtrType) );
  for ( l = 0; l < n_Levels; l++) {
    DemaNodLev[l] = (ListNodPtrType) malloc( sizeof(ListNodType) );
    DemaNodLev[l]->Next = NULL;
  }

  for ( l = 0; l < n_Levels; l++) {
      /*  create random supply nodes  */
      for ( i = 0; i < n_RootLevel[l]; i++ ) {
          /*  randomize node  */
          NodPtr = (NodPtrType) malloc( sizeof(NodType) );
          do {
             NodPtr->i = ( int ) ( urand( &Seed ) * n_Nodes );
          } while ( ValidNode(n_Levels,RootNodLev,DemaNodLev,NodPtr) == NO );
          /*  find position  */
          ListNodAux = RootNodLev[l];
          while ( (ListNodAux->Next != NULL) &&
                  (ListNodAux->Next->NPtr->i < NodPtr->i) )
                ListNodAux = ListNodAux->Next;
          /*  insert new element  */
          ListNodPtr = (ListNodPtrType) malloc( sizeof(ListNodType) );
          ListNodPtr->NPtr = NodPtr;
          ListNodPtr->Next = ListNodAux->Next;
          ListNodAux->Next = ListNodPtr;
      }
  
      /*  create random demand nodes  */
      for ( i = 0; i < n_DemandLevel[l]; i++ ) {
          /*  randomize node  */
          NodPtr = (NodPtrType) malloc( sizeof(NodType) );
          do {
             NodPtr->i = ( int ) ( urand( &Seed ) * n_Nodes );
          } while ( ValidNode(n_Levels,RootNodLev,DemaNodLev,NodPtr) == NO );
          NodPtr->di = 1;
          /*  find position  */
          ListNodAux = DemaNodLev[l];
          while ( (ListNodAux->Next != NULL) &&
                  (ListNodAux->Next->NPtr->i < NodPtr->i) )
                ListNodAux = ListNodAux->Next;
          /*  insert new element  */
          ListNodPtr = (ListNodPtrType) malloc( sizeof(ListNodType) );
          ListNodPtr->NPtr = NodPtr;
          ListNodPtr->Next = ListNodAux->Next;
          ListNodAux->Next = ListNodPtr;
      }
  }

  /*  releasing unused vector  */
  free(n_RootLevel);
  free(n_DemandLevel);
  free(Coords);
  free(InTree);

  /*  write problem and free variables  */
  fprintf(OUTFILE,"Number of nodes\n");
  fprintf(OUTFILE,"%4d\n", n_Nodes);
  fprintf(OUTFILE,"Number of levels\n");
  fprintf(OUTFILE,"%4d\n", n_Levels);
  fprintf(OUTFILE,"Arcs\n");
  fprintf(OUTFILE,"Orig Dest Length\n");
  for ( i = 0; i < n_Nodes; i++ ) {
      ListArcPtr = AdjaNodInd[i]->Next;
      while ( ListArcPtr != NULL ) {
         fprintf(OUTFILE, "%4d %4d %6.0f\n",
                           ListArcPtr->APtr[0]->i+1,
                           ListArcPtr->APtr[0]->j+1,
                           ListArcPtr->APtr[0]->fij );
         ListArcAux = ListArcPtr;
         ListArcPtr = ListArcPtr->Next;

         free(ListArcAux->APtr[0]);
         free(ListArcAux->APtr);
         free(ListArcAux);
      }
      free(AdjaNodInd[i]);
  }
  free(AdjaNodInd);

  fprintf(OUTFILE,"Supplying nodes\n");
  fprintf(OUTFILE,"Index Level\n");
  for ( l = 0; l < n_Levels; l++ ) {
      ListNodPtr = RootNodLev[l]->Next;
      while ( ListNodPtr != NULL ) {
         fprintf(OUTFILE, " %4d  %4d\n",
                 ListNodPtr->NPtr->i+1, 
                                   l+1);
         ListNodAux = ListNodPtr;
         ListNodPtr = ListNodPtr->Next;

         free(ListNodAux->NPtr);
         free(ListNodAux);
      }
      free(RootNodLev[l]);
  }
  free(RootNodLev);

  fprintf(OUTFILE,"Demand nodes\n");
  fprintf(OUTFILE,"Index Level     di\n");
  for ( l = 0; l < n_Levels; l++ ) {
      ListNodPtr = DemaNodLev[l]->Next;
      while ( ListNodPtr != NULL ) {
         fprintf(OUTFILE, " %4d  %4d %6.0f\n",
                 ListNodPtr->NPtr->i+1,
                                   l+1,
                 ListNodPtr->NPtr->di  );
         ListNodAux = ListNodPtr;
         ListNodPtr = ListNodPtr->Next;

         free(ListNodAux->NPtr);
         free(ListNodAux);
      }
      free(DemaNodLev[l]);
  }
  free(DemaNodLev);
  return(0);
}

float Distance (float             x1,
                float             y1,
                float             x2,
                float             y2)
{
     return( sqrt( (x2-x1)*(x2-x1) + (y2-y1)*(y2-y1) ) );
}

int ValidArc   (ListArcPtrType    *AdjaNodInd,
                ArcPtrType        ArcPtr)
{
   ListArcPtrType   ListArcPtr;

    if ( ArcPtr->i == ArcPtr->j )
       return ( NO );
    else {
/* ListArcPtr = AdjaNodInd[ArcPtr->i];      */
       ListArcPtr = AdjaNodInd[ArcPtr->i]->Next;
       while ( ListArcPtr != NULL ) {
/*           
             misled additional comparison previously used:
             if (ArcPtr->j == 0)
                return( NO );
*/
             if ( ArcPtr->j == ListArcPtr->APtr[0]->j )
                return( NO );
             ListArcPtr = ListArcPtr->Next;
       }
       return( YES );
    }
}

int ValidNode  (int               n_Levels,
                ListNodPtrType    *RootNodLev,
                ListNodPtrType    *DemaNodLev,
                NodPtrType        NodPtr)
{
  ListNodPtrType     ListNodPtr;
  int                l;

  for ( l = 0; l < n_Levels; l++ ) {
      ListNodPtr  = RootNodLev[l]->Next;
      while ( ListNodPtr != NULL ) {
            if ( ListNodPtr->NPtr->i == NodPtr->i )
               return( NO );
            ListNodPtr = ListNodPtr->Next;
      }
      ListNodPtr  = DemaNodLev[l]->Next;
      while ( ListNodPtr != NULL ) {
            if ( ListNodPtr->NPtr->i == NodPtr->i )
               return( NO );
            ListNodPtr = ListNodPtr->Next;
      }
  }
  return( YES );
}