/**********************************************************
'*                  DANTZIG'S  MODEL                      *
'*                                                        *
'* LIST OF MAIN VARIABLES:                                *
'*                                                        *
'*   NR       : TOTAL NUMBER OF MARKS                     *
'*   V(NR,NR) : PATH VALUES                               *
'*   XL(NR)   : USED FOR WEIGHTING OF EACH PATH           *
'*   IE(NR*2) : SET OF ADOPTED MARKS                      *
'*   V        : PATH VALUE                                *
'*   IR       : NUMBER OF MARKS COMING FROM A SAME MARK   *
'*   RA       : INDEX OF AN ARRIVAL MARK                  *
'*   R        : = "YES" ON OPTIMAL ROUTE                  *
'*   XM1,XM2  : USED TO SEEK MINIMUM, MAXIMUM PATH        *
'*   IASSO    : ARRIVAL MARK ASSOCIATED WITH SET IE       *
'* ------------------------------------------------------ *
'* PROBLEM DESCRIPTION:                                   *
'* A mountaineer wants to climb up a stiff face. He has   *
'* preliminarily estimated that he can follow different   *
'* paths from 0 (bottom) to 8 (summit) with different     *
'* lengths:                                               *
'*              Path 1:  0 - 1 - 4 - 7 - 8                *
'*              Path 2:  0 - 3 - 5 - 8                    *
'*              Path 3:  0 - 2 - 6 - 5 - 8                *
'*              Path 3a: 0 - 2 - 6 - 7 - 8                *
'*              Path 4:  0 - 1 - 2 - 4 - 7 - 8            *
'*              Path 4a: 0 - 1 - 2 - 4 - 6 - 7 - 8        *
'* The mountaineer wants to know the maximum length rope  *
'* to take,  knowing the following distance matrix        *
'* (meters):                                              *
'*     START/ARR/DIST  START/ARR/DIST  START/ARR/DIST     *
'*       0    1   5      0    2   11     0    3   10      *
'*       1    2   4      1    4   6                       *
'*       2    4   5      2    6   9                       *
'*       3    5   2      4    7   5                       *
'*       5    6   4      5    8   15                      *                                                
'*       6    7   6      7    8   8                       *
'* ------------------------------------------------------ *
'* SAMPLE RUN:                                            *
'*                                                        *
'* DO YOU WANT THE MINIMUM PATH (Y/N) ? N                 *
'*                                                        *
'* NUMBER OF MARKS ? 9                                    *
'*                                                        *
'* NUMBER OF ARCS FROM MARK #0 ? 3                        *
'* ARRIVAL MARK, VALUE ? 1 5                              *
'* ARRIVAL MARK, VALUE ? 2 11                             *
'* ARRIVAL MARK, VALUE ? 3 10                             *
'*                                                        *
'* NUMBER OF ARCS FROM MARK #1 ? 2                        *
'* ARRIVAL MARK, VALUE ? 2 4                              *
'* ARRIVAL MARK, VALUE ? 4 6                              *
'*                                                        *
'* NUMBER OF ARCS FROM MARK #2 ? 2                        *
'* ARRIVAL MARK, VALUE ? 4 5                              *
'* ARRIVAL MARK, VALUE ? 6 9                              *
'*                                                        *
'* NUMBER OF ARCS FROM MARK #3 ? 1                        *
'* ARRIVAL MARK, VALUE ? 5 2                              *
'*                                                        *
'* NUMBER OF ARCS FROM MARK #4 ? 1                        *
'* ARRIVAL MARK, VALUE ? 7 5                              *
'*                                                        *
'* NUMBER OF ARCS FROM MARK #5 ? 2                        *
'* ARRIVAL MARK, VALUE ? 6 4                              *
'* ARRIVAL MARK, VALUE ? 8 15                             *
'*                                                        *
'* NUMBER OF ARCS FROM MARK #6 ? 1                        *
'* ARRIVAL MARK, VALUE ? 7 6                              *
'*                                                        *
'* NUMBER OF ARCS FROM MARK #7 ? 1                        *
'* ARRIVAL MARK, VALUE ? 8 8                              *
'*                                                        *
'* RESULTS:                                               *
'*                                                        *
'* THE MAXIMUM VALUE PATH IS:                             *
'*                                                        *
'*     <- 0 - 2 - 6 - 7 - 8 ->                            *
'*                                                        *
'* Path Value = 34.000000                                 *
'*                                                        *
'* THE MINIMUM VALUE PATH IS:                             *
'*                                                        *
'*     <- 0 - 1 - 2 - 4 - 7 - 8 ->                        *
'*                                                        *
'* Path Value = 27.000000                                 *
'* ------------------------------------------------------ *
'* REFERENCE:                                             *
'*  Modèles pratiques de décision Tome 2, By Jean-Pierre  *
'*  Blanger, PSI Editions, France, 1982.                  *
'*                                                        *
'*                 C++ Release 2.0 By J-P Moreau, Paris.  *
*                            (www.jpmoreau.fr)            *
'*********************************************************/
//PROGRAM DANTZIG;
#include <stdio.h>
#include <math.h>

#define  NMAX  25

  int NR;
  double V[NMAX][NMAX];
  double XL[NMAX];
  int IE[NMAX];
  double XM1,XM2,XV;

void Data0()  {  //INPUT DATA
  int I,J;
  for (I=0; I<NMAX; I++)
    for (J=0; J<NMAX; J++)
      V[I][J]=0.0;
  NR = 9;
  V[0][1] = 5; V[0][2] = 11; V[0][3] = 10;
  V[1][2] = 4; V[1][4] = 6;
  V[2][4] = 5; V[2][6] = 9;
  V[3][5] = 2;
  V[4][7] = 5;
  V[5][6] = 4; V[5][8] = 15;
  V[6][7] = 6;
  V[7][8] = 8;
  printf("\n RESULTS\n\n");
  printf(" THE MAXIMUM VALUE PATH IS:\n\n");
}

//Data0 must be called first
void Data1()  {  //INPUT DATA
  printf(" THE MINIMUM VALUE PATH IS:\n\n");
}

//Seek maximum value path
void TDantzig0() {
//Labels: e30, e50, e70
  int F,IASSO,IO,ID,J,K;
     XL[0] = 0;
     K = 1; IE[K] = 0; F=0;
e30: XM1 = -999999.0; XM2 = -999999.0;
     for (IO=1; IO<=K; IO++) {
	   for (ID=1; ID<=NR; ID++) {
		 if (V[IE[IO]][ID] < XM1 || V[IE[IO]][ID] == 0) goto e70;
         for (J=1; J<=K; J++) {
		   if (IE[J] == ID) {
             F = 1; goto e50;
           }
         }
e50:     if (F == 1)  {F = 0; goto e70;}
         XM1 = V[IE[IO]][ID]; IASSO = ID;
e70:  ;}
       XV = XL[IE[IO]] + XM1;
       if (XV > XM2) {XM2 = XV; IE[K + 1] = IASSO;}
	 }
	 XL[IE[K + 1]] = XM2;
     K++;
	 if (IE[K] != NR - 1) goto e30;
}

//Seek minimum value path
void TDantzig1() {
//Labels: e30, e50, e70
  int F,IASSO,IO,ID,J,K;
     XL[0] = 0;
     K = 1; IE[K] = 0; F=0;
e30: XM1 = 999999.0; XM2 = 999999.0;
     for (IO=1; IO<=K; IO++) {
	   for (ID=1; ID<=NR; ID++) {
		 if (V[IE[IO]][ID] > XM1 || V[IE[IO]][ID] == 0) goto e70;
         for (J=1; J<=K; J++) {
		   if (IE[J] == ID) {
             F = 1; goto e50;
           }
         }
e50:     if (F == 1)  {F = 0; goto e70;}
         XM1 = V[IE[IO]][ID]; IASSO = ID;
e70:  ;}
       XV = XL[IE[IO]] + XM1;
 	   if (XV < XM2) {XM2 = XV; IE[K + 1] = IASSO;}
     }
     XL[IE[K + 1]] = XM2;
     K++;
	 if (IE[K] != NR - 1) goto e30;
}

void Results()  {  //EDIT OPTIMAL PATH
//Labels: e30, e50
    int IO,ID,K;
	double L;
    IO = IE[1]; ID = IE[2]; K = 1; L=0;
    printf("     <- 0 - ");
e30:if (V[IO][ID] != 0) {
      L += V[IO][ID];
      printf("%d - ", ID); IO = ID; K++; ID = IE[K];
      goto e50;
    }
    K++; ID = IE[K];
e50:if (ID != NR - 1) goto e30;
    L += V[IO][ID];
    printf("%d ->\n\n", ID);
	printf(" Path Value = %f\n\n", L);
}

void Pause() {
	char answer[2];
	printf(" Any key + <Enter> to exit... ");
	scanf("%s", answer);
}


void main() {

  Data0();     //INPUT DATA
  TDantzig0(); //DANTZIG MODEL (MAX VALUE PATH)
  Results();   //EDIT OPTIMAL PATH
  Data1();     //INPUT DATA
  TDantzig1(); //DANTZIG MODEL (MIN VALUE PATH)
  Results();   //EDIT OPTIMAL PATH
  Pause();
}

// end of file dantzig.cpp