/*****************************************************************/
/*                                                               */
/* Program to Solve the                                          */
/* Multi-level Network Optimization Problem                      */
/*                                                               */
/* 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: 4.00                                                 */
/*                                                               */
/* Date: May/98                                                  */
/*                                                               */
/*****************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include "ty.h"
#include "wa.c"
#include "io.c"
#include "bb.c"

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);

int main( int argc, char *argv[] ) {
  int               n_Nodes, n_Levels, i, j, k, l, Cont, Visited;
  ListArcPtrType    *AdjaNodInd, ListArcPtr;
  ListNodPtrType    *DemaNodLev, ListNodPtr;
  ListNodPtrType    *RootNodLev;
  MlType            *Ml;
  slType            *sl;
  PredLevPtrType    *BestPredLev, *GoodPredLev, *CurrPredLev;
  float             BestUpper, UpperBound, LowerBound, Elapsed;

  int               Arcs;

  fprintf(OUTFILE, "Settings:\n");
#if _B_B_NODES_ == _FREE_
  fprintf(OUTFILE, "_B_B_NODES_       is _FREE_\n");
#elif _B_B_NODES_ == _ONE_
  fprintf(OUTFILE, "_B_B_NODES_       is _ONE_\n");
#elif _B_B_NODES_ == _TEN_THOUSAND_
  fprintf(OUTFILE, "_B_B_NODES_       is _TEN_THOUSAND_\n");
#elif _B_B_NODES_ == _FIFTY_THOUSAND_
  fprintf(OUTFILE, "_B_B_NODES_       is _FIFTY_THOUSAND_\n");
#else
  fprintf(OUTFILE, "_B_B_NODES_       is unknown\n");
#endif

#if _CHOICE_STRATEGY_ == _FIRST_FREE_
  fprintf(OUTFILE, "_CHOICE_STRATEGY_ is _FIST_FREE_\n");
#elif _CHOICE_STRATEGY_ == _GOOD_INCREASE_
  fprintf(OUTFILE, "_CHOICE_STRATEGY_ is _GOOD_INCREASE_\n");
#elif _CHOICE_STRATEGY_ == _NO_CYCLES_
  fprintf(OUTFILE, "_CHOICE_STRATEGY_ is _NO_CYCLES_\n");
#else
  fprintf(OUTFILE, "_CHOICE_STRATEGY_ is unknown\n");
#endif

#if _REDUCTION_ == _IN_USE_
  fprintf(OUTFILE, "_REDUCTION_       is _IN_USE_\n");
#elif _REDUCTION_ == _NOT_IN_USE_
  fprintf(OUTFILE, "_REDUCTION_       is _NOT_IN_USE_\n");
#else
  fprintf(OUTFILE, "_REDUCTION_       is unknown\n");
#endif

#if _LR_USE_ == _ONCE_
  fprintf(OUTFILE, "_LR_USE_          is _ONCE_\n");
#elif _LR_USE_ == _ALL_THE_TIME_
  fprintf(OUTFILE, "_LR_USE_          is _ALL_THE_TIME_\n");
#else
  fprintf(OUTFILE, "_LR_USE_          is unknown\n");
#endif

#if _STEP_ == _HO_SE_
  fprintf(OUTFILE, "_STEP_            is _HO_SE_\n");
#elif _STEP_ == _HE_WO_CR_
  fprintf(OUTFILE, "_STEP_            is _HE_WO_CR_\n");
#else
  fprintf(OUTFILE, "_STEP_            is unknown\n");
#endif

#if _L2_VERSION_ == _FREE_CARDINALITY_
  fprintf(OUTFILE, "_L2_VERSION_      is _FREE_CARDINALITY_\n");
#elif _L2_VERSION_ == _FIXED_CARDINALITY_
  fprintf(OUTFILE, "_L2_VERSION_      is _FIXED_CARDINALITY_\n");
  fprintf(OUTFILE, "_L2_CARDINALITY_  is %d\n", _L2_CARDINALITY_);
#else
  fprintf(OUTFILE, "_L2_VERSION_      is unknown\n");
#endif

#if _L3_VERSION_ == _FREE_CARDINALITY_
  fprintf(OUTFILE, "_L3_VERSION_      is _FREE_CARDINALITY_\n");
#elif _L3_VERSION_ == _FIXED_CARDINALITY_
  fprintf(OUTFILE, "_L3_VERSION_      is _FIXED_CARDINALITY_\n");
  fprintf(OUTFILE, "_L3_CARDINALITY_  is %d\n", _L3_CARDINALITY_);
#else
  fprintf(OUTFILE, "_L3_VERSION_      is unknown\n");
#endif

  /*   read data                                                       */
  ReadData(INFILE, &n_Nodes, &n_Levels, &AdjaNodInd, &DemaNodLev, &RootNodLev );

  /*   initialize predecessor matrix                                   */
  CreatePred(n_Nodes, &BestPredLev);
  CreatePred(n_Nodes, &GoodPredLev);
  CreatePred(n_Nodes, &CurrPredLev);

  /*   initialize Ml and sl vector                                     */
  Initialize_Ml(n_Levels, DemaNodLev, &Ml);
  Initialize_sl(n_Levels, DemaNodLev, &sl);

  /*   initialize best upper bound                                     */
  BestUpper = INFINITY;

  /*   branch & bound                                                  */
  Visited = 0;
  SetNode( RootNodLev[0]->NPtr, SET_TO_1 );
  SetNode( RootNodLev[0]->NPtr, SET_FREE );
  StartCronograph();
  Branch_Bound(n_Nodes, n_Levels, 
               AdjaNodInd, DemaNodLev, RootNodLev, Ml, sl, 
               &BestPredLev, &GoodPredLev, &CurrPredLev,
               &BestUpper, &UpperBound, &LowerBound, &Visited);
  Elapsed = ElapsedTime();

  /*   write final results                                             */
  fprintf(OUTFILE, "\nFinal Result:\n");
  fprintf(OUTFILE, "Solution      %f\n", BestUpper);
  fprintf(OUTFILE, "Nodes visited %d\n",Visited);
  fprintf(OUTFILE, "Time (watch)  %10.5f\n", Elapsed );

  if ( UpdateFlows(n_Nodes, n_Levels, 
                   AdjaNodInd, DemaNodLev, RootNodLev, 
                   BestPredLev) == SUCCESS ) {
     Arcs = 0;
     for ( i = 0; i < n_Nodes; i++ ) {
         ListArcPtr = AdjaNodInd[i];
         while ( ListArcPtr != NULL ) {
              for (l=0; l < n_Levels; l++ )
                  if ( ListArcPtr->APtr[l]->xij > ZERO )
                     Arcs++;
              ListArcPtr = ListArcPtr->Next;
         }
     }
     fprintf(OUTFILE, "\nPaths (%d arcs)\n", Arcs);
  }
  else 
     fprintf(OUTFILE, "\nPartial paths\n");
  for ( l = 0; l < n_Levels; l++ ) {
      ListNodPtr = DemaNodLev[l];
      while (ListNodPtr != NULL) {
           fprintf(OUTFILE,"%2d", ListNodPtr->NPtr->i+1);
           i = ListNodPtr->NPtr->i;
           Cont = 0;
           for (j=l; j >= 0; j--) {
               while ( ( i != DUMMY ) && ( i != BestPredLev[j][i] ) ) {
                     if ( BestPredLev[j][i] == DUMMY ) 
                        fprintf(OUTFILE,"->DUMMY");
                     else
                        fprintf(OUTFILE,"->%2d",BestPredLev[j][i]+1);
                     i = BestPredLev[j][i];
                     Cont++;
               }
               if ( j > 0 ) {
                  fprintf(OUTFILE, "\n");
                  for (k = 0; k < Cont; k++)
                      fprintf(OUTFILE,"    ");
                  if ( i == DUMMY )
                     fprintf(OUTFILE,"DUMMY");
                  else
                     fprintf(OUTFILE,"%2d", i+1);
               }
           }
           fprintf(OUTFILE, "\n");
           ListNodPtr = ListNodPtr->Next;
      }
      fprintf(OUTFILE, "\n");
  }
  fprintf(OUTFILE, "\nSupplying nodes\n");
  for ( l = 0; l < n_Levels; l++ ) {
      fprintf(OUTFILE, "Level %d -> ", l+1);
      ListNodPtr = RootNodLev[l];
      while (ListNodPtr != NULL) {
           if (ListNodPtr->NPtr->TransFlow > ZERO )
              fprintf(OUTFILE, "%4d ", ListNodPtr->NPtr->i+1 );
           ListNodPtr = ListNodPtr->Next;
      }
      fprintf(OUTFILE, "\n");
  }
  fprintf(OUTFILE, "\n");

  /*  free everything  */
  FreeData(n_Nodes, n_Levels, AdjaNodInd, DemaNodLev, RootNodLev );

  DeletePred(n_Nodes, BestPredLev);
  DeletePred(n_Nodes, GoodPredLev);
  DeletePred(n_Nodes, CurrPredLev);

  Delete_Ml(Ml);
  Delete_sl(sl);
  return(0);
}