/**********************************************************************
   bertsimas.c  

   Copyright (C) 2002, Joshua Knowles.


   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version. 

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details. 

   The GNU General Public License is available at:
      http://www.gnu.org/copyleft/gpl.html
   or by writing to: 
        The Free Software Foundation, Inc., 
        675 Mass Ave, Cambridge, MA 02139, USA.  

***********************************************************************
 
  Purpose
  ~~~~~~~

  This program calculates the difference between the expected lengths
  of two neighbouring probabilistic TSP (pTSP) tours, tau and
  tau'. Two different neighbourhoods are defined (and can be selected
  by a command line parameter). They are the 1-shift neighbourhood and
  the 2-p-opt neighbourhood.

  The two tours are a tour of six nodes, tau = 1,2,3,4,5,6 and a tour
  tau' which is the result of applying the neighbourhood operator to
  tau.

  Both the 2-p-opt and 1-shift operators are controlled by two
  parameters, i and j. The 2-p-opt neighbourhood operator reverses the
  ordering of nodes in positions i...j in the tour. The 1-shift
  operator moves the node at position i to position j and shifts all
  of the intervening nodes one space back. Here follow two examples:

  2p-opt with i=2, j=5 tau = 1,2,3,4,5,6 -> tau' = 1,5,4,3,2,6

  1-shift with i=2, j=5 tau = 1,2,3,4,5,6 -> tau' = 1,3,4,5,2,6
  
  The purpose of the software is to demonstrate that some recursive
  equations proposed by Bertsimas for calculating the expected
  length difference between neighbouring tours are incorrect.

  To do this, the program first calculates the expected length
  difference by making an explicit calculation of the expected length
  of each tour and then taking the difference. Then the appropriate
  Bertsimas recursive equation is used to calculate the expected
  difference. By comparing the results of each calculation (and by
  checking the code herein if necessary) the error in the Bertsimas
  equations should be established.


  Instructions
  ~~~~~~~~~~~~

  To compile: gcc bertsimas.c -o bertsimas -lm

  To run: ./bertsimas [-h] [-n neighbourhood] [-p probability] 
[-g graph] [-i i] [-j j] [-s seed]
   
  where all of the command line parameters are independenlty 
  optional (execept for -h) and are described below.  
  Running the code without any command line parameters is
  equivalent to running it with the following command line:

  ./bertsimas -n 2 -p 0.5 -g 1 -i 2 -j 5

  This calculates the difference between the expected length of two
  tours: tau  = 1,2,3,4,5,6 and tau' = 1,5,4,3,2,6 where the nodes are
  on the vertices of a regular hexagon of side 1.

  For other calculations see the command line parameters section below.

  --
   
  Command line parameters:
  
  [-h] prints out these instructions. This option can not be combined
  with any others

  [-n neighbourhood] selects the neighbourhood operator, 1-shift or          // -n 1 ------> 1-shift
  2-p-opt. The neighburhood parameter is given the value 1 or 2, as          // -n 2 ------> 2-p-opt
  appropriate
         
  [-p probability] sets the probability of each node being in the
  tour. The probability parameter takes a real number in the range
  (0,1)

  [-g graph] selects the type of graph. Giving graph the value 1
  selects a graph where each node is on the vertex of a regular
  hexagon of side 1. Giving graph the value 2 selects a random
  Euclidean graph in the plane. i.e. each node is at a point in the
  unit square and distances between nodes are their Euclidean distance

  [-i i] sets the i parameter (see Purpose section above).  The
  variable i must be an integer from the set 1..5

  [-j j] sets the j parameter (see Purpose section above).  The
  variable i must be an integer from the set 2..6 and j > i

  [-s seed] sets the random seed value, a long integer. This only
  affects the output if the random Euclidean graph is chosen.

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



#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<string.h>
#define N 6
#define SYM 1
#define RN rand()/(RAND_MAX+1.0)

double fA(int i, int k, int *tau);
double fB(int i, int k, int *tau);
int joshmod(int i);
double Explength(int *tau);
double deltaE_iiplusone(int i, int *tau);
double deltaE_ij(int i, int j, int *tau);
void print_perm(int *tau);
double shiftE_ij(int i, int j, int *tau);
void print_header();
void one_shift(int *tau, int i, int j);
void two_p_opt(int *tau, int i, int j);

double p=0.5;         // probability of node presence set to default value 0.5
double q;             // 1 - p
double pos[N+1][2];   // x,y, position of vertices in Euclidean plane for random graph

int tau[N+1];         // the two tours
int tau_p[N+1];

double dist[N+1][N+1]; // the distance matrix 

int graph=1;  // 1 = hexagon , 2 = random
int Gi=2;   // parameter i
int Gj=5;   // parameter j
int Gn=2;   // parameter n which sets the neighbourhood. 1=1-shift, 2=2-p-opt
long int seed = 3425464;

 

int main(int argc, char *argv[])
{
  int i,j,k;
  int count;
  int tmp;
  
  if(argc==2)
    {
      if(strcmp("-h",argv[1])==0)
	{
	  print_header();
	  exit(0);
	}
      else
	{
	  fprintf(stderr,"Command line operators wrongly specified. Try ./bertsimas -h \n");
	  exit(1);
	}
    }
 
      
  else if((argc>2)&&(argc%2==1))
    {
      for(i=1;i<argc-1;i+=2)
	{
	  if(strcmp("-g", argv[i])==0)
 	    graph = atoi(argv[i+1]);
	  else if(strcmp("-i", argv[i])==0)
 	    Gi = atoi(argv[i+1]);
	  else if(strcmp("-j", argv[i])==0)
 	    Gj = atoi(argv[i+1]);
	  else if(strcmp("-s", argv[i])==0)
 	    seed = atol(argv[i+1]);
	  else if(strcmp("-n", argv[i])==0)
 	    Gn = atoi(argv[i+1]);
	  else if(strcmp("-p", argv[i])==0)    //////////////////////
 	    p = atof(argv[i+1]);
	  else
	    {
	      fprintf(stderr,"Unrecognized command line parameter. Try ./bertsimas -h \n");
	      exit(1);
	    }
	}
    }
  
  else if(argc!=1)
    {
      fprintf(stderr,"Command line operators wrongly specified. Try ./bertsimas -h \n");
      exit(1);
    }

  if((Gi>=Gj)||(Gi<1)||(Gi>5)||(Gj<2)||(Gj>6)||(graph<1)||(graph>2)||(Gn<1)||(Gn>2))
    {
      fprintf(stderr,"Command line operators wrongly specified. Try ./bertsimas -h \n");
      exit(1);
    }

  srand(seed);
  q=1-p;
  
  // initially setup the tours
  for(i=1;i<=N;i++)
    {
      tau[i]=i;
      tau_p[i]=i;
    }
  
  //construct the distance matrix
  if(graph==1) // make hexagonal graph
    {
      
      dist[1][2]=1;   
      dist[1][3]=1.732050808;
      dist[1][4]=2;  
      dist[1][5]=1.732050808; 
      dist[1][6]=1;   
      
      dist[2][3]=1;
      dist[2][4]=1.732050808;  
      dist[2][5]=2; 
      dist[2][6]=1.732050808;   
      
      dist[3][4]=1;
      dist[3][5]=1.732050808;  
      dist[3][6]=2; 
      
      dist[4][5]=1;
      dist[4][6]=1.732050808;

      dist[5][6]=1;
    }

  else if (graph==2) // make graph from points in the unit square
    {
      for(i=1;i<=N;i++)
	{
	  pos[i][0]=RN;
	  pos[i][1]=RN;
	}

  
      for(i=1;i<N;i++)
	{
	  for(j=i+1;j<=N;j++)
	    {
	      dist[i][j]=dist[j][i]=pow(((pos[i][0]-pos[j][0])*(pos[i][0]-pos[j][0]))+((pos[i][1]-pos[j][1])*(pos[i][1]-pos[j][1])),0.5);
	    }
	}
    }
  
  // complete the distance matrix by making it symmetrical
  for(i=1;i<N;i++)
    {
      for(j=i+1;j<=N;j++)
	{
	  dist[j][i]=dist[i][j];
	}
    }
  
  // do the neighbourhood move on tau to make tau'
  if(Gn==1)
    one_shift(tau_p, Gi, Gj);

  else if (Gn==2)
    two_p_opt(tau_p, Gi, Gj);


  print_perm(tau);
  print_perm(tau_p);

  printf("the true difference is %lf\n", Explength(tau_p)-Explength(tau));

  if(Gn == 1)
    printf("= %lf\n", shiftE_ij(Gi,Gj,tau));
  else if (Gn==2)
    printf("= %lf\n", deltaE_ij(Gi,Gj,tau));

}

double Explength(int *tau)
{
  int j,r;
  double sum=0.0;
  double coeff;
  double d;
  
  printf("The calculation of expected length for\n");
  print_perm(tau);
  printf("is given by:\n");
  
  for(j=1;j<=N;j++)
    {
      for(r=1;r<=(N-1);r++)
	{       
	  coeff=p*p*pow((1-p),(r-1));
	  if(SYM)
	    printf("p^2*(1-p)^(r-1) * d(%d,%d) = ",tau[j],tau[joshmod(j+r)]);
	  
	  printf("%lf * %lf^(%d-1) * d(%d,%d) = %lf * ", p*p, 1-p, r, tau[j],tau[joshmod(j+r)], coeff);
	  d = dist[tau[j]][tau[joshmod(j+r)]];
	  sum += d * coeff;
	  printf("%lf = %lf) + \n", d, d*coeff);
	}
    }
  //  if(SYM==0)
  printf(" = %lf\n",sum);
  return(sum);
}

double deltaE_iiplusone(int i, int *tau)
{
  double val;
  val=p*p*p*( (fA(i,2,tau)/(1-p)) - (fB(i,1,tau)-fB(i,N-1,tau)) - (fA(i+1,1,tau) - fA(i+1,N-1,tau)) + (fB(i+1,2,tau)/(1-p)));
  printf("delta E_%d,%d = %lf\n", i, i+1, val); 
  return(val);
}

/*---------------- 1-shift Bertsimas recursive delta E evaluation --------*/
double shiftE_ij(int i, int j, int *tau)
{
  double x=0;
  double y=0;
  int k=j-i;
  double q=1-p;

  if(j-i==1)
    return(deltaE_iiplusone(i+1,tau));

  //printf("delta E'_%d,%d ", i,j);
  
  printf("Bertsimas delta E_%d,%d = \n", i,j);

  printf("( %lf * [ \n", p*p);

  //y+=p*p*((pow(q,-k)-pow(q,-(k-1)))*fA(i,k+1,tau) + (pow(q,k)-pow(q,k-1))*(fB(i,1,tau)-fB(i,N-k,tau)) + (q-1)*(fA(j,1,tau)-fA(j,N-k,tau)) + (pow(q,-1)-1) * fB(j,k+1,tau) + (pow(q,N-k)-pow(q,N-(k-1)))*(fA(i,1,tau)-fA(i,k,tau)) + (pow(q,k-N)-pow(q,(k-1)-N))*fB(i,N-k+1,tau) + (1 - pow(q,-1)) * fA(j,N-k+1,tau) + (1 - q)*(fB(j,1,tau)-fB(j,k,tau)));
  
  y+= (pow(q,-k)-pow(q,-(k-1)))*fA(i,k+1,tau);
  printf("%lf * %lf (= %lf) +\n",pow(q,-k)-pow(q,-(k-1)), fA(i,k+1,tau),(pow(q,-k)-pow(q,-(k-1)))*fA(i,k+1,tau));

  y+= (pow(q,k)-pow(q,k-1))*(fB(i,1,tau)-fB(i,N-k,tau));
  printf("%lf * %lf (= %lf)+\n",pow(q,k)-pow(q,k-1),fB(i,1,tau)-fB(i,N-k,tau),(pow(q,k)-pow(q,k-1))*(fB(i,1,tau)-fB(i,N-k,tau)) );

  y+= (q-1)*(fA(j,1,tau)-fA(j,N-k,tau));
  printf("%lf * %lf (= %lf)+\n",(q-1), fA(j,1,tau)-fA(j,N-k,tau),(q-1)*(fA(j,1,tau)-fA(j,N-k,tau)));

  y+= (pow(q,-1)-1) * fB(j,k+1,tau);
  printf("%lf * %lf (= %lf)+\n",pow(q,-1)-1,fB(j,k+1,tau),(pow(q,-1)-1) * fB(j,k+1,tau) );

  y+= (pow(q,N-k)-pow(q,N-(k-1)))*(fA(i,1,tau)-fA(i,k,tau));
  printf("%lf * %lf (= %lf) +\n",pow(q,N-k)-pow(q,N-(k-1)), fA(i,1,tau)-fA(i,k,tau),(pow(q,N-k)-pow(q,N-(k-1)))*(fA(i,1,tau)-fA(i,k,tau)));

  y+= (pow(q,k-N)-pow(q,(k-1)-N))*fB(i,N-k+1,tau);
  printf("%lf * %lf (= %lf) +\n", pow(q,k-N)-pow(q,(k-1)-N),fB(i,N-k+1,tau),(pow(q,k-N)-pow(q,(k-1)-N))*fB(i,N-k+1,tau));

  y+= (1 - pow(q,-1)) * fA(j,N-k+1,tau);
  printf("%lf * %lf (= %lf)+\n", 1 - pow(q,-1),fA(j,N-k+1,tau),(1 - pow(q,-1)) * fA(j,N-k+1,tau));

  y+= (1 - q)*(fB(j,1,tau)-fB(j,k,tau));
  printf("%lf * %lf (= %lf) ]\n", (1 - q),fB(j,1,tau)-fB(j,k,tau),(1 - q)*(fB(j,1,tau)-fB(j,k,tau)));

  y *= p*p;
  printf(" = %lf) + \n", y);
  
//  printf(" = %lf) + (", y);
  
  if(j-i==2)
    x=deltaE_iiplusone(i,tau);
  
  else if(j-i>2)
    x=shiftE_ij(i,j-1,tau);


  x+=y;

  return(x);
}	 

/*---------------- 2-p-opt Bertsimas recursive delta E evaluation --------*/
double deltaE_ij(int i, int j, int *tau)
{
  double x=0;
  double y=0;
  int k=j-i;
  double q=1-p;
  
  if(j-i==1)
    return(deltaE_iiplusone(i+1,tau));

  printf("Bertsimas delta E_%d,%d = \n", i,j);

  printf("( %lf * [ \n", p*p);

  /*
  printf("1:(q^-k-1=%lf)*(A_i,k+1=%lf) +\n", pow(q,-k)-1, fA(i,k+1,tau));
  printf("2:(q^k-1=%lf)*((B_i,1=%lf)-(B_i,n-k=%lf)) +\n", pow(q,k)-1, fB(i,1,tau), fB(i,N-k,tau));
  printf("3:(q^k-1=%lf)*((A_j,1=%lf)-(A_j,n-k=%lf)) +\n", pow(q,k)-1, fA(j,1,tau), fA(j,N-k,tau));
  printf("4:(q^-k-1=%lf)*(B_j,k+1=%lf) +\n", pow(q,-k)-1, fB(j,k+1,tau));
  printf("5:(q^(n-k)-1=%lf)*((A_i,1=%lf)-(A_i,k=%lf)) +\n", pow(q,N-k)-1, fA(i,1,tau), fA(i,k,tau));
  printf("6:(q^(k-n)-1=%lf)*(B_i,n-k+1=%lf) +\n", pow(q,k-N)-1, fB(i,N-k+1,tau));
  printf("7:(q^(k-n)-1=%lf)*(A_j,n-k+1=%lf) +\n", pow(q,k-N)-1, fA(j,N-k+1,tau));
  printf("8:(q^(n-k)-1=%lf)*((B_j,1=%lf)-(B_j,k=%lf))] = \n", pow(q,N-k)-1, fB(j,1,tau), fB(j,k,tau));

  //  y=p*p*((pow(q,-k)-1)*fA(i,k+1,tau) + (pow(q,k)-1)*(fB(i,1,tau)-fB(i,N-k,tau)) + (pow(q,k)-1)*(fA(j,1,tau)-fA(j,N-k,tau)) + (pow(q,-k)-1) * fB(j,k+1,tau) + (pow(q,N-k)-1)*(fA(i,1,tau)-fA(i,k,tau)) + (pow(q,k-N)-1)*fB(i,N-k+1,tau) + (pow(q,k-N)-1) * fA(j,N-k+1,tau) + (pow(q,N-k)-1)*(fB(j,1,tau)-fB(j,k,tau)));
  */

  y += (pow(q,-k)-1)*fA(i,k+1,tau);
  printf("%lf * %lf (= %lf) +\n", pow(q,-k)-1,fA(i,k+1,tau),(pow(q,-k)-1)*fA(i,k+1,tau));
  
  y += (pow(q,k)-1)*(fB(i,1,tau)-fB(i,N-k,tau));
  printf("%lf * %lf (= %lf) +\n",pow(q,k)-1,(fB(i,1,tau)-fB(i,N-k,tau)),(pow(q,k)-1)*(fB(i,1,tau)-fB(i,N-k,tau)) );
  
  y += (pow(q,k)-1)*(fA(j,1,tau)-fA(j,N-k,tau));
  printf("%lf * %lf (= %lf) +\n",pow(q,k)-1,(fA(j,1,tau)-fA(j,N-k,tau)), (pow(q,k)-1)*(fA(j,1,tau)-fA(j,N-k,tau)));
  
  y += (pow(q,-k)-1) * fB(j,k+1,tau);
  printf("%lf * %lf (= %lf) +\n", pow(q,-k)-1, fB(j,k+1,tau),(pow(q,-k)-1) * fB(j,k+1,tau));
  
  y += (pow(q,N-k)-1)*(fA(i,1,tau)-fA(i,k,tau));
  printf("%lf * %lf (= %lf) +\n", pow(q,N-k)-1,fA(i,1,tau)-fA(i,k,tau),(pow(q,N-k)-1)*(fA(i,1,tau)-fA(i,k,tau)));
  
  y += (pow(q,k-N)-1)*fB(i,N-k+1,tau);
  printf("%lf * %lf (= %lf) +\n",pow(q,k-N)-1, fB(i,N-k+1,tau),(pow(q,k-N)-1)*fB(i,N-k+1,tau));
  
  
  y += (pow(q,k-N)-1) * fA(j,N-k+1,tau);
  printf("%lf * %lf (= %lf) +\n", (pow(q,k-N)-1),fA(j,N-k+1,tau),(pow(q,k-N)-1) * fA(j,N-k+1,tau));
  
 
  y += (pow(q,N-k)-1)*(fB(j,1,tau)-fB(j,k,tau));
  printf("%lf * %lf (= %lf) ]\n",pow(q,N-k)-1,fB(j,1,tau)-fB(j,k,tau),(pow(q,N-k)-1)*(fB(j,1,tau)-fB(j,k,tau)));
  
  y *= p*p;
  printf(" = %lf) + \n", y);
    
  if(j-i==2)
    x=deltaE_iiplusone(i+1,tau);

  else if(j-i>2)
    x=deltaE_ij(i+1,j,tau);
  
  x+=y;
 
  return(x);
}

double fA(int i, int k, int *tau)
{
  double sum=0.0;
  int r;

  for(r=k;r<=(N-1);r++)
    {
      sum += pow((1-p),(r-1)) * dist[tau[joshmod(i)]][tau[joshmod(i+r)]];
      // printf("(A_%d,%d = %d) ", i, k, dist[tau[joshmod(i)]][tau[joshmod(i+r)]]);
    }
  // printf("(A_%d,%d = %lf) ", i, k, sum);
  return(sum);

}

double fB(int i, int k, int *tau)
{
  double sum=0.0;
  int r;

  for(r=k;r<=(N-1);r++)
    {
      sum += pow((1-p),(r-1)) * dist[tau[joshmod(i-r)]][tau[joshmod(i)]];
      //    printf("r=%d\n",r);
      // printf("%d %d\n", joshmod(i-r), joshmod(i));
      // printf("%d %d\n", tau[joshmod(i-r)], tau[joshmod(i)]);
      //    printf("(B_%d,%d = %d) ", i, k, dist[tau[joshmod(i-r)]][tau[joshmod(i)]]);
    }
  return(sum);
}

int joshmod(int i)
{
  if(i%N==0)
    return N;
  else if(i>0)
    return(i%N);
  else
    return((i+N)%N);
}
	     
void print_perm(int *tau)
{
  int i;
  for(i=1;i<=N;i++)
    {
      printf("%d,",tau[i]);
    }
  printf("\n");
}

void one_shift(int *tau, int i, int j)
{
  int k;
  int tmp;
  
  tmp = tau[i];
  for(k=i;k<j;k++)
    tau[k]=tau[k+1];

  tau[j]=tmp;
}

void two_p_opt(int *tau, int i, int j)
{
  int k;
  int c=0;
  int d=0;
  int tmp[N];

  for(k=i;k<=j;k++)
    {
      tmp[c]=tau[k];
      c++;
    }

  
  for(k=c-1;k>=0;k--)
    {
      tau[i+d]=tmp[k];
      d++;
    }
}


void print_header()
{
  printf("/**********************************************************************
   bertsimas.c  

   Copyright (C) 2002, Joshua Knowles.


   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version. 

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details. 

   The GNU General Public License is available at:
      http://www.gnu.org/copyleft/gpl.html
   or by writing to: 
        The Free Software Foundation, Inc., 
        675 Mass Ave, Cambridge, MA 02139, USA.  

***********************************************************************
 
  Purpose
  ~~~~~~~

  This program calculates the difference between the expected lengths
  of two neighbouring probabilistic TSP (pTSP) tours, tau and
  tau'. Two different neighbourhoods are defined (and can be selected
  by a command line parameter). They are the 1-shift neighbourhood and
  the 2-p-opt neighbourhood.

  The two tours are a tour of six nodes, tau = 1,2,3,4,5,6 and a tour
  tau' which is the result of applying the neighbourhood operator to
  tau.

  Both the 2-p-opt and 1-shift operators are controlled by two
  parameters, i and j. The 2-p-opt neighbourhood operator reverses the
  ordering of nodes in positions i...j in the tour. The 1-shift
  operator moves the node at position i to position j and shifts all
  of the intervening nodes one space back. Here follow two examples:

  2p-opt with i=2, j=5 tau = 1,2,3,4,5,6 -> tau' = 1,5,4,3,2,6

  1-shift with i=2, j=5 tau = 1,2,3,4,5,6 -> tau' = 1,3,4,5,2,6
  
  The purpose of the software is to demonstrate that some recursive
  equations proposed by Bertsimas for calculating the expected
  length difference between neighbouring tours is incorrect.

  To do this, the program first calculates the expected length
  difference by making an explicit calculation of the expected length
  of each tour and then taking the difference. Then the appropriate
  Bertsimas recursive equation is used to calculate the expected
  difference. By comparing the results of each calculation (and by
  checking the code herein if necessary) the error in the Bertsimas
  equations should be established.


  Instructions
  ~~~~~~~~~~~~

  To compile: gcc bertsimas.c -o bertsimas -lm

  To run: ./bertsimas [-h] [-n neighbourhood] [-p probability] 
[-g graph] [-i i] [-j j] [-s seed]
   
  where all of the command line options are optional and are described
  below.  Running the code without any command line parameters is
  equivalent to running it with the following command line:

  ./bertsimas -n 2 -p 0.5 -g 1 -i 2 -j 5

  This calculates the difference between the expected length of two
  tours: tau  = 1,2,3,4,5,6 and tau' = 1,5,4,3,2,6 where the nodes are
  on the vertices of a regular hexagon of side 1.

  For other calculations see the command line parameters section below.

  --
   
  Command line parameters:
  
  [-h] prints out these instructions

  [-n neighbourhood] selects the neighbourhood operator, 1-shift or
  2-p-opt. The neighburhood parameter is given the value 1 or 2, as
  appropriate
         
  [-p probability] sets the probability of each node being in the
  tour. The probability parameter takes a real number in the range
  (0,1)

  [-g graph] selects the type of graph. Giving graph the value 1
  selects a graph where each node is on the vertex of a regular
  hexagon of side 1. Giving graph the value 2 selects a random
  Euclidean graph in the plane. i.e. each node is at a point in the
  unit square and distances between nodes are their Euclidean distance

  [-i i] sets the i parameter (see Purpose section above).  The
  variable i must be an integer from the set 1..5

  [-j j] sets the j parameter (see Purpose section above).  The
  variable i must be an integer from the set 2..6 and j > i

  [-s seed] sets the random seed value, a long integer. This only
  affects the output if the random Euclidean graph is chosen.

**********************************************************************/\n");
}