/* gerador de redes. Admite varias opcoes
 *
 * NOTA: A cada no' da rede vamos fazer corresponder um indice (posicao no
 *	 no vector "nos") pelo que iremos trabalhar sempre com esses indices
 *	 e so' no fim, e' que iremos utilizar os no's. Assim, sempre que
 *	 for gerado um arco (i, j), esse arco na realidade corresponde ao
 *	 arco (nos[i], nos[j]). Isto torna a distribuicao dos nos mais aleatoria
 *	 e alem disso, simplifica a construcao da rede de pontos e das redes
 *	 aciclicas em geral.
*/

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

/* tipo: 1 -> aleatoria,  2 -> grelha,  3 -> pontos,  4 -> completa
 * n, m, d, r: numero de no's, arcos, densidade e numero de objectivos
 * numS, numT: numeros de no's iniciais e terminais
 * larg, altu: largura e altura da "malha" onde estao os no's
 * orient, ciclo:
 * **dist: vector que ira' conter as distancias de cada arco
 *	   NOTA: dist[0] -> vector "ant" (tail nodes);
 *	         dist[1] -> vector "suc" (head nodes);
 *	         dist[i+1] -> distancias do "i"-esimo objectivo
 * **valor: vector que contem os limites inferiores (valor[0]) e
 *	    superiores (valor[1]) das distancias
 * *point:
 * *nos: coresponde aos no's da rede. Nao deve ser misturado.
 *       nos[i] = j -> j e' o i-esimo no' da rede.
 */

typedef struct
{ int n, m, d, r, numS, numT, ciclo, orient, larg, altu;
  int **dist, **valor, *point, *ant, *suc, *nos, *pontos;
  /* NOTA: os ponteiros "ant" e "suc" vao ser redirecionados
   *       para "dist[0]" e "dist[1], pelo que NAO SE DEVE reservar espaco */
  char tipo;/*tipo: 1 -> aleatoria,  2 -> grelha,  3 -> pontos,  4 -> completa*/
} Rede;

#define maxint 2147483647
#define fmaxint 2147483647.0
#define NmAXsUBiNT 10
#define abs(x) ((x<0)?-x:x)
#define sqr(x) ((x)*(x))

#define NUMaRCOS rede->suc /* numero de arcos que saem do no' "i" */

FILE *ddados;
int tabela[26], /* tabela com numeros inteiros aletorios */
     num1, num2; /* numeros inteiros aleatorios */


int arredonda(x)
  double x;
{ 
   return ( (int) x + 0.5 );

/*  aux = (int) x; if (x - aux >= 0.5) return aux + 1; else return aux;*/
}  /* arredonda */

void inicia()
{ int register x, i;

  if (num1 == 0)
    num1 = maxint;
  num2 = num1 * maxint;
  x = maxint * num1 * num2;
  for (i = 1; ++i < 28; )
    tabela[i-2] = i * x;

  return;
}

int leat(a, b)
  int a, b;
{ double x;
  int indice, aux;
  
  if ( (num1 % 2 == 0) && (num2 % 2 == 0) )
    num1 = num1 + 1;

  /* se os extremos do intervalo estao trocados */
  if (a > b)
  { aux = a;
    a = b;
    b = aux;
  }

  /* escolhe um numero aleatorio "x" no intervalo [0, 1] */
  aux = num1 + num2; /* numero "ainda mais" aleatorio */
  indice = abs(aux) % 26;
  num1 = num2;
  num2 = aux;
  x = abs(tabela[indice]) / fmaxint;

  /* modifica a tabela de numeros aleatorios e os dois numeros (num1 e num2)
   * para nao estar a escolher sempre o mesmo numero */
  tabela[indice] = num1 + num2;
  num1 = num2;
  num2 = tabela[indice];

  aux = (int) (a + (b - a) * x);
  if (aux < a)
    aux = a;
  else
    if (aux > b)
      aux = b;

  return aux;
} /* leat */

/* construir o vector "point" e guardar uma copia dos no's no vector "nos" */
void constroiPoint(point, numArcos, n, m)
  int *point, *numArcos, n, m;
{ register int i;

  point[1] = 1;
  for (i = 0; i++ < n; )
    /* point do no' nos[i] (e nao de "i" como e' habitual) */
    point[i+1] = point[i] + numArcos[i];
  point[n+1] = m + 1;

  return;
} /* constroiPoint */

/* cria um conjunto dos elementos. "n" e' o numero de elementos a criar
 * SAIDA: vector "v" com os elementos de 1 ate' "n" */
void criaElem(v, n)
  int *v, n;
{ register int i;

  for (i = 0; i++ < n; )
    v[i] = i;
  /* ainda nao foi escolhido nenhum no' */
  return;
} /* criaElem */

/* cria um conjunto dos no's como sendo pontos de uma malha larg x altu.
 * "n" e' o numero de no's que devemos criar.
 * SAIDA: vector "v" com os no's escolhidos */
void criaPontos(v, n, larg, altu)
  int *v, n, larg, altu;
{ register int i, aux, novoPonto, j;

  aux = larg*altu;
  for (i = 0; i++ < n; )
  { v[i] = novoPonto = leat(0, aux);
    /* verificar se o novo ponto criado ja' existia */
    /* CUIDADO: ESTA CONDICAO PERMITE GARANTIR QUE NAO HA' PONTOS
     * REPETIDOS, NO ENTANTO, SE A "MALHA" FOR FICAR MUITO SATURADA
     * PODE SER QUE DEMORE MUITO TEMPO A OBTER NOVOS PONTOS NAO REPETIDOS
     * (POIS A PROBABILIDADE DE O PONTO JA' EXISTIR COMECA A SER GRANDE ...)
     * E PODE MESMO NAO PARAR ... */
    for (j = 0; ++j < i; )
      if (v[j] == novoPonto)
      { i--;
	break;
      }
  }

  return;
} /* criaPontos */

void geraDistEuclid(dist, ant, suc, nos, pontos, m, base)
  int *dist, *ant, *suc, *nos, *pontos, m, base;
{ int i;

    for (i = 0; i++ < m; )
      dist[i] = arredonda (( sqrt((double)
		sqr((pontos[nos[ant[i]]]/base) - (pontos[nos[suc[i]]]/base)) +
	       sqr((pontos[nos[ant[i]]]%base) - (pontos[nos[suc[i]]]%base))) ));
} /* geraDistEuclid */

void geraNumeros(v, m, lim_inf, lim_sup)
  int *v, m, lim_inf, lim_sup;
{ int i;

  for (i = 0 ; i++ < m; )
    v[i] = leat(lim_inf, lim_sup);
  return;
} /* geraNumeros */

/* escolhe, aleatoriamente, um elemento do conjunto "v" entre o "limite"
 * primeiros elementos. 
 * ENTRADA: "v" -> conjunto de elementos; "limite" e "pos"
 * SAIDA: elemento escolhido do vector, actualizacao da variavel "pos" */
int escolheElem(v, limite, pos)
  int *v, limite, *pos;
{ 

  /* Escolhe e devolve o elemento (o elemento e' v[pos]) */
  return v[ (*pos) = leat(1, limite) ];
} /* escolheElem */

void escreveArcos(f, dist, ordemNos, ordemArcos, r, m)
  FILE *f;
  int **dist, *ordemNos, *ordemArcos, r, m;
{ int i, j;

  for (i = 0; i++ < m; )
  { fprintf(f, "a\t%d %d ",
            ordemNos[dist[0][ordemArcos[i]]], ordemNos[dist[1][ordemArcos[i]]]);
    for (j = 2; j <= r + 1; j++)
      fprintf(f, "%d ", dist[j][ ordemArcos[i] ]);
    fprintf(f, "\n");
  }
  return;
} /* escreveArcos */

void escrevePontos(f, nos, pontos, n, base)
  FILE *f;
  int *nos, *pontos, n, base;
{ int i;

  for (i = 0; i++ < n; )
    fprintf(f, "v\t%d %d %d\n", nos[i], pontos[nos[i]] / base, pontos[nos[i]] % base);
  fprintf(f, "c\n");
  fflush(f);

  return;
} /* escrevePontos */
 
/* retira o elemento do conjunto "v" na posicao "pos" 
 * ENTRADA: "v" -> conjunto de elementos; "limite" e "pos"
 * SAIDA: conjunto sem o elemento da posicao "pos".
 *	  Actualizacao da variavel "limite" */
void retiraElem(v, limite, pos)
  int *v, *limite, pos;
{ int aux;

  /* deslocar o elemento escolhido para o "limite" do conjunto. Assim, este
   * elemento nao sera' escolhido novamente. */
  aux = v[pos];
  v[pos] = v[*limite];
  v[*limite] = aux;

  /* actualizar o "limite" */
  (*limite)--;

  return;
} /* retiraElem */

/* escolhe "n" no's da rede escreve-os no ficheiro. A variavel "str" indicara'
 * se sao no's iniciais ou terminais */
void escolheNos(f, str, v, ordemNos, n, limite)
  FILE *f;
  char *str;
  int *v, *ordemNos, n, *limite;
{ int i, pos;

  fprintf(f, "%s\t", str);
  for (i = 0; i++ < n; )
  { fprintf(f, "%d ", ordemNos[escolheElem(v, *limite, &pos)]);
    retiraElem(v, limite, pos);
  }
  fprintf(f, "\nc\n");
  fflush(f);
  return;
} /* escolheNos */

/* Mistura os elementos do conjunto (assim torna-se mais aleatorio o processo
 * da escolha de um elemento de um conjunto) */
void misturaElem(v, n)
  int *v, n;
{ int i, limite, pos;

  limite = n;
  for (i = 1; i++ < n; )
  { escolheElem(v, limite, &pos);
    retiraElem(v, &limite, pos);
  }
  return;
} /* misturaNos */

void reservaMemoria(rede, ordemArcos, conj)
  Rede *rede;
  int **ordemArcos, **conj;
{ int i;

  if (! ( (*conj) = (int *) malloc(sizeof(int)*(rede->n+3))) ) goto saida;
  if (! ( (rede->point) = (int *) malloc(sizeof(int)*(rede->n+3)))) goto saida;
  if (! ( (rede->nos) = (int *) malloc(sizeof(int)*(rede->n+3))) ) goto saida;
  if (! ( (rede->pontos) = (int *) malloc(sizeof(int)*(rede->n+3))) )goto saida;
  if (! ( (*ordemArcos) = (int *) malloc(sizeof(int)*(rede->m+3))) ) goto saida;
  if (! ((rede->dist) = (int **) malloc(sizeof(int*)*(rede->r+2))) ) goto saida;
  for (i = 0 ; i <= rede->r+1; i++)
    if (!(rede->dist[i] = (int *) malloc(sizeof(int)*(rede->m+3))) ) goto saida;
  if (! ( (rede->valor) = (int **) malloc(sizeof(int*)*(2))) ) goto saida;
  if (! (rede->valor[0] = (int *) malloc(sizeof(int)*(rede->r+1))) ) goto saida;
  if (! (rede->valor[1] = (int *) malloc(sizeof(int)*(rede->r+1))) ) goto saida;

  rede->ant = rede->dist[0]; rede->suc = rede->dist[1];

  return;

saida:
  perror("Error in the allocated memory space\n");
  exit(0);
} /* reservaMemoria */

void lerDados(rede, ordemArcos, conj, numSubInt)
  Rede *rede;
  int **ordemArcos, **conj, *numSubInt;
{ int aux;
  register int i;

  printf("Seed number: ");
  scanf("%d", &num1);
  fprintf(ddados, "%d\n", num1);

  if ( (rede->tipo == '2') || (rede->tipo == '3') )
  { printf("Mesh width: ");
    scanf("%d", &rede->larg);
    fprintf(ddados, "%d\n", rede->larg);
    printf("Mesh height: ");
    scanf("%d", &rede->altu);
    fprintf(ddados, "%d\n", rede->altu);
  }

  /* ler o numero de no's */
  switch(rede->tipo)
  { case '1' : ;
    case '4' : printf("Number of nodes: ");
	       scanf("%d", &rede->n);
    	       fprintf(ddados, "%d\n", rede->n);
	       break;
    case '2' : (rede->n) = (rede->larg) * (rede->altu);
	       break;
    case '3' : printf("Number of nodes (OBS: n ~ width*height/10 = %d) : ",
			(rede->larg)*(rede->altu)/10);
	       scanf("%d", &rede->n);
    	       fprintf(ddados, "%d\n", rede->n);
	       if (rede->n > (rede->larg)*(rede->altu))
	       { printf("There are no so much point in the mesh.\n");
		 printf("We assume for n the maximum number of admissible nodes,\n");
		 printf("that is, %d\n",
			(rede->larg)*(rede->altu));
		 rede->n = (rede->larg)*(rede->altu);
	       }
	       printf("(NOTE: Saturation degree: %5.2f%%)\n",
			((rede->n)*100.0)/((rede->larg)*(rede->altu)));
	       break;
    default  : break;
  } /* switch */

  /* ler o numero de arcos */
  switch( rede->tipo )
  { case '1' : ;
    case '3' : printf("Number of arcs: "); 
	       scanf("%d", &rede->m);
    	       fprintf(ddados, "%d\n", rede->m);
	       if (rede->n > rede->m)
	       { printf("The number of arcs have to be greater than the number of nodes.\n");
		 exit(0);
	       }
	       else
	       /* Se "m" e' maior que o maximo dos arcos que a rede pode ter */
	       if (rede->ciclo && rede->orient)
	       { if (rede->m > (rede->n)*((rede->n) - 1))
		   (rede->m) = (rede->n)*((rede->n) - 1);
	       }
	       else
	       { if (rede->m > ((rede->n)*((rede->n) - 1)) / 2)
		   (rede->m) = ((rede->n)*((rede->n) - 1)) / 2;
	       }
	       break;
    case '2' : printf("Netwok density: ");
	       scanf("%d", &rede->d);
    	       fprintf(ddados, "%d\n", rede->d);
	       if (rede->d == 3)
	       { /* nao se deve simplificar a expressao, pois assim considera
		  * os casos par e impar das variaveis */
		  (rede->m) = (rede->altu - 1)*(rede->larg) +
			      ((rede->altu)/2)*(rede->larg - 1);
		 /* se a altura e' impar, e' preciso acrescentar alguns arcos */
		 if ((rede->altu) % 2)
		   (rede->m) += (rede->larg)/2;
	       }
	       else
	         if (rede->d == 5)
	         { (rede->m) = arredonda(((rede->larg - 1)*(rede->altu - 1)*(rede->d) +
		      2*(rede->larg + rede->altu -2))/2.0);
	         }
	         else
	           if (rede->d == 7)
	           { /* arcos = numero de arcos para densidade 6 mais uns quantos */
	             (rede->m) = ((rede->larg - 1)*(rede->altu - 1)*6 +
		        2*(rede->larg + rede->altu -2))/2 +
		        (rede->larg - 1)*((rede->altu)/2);
	           }
	           else
                     (rede->m) =
		       ((rede->larg - 1)*(rede->altu - 1)*(rede->d) +
		        2*(rede->larg + rede->altu -2))/2;

	       if (rede->ciclo && rede->orient)
	         (rede->m) = 2*(rede->m);
	       break;
    case '4' : if (rede->ciclo && rede->orient)
	         (rede->m) = (rede->n)*((rede->n) - 1);
	       else
	         (rede->m) = ((rede->n)*((rede->n) - 1)) / 2;
	       break;
    default  : break;
  } /* switch */

  printf("Number of source nodes (>= 0): ");
  scanf("%d", &rede->numS);
  fprintf(ddados, "%d\n", rede->numS);
  if (rede->numS > rede->n)
  { printf("The number of source nodes cannot be greater than the total number of nodes.\n");
    exit(0);
  }
  else
    if (rede->numS < 0)
    { printf("You cannont choose a negative number of source nodes.\n");
      exit(0);
    }
  printf("Number of target nodes (>= 0): ");
  scanf("%d", &rede->numT);
  fprintf(ddados, "%d\n", rede->numT);
  if (rede->numT < 0)
  { printf("You cannont choose a negative number of traget nodes.\n");
    exit(0);
  }
  else
    if (rede->numS + rede->numT > rede->n)
    { printf("The sum of sorce and target nodes cannot be greater than the total number of nodes.\n");
      exit(0);
    }

  printf("Number of criteria (>=1): ");
  scanf("%d", &rede->r);
  fprintf(ddados, "%d\n", rede->r);
  if (rede->r < 1)
  { printf("The number of criteria should be positive. We assume you choose the mono-criterion case (k =1)\n");
    rede->r = 1;
  }

  reservaMemoria(rede, ordemArcos, conj);

  if (rede->tipo == '3')
    aux = 1;
  else
    aux = 0;
  for (i = aux; i++ < rede->r; )
  { printf("Indicate the lower and upper bound for the objective %d: ", i);
    scanf("%d %d", &(rede->valor[0][i]), &(rede->valor[1][i]));
    fprintf(ddados, "%d %d\n", rede->valor[0][i], rede->valor[1][i]);
    if (rede->valor[0][i] > rede->valor[1][i])
    { aux = rede->valor[0][i];
      rede->valor[0][i] = rede->valor[1][i];
      rede->valor[1][i] = aux;
    }
  }

  if (rede->r == 2)
  { printf("How many sub-intervals do you like to split the values for the ");
    printf("second criterion (>=1 and <=10): ");
    scanf("%d", numSubInt);
    fprintf(ddados, "%d", *numSubInt);
    if (*numSubInt < 1)
    { printf("We assume you do not slpit the interval.\n");
      *numSubInt = 1;
    }
    else
      if (*numSubInt > NmAXsUBiNT)
      { printf("We assume you split the interval in ");
	printf("%d sub-intervals.\n", NmAXsUBiNT);
        *numSubInt = NmAXsUBiNT;
      }
  }
} /* lerDados */

/* Le as caracteristicas da rede */
void lerTipo(rede)
  Rede *rede;
{

  printf("\t\t##################\n");
  printf("\t\t#  1 - Random    #\n");
  printf("\t\t#  2 - Grid      #\n");
  printf("\t\t#  3 - Euclidean #\n");
  printf("\t\t#  4 - Complete  #\n");
  printf("\t\t##################\n");
  printf("\nChoose the type of network: ");
  rede->tipo = getchar();
  fprintf(ddados, "%c\n", rede->tipo);
  /* tipo: 1 -> aleatoria,  2 -> grelha,  3 -> pontos,  4 -> completa */
  if( (rede->tipo < '1') || (rede->tipo > '4') )
  { printf("Wrong option. We assume for default Random networks.\n");
    rede->tipo = '1';
  }

  printf("\n\n\n0 - acyclic        1 - cyclic      -> ");
  scanf("%d", &rede->ciclo);
  fprintf(ddados, "%d\n", rede->ciclo);
  if( (rede->ciclo < 0) || (rede->ciclo > 1) )
  { printf("Wrong option. We assume for default cyclic networks.\n");
    rede->ciclo = 1;
  }

  if ( (rede->ciclo) )
  { printf("\n\n\n0 - undirected        1 - directed      -> ");
    scanf("%d", &rede->orient);
    fprintf(ddados, "%d\n", rede->orient);
    if( (rede->orient < 0) || (rede->orient > 1) )
    { printf("Wrong option. We assume for default direct networks.\n");
      rede->orient = 1;
    }
  }
  else
    rede->orient = 1;

  return;
} /* lerTipo */

/* gera os arcos de uma rede aciclica orientada, isto e', para cada arco
 * determina o "tail" (vector ant) e o "head" (vector suc) no'
 * NOTA: E' usado em redes aleatorias e euclidianas */
void redeAcicloOrient(conj, rede)
  int *conj;
  Rede *rede;
{ register int i, k, j, kb;
  int nosNaoSat, limite, pos;

  /* atribuir um arco a cada no', menos ao ultimo, para garantir que existe uma
   * cadeia hamiltoniana */
  for (i = 0; ++i < rede->n; )
    NUMaRCOS[i] = 1;
  NUMaRCOS[rede->n] = 0;

  /* para cada um dos restantes "m-n+1" arcos, escolher o "tail" no' do arco */
  /* do ultimo no' nao devem sair arcos, e do penultimo so' deve sair um */
  criaElem(conj, rede->n);
  misturaElem(conj, rede->n - 2);
  limite = rede->n - 2;

  for (k = 0; k++ <= rede->m - rede->n; )
  { /* escolher o indice dum no' nao saturado */
    i = escolheElem(conj, limite, &pos);
    /* acresentar um arco a esse no' e se estiver saturado retirar-lo 
     * NOTA: Como estou a considerar arcos (nos[i], nos[j]) com i < j entao
     *       terei no maximo n - i arcos associados ao no' nos[i] */
    if ( (++NUMaRCOS[i]) == rede->n - i )
      retiraElem(conj, &limite, pos);
  }
  nosNaoSat = limite;

  /* construir o vector "point" */
  constroiPoint(rede->point, NUMaRCOS, rede->n, rede->m);

  /* para cada no' saturado, indicar os seus arcos que serao da forma
   * (nos[i], nos[j]) com j > i */
  /* NOTA: Como do ultimo no' nao saem arcos, entao nao e' necessario tratar-lo
   * no ciclo */
  for (i = nosNaoSat; ++i < rede->n; )
    for (j = i, k = rede->point[i]; j++ < rede->n; k++)
    { rede->suc[k] = j;
      rede->ant[k] = i;
    }

  /* para cada no' nao saturado, determinar o "head" no' de cada arco
   * NOTA: A cadeia hamiltoniana fica automaticamente construida */
  for (i = 0; i++ < nosNaoSat; )
  { /* Criar o arco (nos[i], nos[i+1]) */
    rede->suc[k = rede->point[i]] = i+1;
    rede->ant[k] = i;
    /* Queremos arcos da forma (nos[i], nos[j]) com i < j. Logo terei de
     * inicializar "conj" com as "n-i-1" componentes do conjunto com os indices
     * possiveis a escolher (note-se que ja escolhi o arco (nos[i], nos[i+1]))*/
    for (j = i + 1; j < rede->n; )
      conj[j - i] = ++j;
    limite = rede->n - i - 1;
    misturaElem(conj, limite);
    /* para cada arco que se inicie em "nos[i]" */
    for (kb = rede->point[i+1]; ++k < kb; )
    { j = escolheElem(conj, limite, &pos);
      retiraElem(conj, &limite, pos);
      rede->ant[k] = i;
      rede->suc[k] = j;
    }
  }
  return;
} /* redeAcicloOrient */

/* gera os arcos de uma rede ciclica orientada, isto e', para cada arco
 * determina o "tail" (vector ant) e o "head" (vector suc) no'
 * NOTA: E' usado em redes aleatorias e euclidianas */
void redeCicloOrient(conj, rede)
  int *conj;
  Rede *rede;
{ register int i, k, j, kb;
  int nosNaoSat, limite, pos;

  /* atribuir um arco a cada no' para garantir que existe um ciclo
   * hamiltoniano */
  for (i = 0; i++ < rede->n; )
    NUMaRCOS[i] = 1;

  /* criar o conjunto dos indices dos no's e misturar-los */
  criaElem(conj, rede->n);
  misturaElem(conj, rede->n);
  limite = rede->n;
  /* para cada um dos restantes arcos, escolher o "tail" no' do arco */
  for (k = 0; k++ < rede->m - rede->n; )
  { /* escolher um indice nao saturado */
    i = escolheElem(conj, limite, &pos);
    /* acresentar um arco a esse indice e se estiver saturado retirar-lo */
    if ( (++NUMaRCOS[i]) == rede->n - 1 )
      retiraElem(conj, &limite, pos);
  }

  /* construir o vector "point" */
  nosNaoSat = limite;

  constroiPoint(rede->point, NUMaRCOS, rede->n, rede->m);

  /* para cada indice saturado, indicar os seus arcos que serao (nos[i], nos[j])
   * com j != i */
  for (i = nosNaoSat; i++ < rede->n; )
  { for (j = 0, k = rede->point[i]; ++j < i; k++)
    { rede->suc[k] = j;
      rede->ant[k] = i;
    }
    for ( ; j++ < rede->n; k++)
    { rede->suc[k] = j;
      rede->ant[k] = i;
    }
  }

  /* Construi o trajecto (ciclo) hamiltoniano */
  for (i = 0; i++ < nosNaoSat; )
    /* Criar o arco (nos[i], nos[i+1]) */
    rede->suc[rede->point[i]] = i+1;

  /* se nao ha' no's saturados, entao criamos o arco (nos[n], nos[n+1]) em
   * vez de (nos[n], nos[1]) */
  if (nosNaoSat == rede->n)
    rede->suc[rede->point[rede->n]] = 1;

  /* para cada indice nao saturado, determinar o "head" no' de cada arco */
  for (i = 0; i++ < nosNaoSat; )
  { /* NOTA: Ja' criamos o "head" no' ("suc") do arco (nos[i], nos[i+1]) */
    rede->ant[k = rede->point[i]] = i;
    /* para cada arco que se inicie em "nos[i]" */
    limite = rede->n;
    for (kb = rede->point[i+1]; ++k < kb; )
    { j = escolheElem(conj, limite, &pos);
      retiraElem(conj, &limite, pos);
      /* se o arco (nos[i], nos[j]) e' um laco ou coincide com o primeiro arco
       * definido para nos[i], entao devemos ignorar-lo */
      if ( (j == i) || (j == i+1) )
      { k--;
	continue;
      }
      rede->ant[k] = i;
      rede->suc[k] = j;
    }
  }
  /* se nao ha' no's saturados, entao "nosNaoSat == n", e portanto na ultima
   * passagem do ciclo mais externo (i = n) vamos comparar "j" com "n" e com
   * "n+1" em vez de "n" e "1", logo e' preciso retificar esse ERRO.
   * SE "n == nosNaoSat" ENTAO GERAR
   * NOVAMENTE OS SUCESSORES DOS ARCOS QUE SE INICIAM EM "i" INDEPENDENTEMENTE
   * DE NUNCA TER SIDO ESCOLHIDO O INDICE "1" MAIS DO QUE UMA VEZ !!! */
  if ( (nosNaoSat == rede->n) && ((k = rede->point[rede->n]) < rede->m) )
  { /* NOTA: Ja' criamos o "head" no' ("suc") e o "tail" no' do
     * arco (nos[i], nos[i+1]) */
    /* Para cada arco que se inicie em "nos[i]" */
    limite = rede->n;
    for (kb = rede->point[i+1]; ++k < kb; )
    { j = escolheElem(conj, limite, &pos);
      retiraElem(conj, &limite, pos);
      /* se o arco (nos[i], nos[j]) e' um laco ou coincide com o primeiro arco
       * definido para nos[i], entao devemos ignorar-lo */
      if ( (j == i) || (j == 1) )
      { k--;
	continue;
      }
      rede->ant[k] = i;
      rede->suc[k] = j;
    }
  }
  return;
} /* redeCicloOrient */

void grelhaAcic_d3(rede)
  Rede *rede;
{ register int i, j, k, par;

  k = 0;
  /* para todas as linhas menos para a ultima */
  for (i = 0; i < rede->altu - 1; i++)
  { /* para todos os no's, menos o ultimo, da linha "i+1" */
    par = i % 2;
    for (j = 0; ++j < rede->larg; )
    { /* construir os arcos */
      rede->ant[++k] = i*rede->larg + j; rede->suc[k] = (i+1)*rede->larg + j;
      if ( par = (++par) % 2)
      { rede->ant[++k] = i*rede->larg + j; rede->suc[k] = i*rede->larg + j + 1;}
    }
    rede->ant[++k] = i*rede->larg + j; rede->suc[k] = (i+1)*rede->larg + j;
  }
  par = i % 2;
  /* para todos os no's, menos o ultimo, da linha "i+1" */
  for (j = i*rede->larg; ++j < rede->n; )
  { /* construir os arcos */
    if ( par = (++par) % 2)
    { rede->ant[++k] = j; rede->suc[k] = j + 1;}
  }

  return;
} /* grelhaAcic_d3 */

/* gera os arcos de uma grelha aciclica orientada
 * a rede e' da forma:
 * (altu-1)*larg+1 --> (altu-1)larg+2 --> (altu-1)larg+3 --> ... --> altu*larg
 *         ^ 		      ^		         ^	                 ^
 *         |		      |		         |	                 |
 *         :		      :		         :	                 :
 *         ^ 		      ^		         ^	                 ^
 *         |		      |		         |	                 |
 *      larg+1     -->     larg+2     -->     larg+3     --> ... -->   2*larg
 *         ^ 		      ^		         ^	                 ^
 *         |		      |		         |	                 |
 *         1 	   -->	      2	      -->	 3	 --> ... -->    larg
 */
void grelhaAcic_d4(rede)
  Rede *rede;
{ register int i, j, k;

  k = 0;
  /* para todas as linhas menos para a ultima */
  for (i = 0; i < rede->altu - 1; i++)
  { /* para todos os no's, menos o ultimo, da linha "i+1" */
    for (j = 0; ++j < rede->larg; )
    { /* construir os arcos */
      rede->ant[++k] = i*rede->larg + j; rede->suc[k] = i*rede->larg + j + 1;
      rede->ant[++k] = i*rede->larg + j; rede->suc[k] = (i+1)*rede->larg + j;
    }
    rede->ant[++k] = i*rede->larg + j; rede->suc[k] = (i+1)*rede->larg + j;
  }
  /* para todos os no's, menos o ultimo, da linha "i+1" */
  for (j = i*rede->larg; ++j < rede->n; )
  { /* construir os arcos */
    rede->ant[++k] = j; rede->suc[k] = j + 1;
  }

  return;
} /* grelhaAcic_d4 */

void grelhaAcic_d5(rede)
  Rede *rede;
{ register int i, j, k;

  k = 0;
  /* para todas as linhas menos para a ultima */
  for (i = 0; i < rede->altu - 1; i++)
  { /* para todos os no's, menos o ultimo, da linha "i+1" */
    for (j = 0; ++j < rede->larg; )
    { /* construir os arcos */
      rede->ant[++k] = i*rede->larg + j; rede->suc[k] = i*rede->larg + j + 1;
      rede->ant[++k] = i*rede->larg + j; rede->suc[k] = (i+1)*rede->larg + j;
    }
    rede->ant[++k] = i*rede->larg + j; rede->suc[k] = (i+1)*rede->larg + j;
  }
  /* para todos os no's, menos o ultimo, da linha "i+1" */
  for (j = i*rede->larg; ++j < rede->n; )
  { /* construir os arcos */
    rede->ant[++k] = j; rede->suc[k] = j + 1;
  }

  /* Construir os arcos "diagonais" */

  /* para todas as linhas impares menos para a ultima */
  for (i = 0; i < rede->altu - 1; i+=2)
  { /* para todos os no's (de dois em dois) , menos o ultimo, da linha "i+1" */
    for (j = 1; j < rede->larg; j+=2)
    { /* construir os arcos */
      rede->ant[++k] = i*rede->larg + j; rede->suc[k] = (i+1)*rede->larg + j +1;
    }
  }
  /* para todas as linhas pares menos para a ultima */
  for (i = 1; i < rede->altu - 1; i+=2)
  { /* para todos os no's (de dois em dois) , menos o ultimo, da linha "i+1" */
    for (j = 3; j <= rede->larg; j+=2)
    { /* construir os arcos */
      rede->ant[++k] = i*rede->larg + j; rede->suc[k] = (i+1)*rede->larg + j -1;
    }
  }

  return;
} /* grelhaAcic_d5 */

void grelhaAcic_d6(rede)
  Rede *rede;
{ register int i, j, k;

  k = 0;
  /* para todas as linhas menos para a ultima */
  for (i = 0; i < rede->altu - 1; i++)
  { /* para todos os no's, menos o ultimo, da linha "i+1" */
    for (j = 0; ++j < rede->larg; )
    { /* construir os arcos */
      rede->ant[++k] = i*rede->larg + j; rede->suc[k] = i*rede->larg + j + 1;
      rede->ant[++k] = i*rede->larg + j; rede->suc[k] = (i+1)*rede->larg + j;
      rede->ant[++k] = i*rede->larg + j; rede->suc[k] = (i+1)*rede->larg + j +1;
    }
    rede->ant[++k] = i*rede->larg + j; rede->suc[k] = (i+1)*rede->larg + j;
  }
  /* para todos os no's, menos o ultimo, da linha "i+1" */
  for (j = i*rede->larg; ++j < rede->n; )
  { /* construir os arcos */
    rede->ant[++k] = j; rede->suc[k] = j + 1;
  }

  return;
} /* grelhaAcic_d6 */

void grelhaAcic_d7(rede)
  Rede *rede;
{ register int i, j, k;

  k = 0;
  /* para todas as linhas menos para a ultima */
  /* NOTA: Aqui so' vai ser criado um tipo de arco "diagonal" */
  for (i = 0; i < rede->altu - 1; i++)
  { /* para todos os no's, menos o ultimo, da linha "i+1" */
    for (j = 0; ++j < rede->larg; )
    { /* construir os arcos */
      rede->ant[++k] = i*rede->larg + j; rede->suc[k] = i*rede->larg + j + 1;
      rede->ant[++k] = i*rede->larg + j; rede->suc[k] = (i+1)*rede->larg + j;
      rede->ant[++k] = i*rede->larg + j; rede->suc[k] = (i+1)*rede->larg + j +1;
    }
    rede->ant[++k] = i*rede->larg + j; rede->suc[k] = (i+1)*rede->larg + j;
  }
  /* para todos os no's, menos o ultimo, da linha "i+1" */
  for (j = i*rede->larg; ++j < rede->n; )
  { /* construir os arcos */
    rede->ant[++k] = j; rede->suc[k] = j + 1;
  }

  /* Cria os restantes arcos "diagonais" */
  /* para todas as linhas, duas a duas, menos para a primeira */
  for (i = 1; i < rede->altu; i+=2)
  { /* para todos os no's, menos o ultimo, da linha "i" */
    for (j = 0; ++j < rede->larg; )
    { /* construir os arcos */
      rede->ant[++k] = i*rede->larg + j; rede->suc[k] = (i-1)*rede->larg + j +1;
    }
  }

  return;
} /* grelhaAcic_d7 */

void grelhaAcic_d8(rede)
  Rede *rede;
{ register int i, j, k;

  k = 0;
  /* para todas as linhas menos para a ultima */
  /* NOTA: Aqui so' vai ser criado um tipo de arco "diagonal" */
  for (i = 0; i < rede->altu - 1; i++)
  { /* para todos os no's, menos o ultimo, da linha "i+1" */
    for (j = 0; ++j < rede->larg; )
    { /* construir os arcos */
      rede->ant[++k] = i*rede->larg + j; rede->suc[k] = i*rede->larg + j + 1;
      rede->ant[++k] = i*rede->larg + j; rede->suc[k] = (i+1)*rede->larg + j;
      rede->ant[++k] = i*rede->larg + j; rede->suc[k] = (i+1)*rede->larg + j +1;
    }
    rede->ant[++k] = i*rede->larg + j; rede->suc[k] = (i+1)*rede->larg + j;
  }
  /* para todos os no's, menos o ultimo, da linha "i+1" */
  for (j = i*rede->larg; ++j < rede->n; )
  { /* construir os arcos */
    rede->ant[++k] = j; rede->suc[k] = j + 1;
  }

  /* Cria os restantes arcos "diagonais" */
  /* para todas as linhas menos para a primeira */
  for (i = 0; ++i < rede->altu; )
  { /* para todos os no's, menos o ultimo, da linha "i" */
    for (j = 0; ++j < rede->larg; )
    { /* construir os arcos */
      rede->ant[++k] = i*rede->larg + j; rede->suc[k] = (i-1)*rede->larg + j +1;
    }
  }

  return;
} /* grelhaAcic_d8 */

void grelhaCicloOrient(rede)
  Rede *rede;
{ register int i, j, k;


  k = j = rede->m / 2;
  for (i = 0; i++ < j; ) 
  { rede->ant[++k] = rede->suc[i]; rede->suc[k] = rede->ant[i];
  }

  return;
} /* grelhaCicloOrient */

void complAcicloOrient(rede)
  Rede *rede;
{ register int i, j, k;

  k= 0;
  for (i = 0; i++ < rede->n; )
  { for (j = i; j++ < rede->n; )
    { rede->ant[++k] = i;
      rede->suc[k] = j;
    }
  }

  return;
} /* complAcicloOrient */

void complCicloOrient(rede)
  Rede *rede;
{ register int i, j, k;

  k= 0;
  for (i = 0; i++ < rede->n; )
  { for (j = 0; ++j < i; )
    { rede->ant[++k] = i;
      rede->suc[k] = j;
    }
    for ( ; j++ < rede->n; )
    { rede->ant[++k] = i;
      rede->suc[k] = j;
    }
  }

  return;
} /* complCicloOrient */

void redeAleat (f, conj, rede)
  FILE *f;
  int *conj;
  Rede *rede;
{ int limite, pos;
  register int i;

  criaElem(rede->nos, rede->n);
  misturaElem(rede->nos, rede->n);

  /* copiar os no's baralhados para "conj" */
  for (i = 0; i++ < rede->n; )
    conj[i] = rede->nos[i];
  limite = rede->n;
  if ( rede->ciclo )
  { if (rede->numS > 0)
      escolheNos(f, "s", conj, rede->nos, rede->numS, &limite);

    /* NOTA: nao se admite que um no' possa ser inicial e terminal */
    /* caso contrario, fazer aqui:
     *
     * "limite = n;" */
    if (rede->numT > 0)
      escolheNos(f, "t", conj, rede->nos, rede->numT, &limite);
  }
  else
  { if (rede->numS > 0)
    { fprintf(f, "s\t");
      for (i = 0; i++ < rede->numS; )
        fprintf(f, "%d ", rede->nos[i]);
      fprintf(f, "\nc\n");
    }
    if (rede->numT > 0)
    { fprintf(f, "t\t");
      for (i = 0; i++ < rede->numT; )
        fprintf(f, "%d ", rede->nos[rede->n-i+1]);
      fprintf(f, "\nc\n");
    }
    fflush(f);
  }

  if ( rede->ciclo && rede->orient )
    redeCicloOrient(conj, rede);
  else
    redeAcicloOrient(conj, rede);

  fflush(f);
} /* redeAleat */

void redeCompl (f, rede)
  FILE *f;
  Rede *rede;
{ int limite, pos;
  register int i;

  criaElem(rede->nos, rede->n);
  misturaElem(rede->nos, rede->n);

  limite = rede->n;
  if ( rede->ciclo )
  { if (rede->numS > 0)
      escolheNos(f, "s", rede->nos, rede->nos, rede->numS, &limite);

    /* NOTA: nao se admite que um no' possa ser inicial e terminal */
    /* caso contrario, fazer aqui:
     *
     * "limite = n;" */
    if (rede->numT > 0)
      escolheNos(f, "t", rede->nos, rede->nos, rede->numT, &limite);
  }
  else
  { if (rede->numS > 0)
    { fprintf(f, "s\t");
      for (i = 0; i++ < rede->numS; )
        fprintf(f, "%d ", rede->nos[i]);
      fprintf(f, "\nc\n");
    }
    if (rede->numT > 0)
    { fprintf(f, "t\t");
      for (i = 0; i++ < rede->numT; )
        fprintf(f, "%d ", rede->nos[rede->n-i+1]);
      fprintf(f, "\nc\n");
    }
    fflush(f);
  }

  if ( rede->ciclo && rede->orient )
    complCicloOrient(rede);
  else
    complAcicloOrient(rede);

  fflush(f);
} /* redeCompl */

void redeGrelha (f, conj, rede)
  FILE *f;
  int *conj;
  Rede *rede;
{ int limite, pos;
  register int i, j, k;

  fprintf(f, "c\t%dx%d\nc\n", rede->larg, rede->altu);

  criaElem(rede->nos, rede->n);

  /* Os nos iniciais serao: 1, 2, ... , numS */
  if (rede->numS > 0)
  { fprintf(f, "s\t%d", 1);
    for (i = 1; i++ < rede->numS; )
      fprintf(f, " %d", i);
    fprintf(f, "\nc\n");
  }

  /* Os nos terminais serao: n, n - 1, ... , n - numT + 1 */
  if (rede->numT > 0)
  { fprintf(f, "t\t%d", rede->n);
    for (i = 1; i < rede->numT; i++)
      fprintf(f, " %d", rede->n - i);
    fprintf(f, "\nc\n");
  }

  switch( rede->d )
  { case 3 : grelhaAcic_d3(rede);
	       break;
    case 4 : grelhaAcic_d4(rede);
	       break;
    case 5 : grelhaAcic_d5(rede);
	       break;
    case 6 : grelhaAcic_d6(rede);
	       break;
    case 7 : grelhaAcic_d7(rede);
	       break;
    case 8 : grelhaAcic_d8(rede);
	       break;
    default: printf("Wrong option for network density (d = %d).\n", rede->d);
	       break;
  } /* switch( rede->d ) */
  if ( rede->ciclo && rede->orient )
    grelhaCicloOrient(rede);

  fflush(f);
} /* redeGrelha */

void redePontos (f, conj, rede)
  FILE *f;
  int *conj;
  Rede *rede;
{ int limite, pos;
  register int i;

  fprintf(f, "c\t%dx%d\n", rede->larg, rede->altu);

  criaPontos(rede->pontos, rede->n, rede->larg, rede->altu);
  criaElem(rede->nos, rede->n);
  misturaElem(rede->nos, rede->n);
  escrevePontos(f, rede->nos, rede->pontos, rede->n, rede->larg);

  criaElem(conj, rede->n);
  misturaElem(conj, rede->n);
  limite = rede->n;
  if ( rede->ciclo )
  { if (rede->numS > 0)
    escolheNos(f, "s", conj, rede->nos, rede->numS, &limite);

  /* NOTA: nao se admite que um no' possa ser inicial e terminal */
  /* caso contrario, fazer aqui:
   *
   * "limite = n;" */
  if (rede->numT > 0)
    escolheNos(f, "t", conj, rede->nos, rede->numT, &limite);
  }
  else
  { if (rede->numS > 0)
    { fprintf(f, "s\t");
      for (i = 0; i++ < rede->numS; )
        fprintf(f, "%d ", rede->nos[i]);
      fprintf(f, "\nc\n");
    }
    if (rede->numT > 0)
    { fprintf(f, "t\t");
      for (i = 0; i++ < rede->numT; )
        fprintf(f, "%d ", rede->nos[rede->n-i+1]);
      fprintf(f, "\nc\n");
    }
    fflush(f);
  }

  if ( rede->ciclo && rede->orient )
    redeCicloOrient(conj, rede);
  else
    redeAcicloOrient(conj, rede);

  fflush(f);
  return;
} /* redePontos */

int main()
{ Rede rede;
  int *ordemArcos,/*coresponde aos arcos da rede. Tem os elementos baralhados */
	      /* para nao "viciar" a escrita da rede */
    *conj, /* vector que ira' ter os no's baralhados e permitira' escolher */
	   /* um no' aleatoriamente, pelo que posso misturar os seus elementos*/
	   /* em qualquer altura */
    pos,   /* posicao do ultimo elemento escolhido no conjunto */
 numSubInt, /* Numero de subintervalos um que vai ser dividido o 1o objectivo */
		/* tentando assim aumentar o numero de trajectos nao dominados*/
		/* ( so' e' utilizado quando r = 2) */
    vectSub[NmAXsUBiNT + 1], /* vector que permite realizar a subdivisao do */
		 /* intervalo da distancia */
    limite; /* limite do vector "conj" onde se encontra os elementos que */
            /* posso escolher. Os no's para ale'm de "limite" ja' foram */
	    /* escolhidos */
  register int i, k, aux;
  FILE *f;


  ddados = fopen("_ddados", "w");
  lerTipo(&rede);
  lerDados(&rede, &ordemArcos, &conj, &numSubInt);
  fflush(ddados);
  fclose(ddados);

  inicia();

  f = fopen("rede.dat", "w");
  fprintf(f, "c\tseed = %d\nc\n", num1);

  fprintf(f, "c\t");
  switch( rede.tipo )
  { case '1' : fprintf(f, "Random ");
	       break;
    case '2' : fprintf(f, "Grid ");
	       break;
    case '3' : fprintf(f, "Euclidean ");
	       break;
    case '4' : fprintf(f, "Complete ");
	       break;
    default  : break;
  } /* switch */

  if (! rede.ciclo)
    fprintf(f, "acyclic ");
  else
  { if (! rede.orient)
      fprintf(f, "undirected ");
    else
    fprintf(f, "directed ");
  }
  fprintf(f, "network\n");
  fprintf(f, "c\n");

  fprintf(f, "T\t");
  switch( rede.tipo )
  { case '1' : fprintf(f, "r ");
	       break;
    case '2' : fprintf(f, "g ");
	       break;
    case '3' : fprintf(f, "e ");
	       break;
    case '4' : fprintf(f, "c ");
	       break;
    default  : break;
  } /* switch */

  if (rede.ciclo)
  { if (rede.orient)
      fprintf(f, "d\n");
    else
      fprintf(f, "u\n");
  }
  else
    fprintf(f, "a\n");

  if (rede.tipo == '2')
    fprintf(f, "c\nc\td = %d\n", rede.d);
  fprintf(f, "c\nN\t%d\n", rede.n); fprintf(f, "c\nA\t%d\n", rede.m);
  fprintf(f, "c\nk\t%d\n", rede.r); fprintf(f, "c\n");

  switch( rede.tipo )
  { case '1' : redeAleat (f, conj, &rede);
	       break;
    case '2' : redeGrelha (f, conj, &rede);
	       break;
    case '3' : redePontos(f, conj, &rede);
	       break;
    case '4' : redeCompl(f, &rede);
	       break;
    default  : break;
  } /* switch */

  if (rede.tipo == '3')
  { /* O primeiro objectivo (dist[2]) corresponde as distancias euclidianas
     * entre os pontos */
    geraDistEuclid(rede.dist[2], rede.ant, rede.suc, rede.nos, rede.pontos, rede.m,rede.larg);
  }
  else
    geraNumeros(rede.dist[2], rede.m, rede.valor[0][1], rede.valor[1][1]);


  if ( (rede.r == 2) && (numSubInt > 1))
  { aux = rede.valor[1][1] - rede.valor[0][1];
    vectSub[0] = rede.valor[0][1];
    for (i = 0; i++ < numSubInt; )
      /* NOTA: convem deixar estar forma, pois definindo um "h", todos os
       * subintervalos iriam ficar iguais, com exepcao do ultimo que ficaria
       * com o resto e, portanto, poderia ficar muito maior */
      vectSub[i] = vectSub[0] + (aux*i)/numSubInt;
    for (k = 0; k++ < rede.m; )
    { aux = rede.dist[2][k];
      for (i = 1; i < numSubInt; i++)
        if (aux <= vectSub[i])
	  break;
      /* aux pertence ao i-esimo intervalo => gerar o valor do 2o objectivo no
       * (numSubInt - i +1)-esimo intervalo */
      rede.dist[3][k] = leat(vectSub[numSubInt-i], vectSub[numSubInt-i+1]);
    }
  }
  else
    for (i = 1; i++ < rede.r; )
      geraNumeros(rede.dist[i+1], rede.m, rede.valor[0][i], rede.valor[1][i]);

  criaElem(ordemArcos, rede.m); misturaElem(ordemArcos, rede.m);
  escreveArcos(f, rede.dist, rede.nos, ordemArcos, rede.r, rede.m);

  fflush(f);
  close(f);
  return 0;
} /* main */