/*****************************************************************/
/*                                                               */
/* Program to Solve the                                          */
/* Multi-level network optimization problem                      */
/*                                                               */
/* Input/Output Routines                                         */
/*                                                               */
/* 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: 3.00                                                 */
/*                                                               */
/* Date: May/98                                                  */
/*                                                               */
/*****************************************************************/

void ReadData      (FILE              *InFile,
                    int               *n_Nodes,
                    int               *n_Levels,
                    ListArcPtrType    **AdjaNodInd,
                    ListNodPtrType    **DemaNodLev,
                    ListNodPtrType    **RootNodLev);

void PrintData     (FILE              *InFile,
                    int               n_Nodes,
                    int               n_Levels,
                    ListArcPtrType    *AdjaNodInd,
                    ListNodPtrType    *DemaNodLev,
                    ListNodPtrType    *RootNodLev);

void FreeData      (int               n_Nodes,
                    int               n_Levels,
                    ListArcPtrType    *AdjaNodInd,
                    ListNodPtrType    *DemaNodLev,
                    ListNodPtrType    *RootNodLev);

void CreatePred    (int            n_Nodes, 
                    PredLevPtrType **PredLev);

void DeletePred    (int            n_Nodes,
                    PredLevPtrType *PredLev);

void Initialize_Ml (int            n_Levels, 
                    ListNodPtrType *DemaNodLev, 
                    MlType         **Ml);

void Delete_Ml     (MlType         *Ml);

void Initialize_sl (int            n_Levels, 
                    ListNodPtrType *DemaNodLev,
                    slType         **sl);

void Delete_sl     (slType         *sl);


/*****************************************************************/

void ReadData      (FILE              *InFile,
                    int               *n_Nodes,
                    int               *n_Levels,
                    ListArcPtrType    **AdjaNodInd,
                    ListNodPtrType    **DemaNodLev,
                    ListNodPtrType    **RootNodLev)
{
  char              *line;
  char              Line[LLENGTH];
  int               i, l;
  int               Orig, Dest;
  int               Index, Level;
  float             FixCost, VarCost, Demand;
  ArcPtrType        *ArcPtr;
  NodPtrType        NodPtr;
  ListArcPtrType    ListArcPtr, ListArcAux;
  ListNodPtrType    ListNodPtr, ListNodAux;

  /*    read number of nodes and number of levels                   */
  line = &Line[0];
  fgets(line, LLENGTH, InFile);
  fgets(line, LLENGTH, InFile);
  sscanf(line, "%d", n_Nodes);
  
  fgets(line, LLENGTH, InFile);
  fgets(line, LLENGTH, InFile);
  sscanf(line, "%d", n_Levels);

  /*    read arcs, fixed and  variable costs                        */
  fgets(line, LLENGTH, InFile);
  fgets(line, LLENGTH, InFile);
  *AdjaNodInd = (ListArcPtrType *) calloc( *n_Nodes, sizeof(ListArcPtrType) );
  for ( i = 0; i < *n_Nodes; i++) {
      (*AdjaNodInd)[i] = (ListArcPtrType) malloc( sizeof(ListArcType) );
      (*AdjaNodInd)[i]->Next = NULL;
  }
  while ( fscanf(InFile,"%d %d ", &Orig, &Dest ) == 2 ) {
      /*  read values  */
      ArcPtr = (ArcPtrType *) calloc( *n_Levels, sizeof(ArcPtrType) );
      for ( l = 0; l < *n_Levels; l++) {
          fscanf(InFile, "%f %f", &FixCost, &VarCost);
          ArcPtr[l] = (ArcPtrType) malloc( sizeof(ArcType) );
          ArcPtr[l]->i          = Orig-1;
          ArcPtr[l]->j          = Dest-1;
          ArcPtr[l]->cij        = VarCost;
          ArcPtr[l]->fij        = FixCost;
          ArcPtr[l]->Cij        = 0.0;
          ArcPtr[l]->xij        = 0.0;
          ArcPtr[l]->wij        = 0.0;
          ArcPtr[l]->Gamma_wij  = 0.0;
          ArcPtr[l]->Fij        = 0.0;
          ArcPtr[l]->yij        = 0;
          ArcPtr[l]->Status     = SET_FREE;
      }
      /*  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;
  }

  /*    read index, level, and fixed cost of supplying nodes          */
  fgets(line, LLENGTH, InFile);
  fgets(line, LLENGTH, InFile);
  *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;
  }
  while (fscanf(InFile, "%d %d %f ", &Index, &Level, &FixCost) == 3 ) {
      /*  read values  */
      NodPtr            = (NodPtrType) malloc( sizeof(NodType) );
      NodPtr->i         = Index-1;
      NodPtr->fi        = FixCost;
      NodPtr->Fi        = 0.0;
      NodPtr->zi        = 0;
      NodPtr->vi        = 0.0;
      NodPtr->Gamma_vi  = 0.0;
      NodPtr->TransFlow = 0.0;
      NodPtr->weight_i  = 0.0;
      NodPtr->Status    = SET_FREE;

      /*  find position  */
      ListNodAux = (*RootNodLev)[Level-1];
      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;
  }

  /*    read index, level, and demand of demand nodes                */
  fgets(line, LLENGTH, InFile);
  fgets(line, LLENGTH, InFile);
  *DemaNodLev = (ListNodPtrType *) calloc(*n_Levels, sizeof(ListNodPtrType) );
  for ( l = 0; l < *n_Levels; l++) {
    (*DemaNodLev)[l] = (ListNodPtrType) malloc( sizeof(ListNodType) );
    (*DemaNodLev)[l]->Next = NULL;
  }
  while ( fscanf(InFile, "%d %d %f", &Index, &Level, &Demand) == 3 ) {
      /*  read values  */
      NodPtr         = (NodPtrType) malloc( sizeof(NodType) );
      NodPtr->i      = Index-1;
      NodPtr->di     = Demand;
      /*  find position  */
      ListNodAux = (*DemaNodLev)[Level-1];
      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;
  }

  /*   removing head nodes                                             */
  for ( i = 0; i < *n_Nodes; i++) {
      ListArcPtr = (*AdjaNodInd)[i];
      (*AdjaNodInd)[i] = (*AdjaNodInd)[i]->Next;
      free(ListArcPtr);
  }
  for ( l = 0; l < *n_Levels+1; l++) {
      ListNodPtr = (*RootNodLev)[l];
      (*RootNodLev)[l] = (*RootNodLev)[l]->Next;
      free(ListNodPtr);
  }
  for ( l = 0; l < *n_Levels; l++) {
      ListNodPtr = (*DemaNodLev)[l];
      (*DemaNodLev)[l] = (*DemaNodLev)[l]->Next;
      free(ListNodPtr);
  }

  /*  testing routine  */
/*
  PrintData(OUTFILE,*n_Nodes,*n_Levels,*AdjaNodInd,*DemaNodLev,*RootNodLev);
*/

}

void PrintData     (FILE              *OutFile,
                    int               n_Nodes,
                    int               n_Levels,
                    ListArcPtrType    *AdjaNodInd,
                    ListNodPtrType    *DemaNodLev,
                    ListNodPtrType    *RootNodLev)

{
  int               i, l;
  ListArcPtrType    ListArcPtr;
  ListNodPtrType    ListNodPtr;


  fprintf(OutFile,"\nProblem:\n");
  fprintf(OutFile,"\nNumber 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    ");
  for ( l = 0; l < n_Levels; l++ )
      fprintf(OutFile, "f^%d    c^%d Status^%d    ", l+1, l+1, l+1);
  fprintf(OutFile,"\n");
  for ( i = 0; i < n_Nodes; i++ ) {
    ListArcPtr = AdjaNodInd[i];
    while (ListArcPtr != NULL) {
       fprintf(OutFile, "%4d %4d ",
               ListArcPtr->APtr[0]->i+1,
               ListArcPtr->APtr[0]->j+1 );
       for ( l = 0; l < n_Levels; l++ ) {
         fprintf(OutFile, "%6.0f %6.0f ",
                 ListArcPtr->APtr[l]->fij, ListArcPtr->APtr[l]->cij );
         if ( ListArcPtr->APtr[l]->Status == SET_FREE )
            fprintf(OutFile, "SET_FREE " );
         else if ( ListArcPtr->APtr[l]->Status == SET_TO_0 )
            fprintf(OutFile, "SET_TO_0 " );
         else if ( ListArcPtr->APtr[l]->Status == SET_TO_1 )
            fprintf(OutFile, "SET_TO_1 " );
       }
       fprintf(OutFile,"\n" );
       ListArcPtr = ListArcPtr->Next;
    }
  }
  fprintf(OutFile,"Supplying nodes\n");
  fprintf(OutFile,"Index Level     fi   Status\n");
  for ( l = 0; l < n_Levels; l++ ) {
      ListNodPtr = RootNodLev[l];
      while (ListNodPtr != NULL) {
         fprintf(OutFile, " %4d  %4d %6.0f ",
                 ListNodPtr->NPtr->i+1, l+1, ListNodPtr->NPtr->fi);
         if ( ListNodPtr->NPtr->Status == SET_FREE )
            fprintf(OutFile, "SET_FREE\n" );
         else if ( ListNodPtr->NPtr->Status == SET_TO_0 )
            fprintf(OutFile, "SET_TO_0\n" );
         else if ( ListNodPtr->NPtr->Status == SET_TO_1 )
            fprintf(OutFile, "SET_TO_1\n" );
         ListNodPtr = ListNodPtr->Next;
      }
  }
  fprintf(OutFile,"Demand nodes\n");
  fprintf(OutFile,"Index Level     di\n");
  for ( l = 0; l < n_Levels; l++ ) {
      ListNodPtr = DemaNodLev[l];
      while (ListNodPtr != NULL) {
         fprintf(OutFile, " %4d  %4d %6.0f\n",
                 ListNodPtr->NPtr->i+1, l+1, ListNodPtr->NPtr->di);
         ListNodPtr = ListNodPtr->Next;
      }
  }
}

void FreeData      (int               n_Nodes,
                    int               n_Levels,
                    ListArcPtrType    *AdjaNodInd,
                    ListNodPtrType    *DemaNodLev,
                    ListNodPtrType    *RootNodLev)
{
  int               i, l;
  ListArcPtrType    ListArcPtr, ListArcAux;
  ListNodPtrType    ListNodPtr, ListNodAux;

  /*  fprintf(OUTFILE, "\nvoid FreeData working\n" ); */
  for ( i = 0; i < n_Nodes; i++ ) {
      ListArcPtr = AdjaNodInd[i];
      while ( ListArcPtr != NULL ) {
            ListArcAux = ListArcPtr;
            ListArcPtr = ListArcPtr->Next;

            for ( l = 0; l < n_Levels; l++ )
                free(ListArcAux->APtr[l]);
            free( ListArcAux->APtr );
            free( ListArcAux );
      }
  }
  free( AdjaNodInd );

  for ( l = 0; l < n_Levels; l++ ) {
      ListNodPtr = DemaNodLev[l];
      while ( ListNodPtr != NULL ) {
            ListNodAux = ListNodPtr;
            ListNodPtr = ListNodPtr->Next;

            free( ListNodAux->NPtr );
            free( ListNodAux );
      }
      ListNodPtr = RootNodLev[l];
      while ( ListNodPtr != NULL ) {
            ListNodAux = ListNodPtr;
            ListNodPtr = ListNodPtr->Next;

            free( ListNodAux->NPtr );
            free( ListNodAux );
      }
  }
  free( DemaNodLev );
  free( RootNodLev );
}


void CreatePred    (int            n_Nodes, 
                    PredLevPtrType **PredLev)
{
  int i,j;

  (*PredLev) = (PredLevPtrType *) calloc( n_Nodes, sizeof(PredLevPtrType)) ;
  for (i=0; i < n_Nodes; i++) {
     (*PredLev)[i] = (PredLevPtrType) calloc( n_Nodes,sizeof(PredLevType));
      for (j=0; j < n_Nodes; j++)
          (*PredLev)[i][j] = DUMMY;
  }
}

void DeletePred    (int            n_Nodes,
                    PredLevPtrType *PredLev)
{
  int   i;

  /*  fprintf(OUTFILE, "\nvoid DeletePred working\n" ); */
  for ( i = 0; i < n_Nodes; i++ )
      free( PredLev[i] );
  free( PredLev );
}

void Initialize_Ml (int            n_Levels,
                    ListNodPtrType *DemaNodLev,
                    MlType         **Ml)
{
  int               l;
  MlType            Sum;
  ListNodPtrType    DemaNodPtr;

  (*Ml) = (MlPtrType) calloc( n_Levels, sizeof(MlType));
  Sum = 0;
  for (l=n_Levels-1; l >= 0; l-- ) {
      DemaNodPtr = DemaNodLev[l];
      while (DemaNodPtr != NULL) {
            Sum += DemaNodPtr->NPtr->di;
            DemaNodPtr = DemaNodPtr->Next;
      }
      (*Ml)[l] = Sum;
  }
  /* testing routine */
/*
  for ( l = 0; l < n_Levels; l++ )
      fprintf(OUTFILE, "M[%d] = %f\n", l+1, (*Ml)[l] );
*/
}

void Delete_Ml     (MlType         *Ml)
{
  /*  fprintf(OUTFILE, "\nvoid Delete_Ml working\n" ); */
  free(Ml);
}

void Initialize_sl (int            n_Levels,
                    ListNodPtrType *DemaNodLev,
                    slType         **sl)
{
  int               l;
  slType            Sum;
  ListNodPtrType    DemaNodPtr;

  (*sl) = (slPtrType) calloc( n_Levels, sizeof(slType));
  Sum = 0;
  for (l=n_Levels-1; l >= 0; l-- ) {
      DemaNodPtr = DemaNodLev[l];
      while (DemaNodPtr != NULL) {
            Sum += DemaNodPtr->NPtr->di;
            DemaNodPtr = DemaNodPtr->Next;
      }
      (*sl)[l] = Sum;
  }
  /* testing routine */
/*
  for ( l = 0; l < n_Levels; l++ )
      fprintf(OUTFILE, "s[%d] = %f\n", l+1, (*sl)[l] );
*/
}

void Delete_sl     (slType         *sl)
{
  /*  fprintf(OUTFILE, "\nvoid Delete_sl working\n" ); */
  free(sl);
}