/* Fabiano: 06/05/2010 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define TRUE 1
#define FALSE 0
#define MAXNUMVERTICES 100000 /*--No. maximo de vertices--*/
#define MAXNUMARESTAS 100000 /*--No. maximo de arestas--*/
#define MAXR 5
#define MAXTAMPROX MAXR*MAXNUMARESTAS
#define MAXTAM 1000 /*--Usado Fila--*/
#define MAXTAMCHAVE 6 /*--No. maximo de caracteres da chave--*/
#define MAXNUMCHAVES 100000 /*--No. maximo de chaves lidas--*/
#define INDEFINIDO -1
/*-- Tipos usados em GrafoListaInc do Programa 7.25 --*/
typedef int TipoValorVertice;
typedef int TipoValorAresta;
typedef int Tipor;
typedef int TipoMaxTamProx;
typedef int TipoPesoAresta;
typedef TipoValorVertice TipoArranjoVertices[MAXR];
typedef struct TipoAresta {
  TipoArranjoVertices Vertices;
  TipoPesoAresta Peso;
} TipoAresta;
typedef TipoAresta TipoArranjoArestas[MAXNUMARESTAS];
typedef struct TipoGrafo {
  TipoArranjoArestas Arestas;
  TipoValorVertice Prim[MAXNUMVERTICES];
  TipoMaxTamProx Prox[MAXTAMPROX];
  TipoMaxTamProx ProxDisponivel;
  TipoValorVertice NumVertices;
  TipoValorAresta NumArestas;
  Tipor r;
} TipoGrafo;
/*-- Tipos usados em Fila do Programa 3.17 --*/
typedef int TipoApontador;
typedef struct {
  TipoValorVertice Chave;
  /* outros componentes */
} TipoItem;
typedef struct {
  TipoItem Item[MAXTAM + 1];
  TipoApontador Frente, Tras;
} TipoFila;
typedef int TipoPesos[MAXTAMCHAVE];
typedef TipoPesos TipoTodosPesos[MAXR];
typedef int Tipog[MAXNUMVERTICES];
typedef char TipoChave[MAXTAMCHAVE];
typedef TipoChave TipoConjChaves[MAXNUMCHAVES];
typedef TipoValorVertice TipoIndice;
static TipoValorVertice M;
static TipoValorAresta N;
/*-- Entram aqui os operadores do Programa 3.18 --*/
void FFVazia(TipoFila *Fila)
{ Fila->Frente = 1; Fila->Tras = Fila->Frente; } /* FFVazia */

/* Nivio: aqui deveria ser TipoFila * ao inves de TipoFila.
 *        estou mantendo, mas fica estranho ja que fila eh
 *        um tipo abstrato.  */
int Vazia(TipoFila Fila)
{ return (Fila.Frente == Fila.Tras); } /* Vazia */

void Enfileira(TipoItem x, TipoFila *Fila)
{ if (Fila->Tras % MAXTAM + 1 == Fila->Frente)
  printf(" Erro: fila esta cheia\n");
  else 
  { Fila->Item[Fila->Tras - 1] = x;
    Fila->Tras = Fila->Tras % MAXTAM + 1;
  }
}  /* Enfileira */

void Desenfileira(TipoFila *Fila, TipoItem *Item)
{ if (Vazia(*Fila))
  printf(" Erro: fila esta vazia\n");
  else 
  { *Item = Fila->Item[Fila->Frente - 1];
    Fila->Frente = Fila->Frente % MAXTAM + 1;
  }
}  /* Desenfileira */

/*-- Entram aqui os operadores do Programa 7.26 --*/
/* Nivio: nao faz sentido NumArestas ser um apontador. Estou transformando em uma variavel.
          Sugiro fazer o mesmo para o o programa C correspondente ao programa 7.26 para tornar
          o codigo mais claro.
*/
short ArestasIguais(TipoArranjoVertices V1, TipoValorAresta NumAresta, TipoGrafo *Grafo)
{ Tipor i, j; short Aux = TRUE; i = 0;
  while (i < Grafo->r && Aux)
    { j = 0;
      while ((V1[i] != Grafo->Arestas[NumAresta].Vertices[j]) 
        && (j < Grafo->r)) j++; 
      if (j == Grafo->r) Aux = FALSE; 
      i++;
    }
  return Aux;
}

void FGVazio(TipoGrafo *Grafo)
{ int i; Grafo->ProxDisponivel = 0;
  for (i = 0; i < Grafo->NumVertices; i++) Grafo->Prim[i] = INDEFINIDO;
}

void InsereAresta(TipoAresta *Aresta, TipoGrafo *Grafo)
{ int i, Ind;
  if (Grafo->ProxDisponivel == MAXTAMPROX) 
  printf ("Nao ha espaco disponivel para a aresta\n");
  else 
  { Grafo->Arestas[Grafo->ProxDisponivel] = *Aresta;
    for (i = 0; i < Grafo->r; i++)
      { Ind = Grafo->ProxDisponivel + i * Grafo->NumArestas;
        Grafo->Prox[Ind] = Grafo->Prim[Grafo->Arestas[Grafo->ProxDisponivel].Vertices[i]];
        Grafo->Prim[Grafo->Arestas[Grafo->ProxDisponivel].Vertices[i]] = Ind;
      }
  }
  Grafo->ProxDisponivel++;
}

short ExisteAresta(TipoAresta *Aresta, TipoGrafo *Grafo)
{ Tipor v; TipoValorAresta A1;
  int Aux; short EncontrouAresta;
  EncontrouAresta = FALSE;
  for(v = 0; v < Grafo->r; v++)
    { Aux = Grafo->Prim[Aresta->Vertices[v]];
      while (Aux != INDEFINIDO && !EncontrouAresta)
        { A1 = Aux % Grafo->NumArestas;
          if (ArestasIguais(Aresta->Vertices, A1, Grafo)) EncontrouAresta = TRUE;
          Aux = Grafo->Prox[Aux];
        }
    }
  return EncontrouAresta;
}

TipoAresta RetiraAresta(TipoAresta *Aresta, TipoGrafo *Grafo)
{ int Aux, Prev, i;
  TipoValorAresta A1; Tipor v;
  for (v = 0; v < Grafo->r; v++)
    { Prev = INDEFINIDO;
      Aux = Grafo->Prim[Aresta->Vertices[v]];
      A1 = Aux % Grafo->NumArestas;
      while (Aux >= 0 && !ArestasIguais(Aresta->Vertices, A1, Grafo))
        { Prev = Aux; Aux = Grafo->Prox[Aux];
          A1 = Aux % Grafo->NumArestas;
        }
      if (Aux >= 0)
      { if (Prev == INDEFINIDO)
        Grafo->Prim[Aresta->Vertices[v]] = Grafo->Prox[Aux];
        else Grafo->Prox[Prev] = Grafo->Prox[Aux];
      }
    }
    TipoAresta Resultado = Grafo->Arestas[A1];
    for (i = 0; i < Grafo->r; i++) Grafo->Arestas[A1].Vertices[i] = INDEFINIDO;
    Grafo->Arestas[A1].Peso = INDEFINIDO;
    return Resultado;
}

void ImprimeGrafo(TipoGrafo *Grafo)
{ int i, j;
  printf(" Arestas: Num Aresta, Vertices, Peso \n");
  for (i = 0; i < Grafo->NumArestas; i++)
    { printf ("%2d", i);
      for (j = 0; j < Grafo->r; j++) printf ("%3d", Grafo->Arestas[i].Vertices[j]);
      printf ("%3d\n", Grafo->Arestas[i].Peso);
    }
  printf ("Lista arestas incidentes a cada vertice:\n");
  for (i = 0 ; i < Grafo->NumVertices; i++)
    { printf ("%2d", i);  
      j = Grafo->Prim[i];
      while (j != INDEFINIDO)
        { printf ("%3d", j % Grafo->NumArestas);  
          j = Grafo->Prox[j];
        }
      printf("\n");
    }
}

short VerticeGrauUm (TipoValorVertice V, TipoGrafo* Grafo)
{ return ((Grafo->Prim[V] >= 0) && 
          (Grafo->Prox[Grafo->Prim[V]] == INDEFINIDO)); 
}

void GrafoAciclico (TipoGrafo* Grafo,
                    TipoArranjoArestas L,
                    short* GAciclico)
{ TipoValorVertice j; TipoValorAresta A1;  
  TipoItem x; TipoFila Fila; 
  TipoValorAresta NArestas; TipoAresta Aresta;
  NArestas = Grafo->NumArestas; 
  FFVazia (&Fila);  j = 0;
  while (j < Grafo->NumVertices) 
    { if (VerticeGrauUm (j, Grafo)) 
      { x.Chave = j;  Enfileira (x, &Fila); }
      j = j + 1;
    }
  while (!Vazia (Fila) && (NArestas > 0)) 
    { Desenfileira (&Fila, &x);
      if (Grafo->Prim[x.Chave] >= 0) 
      { A1 = Grafo->Prim[x.Chave] % Grafo->NumArestas;
        Aresta = RetiraAresta (&Grafo->Arestas[A1], Grafo);
        L[Grafo->NumArestas - NArestas] = Aresta;
        NArestas = NArestas - 1;
        if (NArestas > 0) 
        { for (j = 0; j < Grafo->r; j++) 
            { if (VerticeGrauUm (Aresta.Vertices[j], Grafo)) 
              { x.Chave = Aresta.Vertices[j]; 
                Enfileira (x, &Fila); 
              }
            }
        }
      }
    }  
  *GAciclico = (NArestas == 0);
} /* GrafoAciclico */

/*--Operadores para obter a lista de arestas incidentes a um vertice--*/
/* Nivio: novamente um apontador esta sendo usado desnecessariamente para Vertice */
short ListaIncVazia(TipoValorVertice *Vertice, TipoGrafo *Grafo)
{ return Grafo->Prim[*Vertice] == INDEFINIDO; }

/* Nivio: novamente um apontador esta sendo usado desnecessariamente para Vertice */
TipoApontador PrimeiroListaInc(TipoValorVertice *Vertice, TipoGrafo *Grafo)
{ return Grafo->Prim[*Vertice]; }

/* Nivio: novamente um apontador esta sendo usado desnecessariamente para Vertice e ele nao 
          eh nem usado na funcao. Isso eh para manter compatibilidade? 
*/
void ProxArestaInc(TipoValorVertice *Vertice, TipoGrafo *Grafo, 
  TipoValorAresta *Inc, TipoPesoAresta *Peso, TipoApontador *Prox, short *FimListaInc)
{
  *Inc = *Prox % Grafo->NumArestas; *Peso = Grafo->Arestas[*Inc].Peso;
  if (Grafo->Prox[*Prox] == INDEFINIDO) *FimListaInc = TRUE;
  else *Prox = Grafo->Prox[*Prox];
}
/*---- Fim dos operadores do Programa 7.? ----*/
/*--Funcao hash universal apresentada no Programa 4.22--*/
TipoIndice h(TipoChave Chave, TipoPesos p)
{ int i; unsigned int Soma = 0; int comp = strlen(Chave);
  for (i = 0; i < comp; i++)
    Soma += (unsigned int)Chave[i] * p[i];
  return (Soma % M);
}

/*--Gera pesos para funcao h apresentado no Programa 6.X --*/
void GeraPesos(TipoPesos p)
{ int i; struct timeval semente;
  gettimeofday(&semente,NULL); 
  srand((int)(semente.tv_usec + 1000000 * semente.tv_sec)); /* Nivio: tinha um erro aqui. Compare com o original */
  for (i = 0; i < MAXTAMCHAVE; i++)
    p[i] =  rand(); /* nivio: funcao nao funciona bem em em c e por isso tive que altera-la para funcionar com os exemplos. */
} 

void Atribuig (TipoGrafo *Grafo,
               TipoArranjoArestas L,
               Tipog g)
{ int i, u, Soma;
  TipoValorVertice v;  TipoAresta a;
  for (i = Grafo->NumVertices - 1; i >= 0; i--) g[i] = INDEFINIDO;
  for (i = Grafo->NumArestas - 1; i >= 0; i--) 
    { a = L[i];  Soma = 0;
      for (v = Grafo->r - 1; v >= 0; v--) 
        { if (g[a.Vertices[v]] == INDEFINIDO) 
          { u = a.Vertices[v]; g[u] = Grafo->NumArestas; } 
          else Soma += g[a.Vertices[v]];
        }
        g[u] = a.Peso - Soma;
        if (g[u] < 0) g[u] = g[u]+(Grafo->r-1)*Grafo->NumArestas;
    } 
}

void GeraGrafo (TipoConjChaves   ConjChaves,
                TipoValorAresta  N,
                TipoValorVertice M,
                Tipor            r,
                TipoTodosPesos   Pesos,
                int              *NGrafosGerados,
                TipoGrafo        *Grafo) 
{ /* Gera um grafo sem arestas repetidas e sem self-loops */
  int i, j;  TipoAresta Aresta;  int GrafoValido;

  inline int VerticesIguais (TipoAresta *Aresta) 
  { int i, j;
    for (i = 0; i < Grafo->r - 1; i++) 
    { for (j = i + 1; j < Grafo->r; j++) 
      { if (Aresta->Vertices[i] == Aresta->Vertices[j]) 
        return TRUE; 
      }
    }
    return FALSE;
  }

  do 
  { GrafoValido = TRUE; Grafo->NumVertices = M;
    Grafo->NumArestas = N; Grafo->r = r;
    FGVazio (Grafo); *NGrafosGerados = 0;
    for (j = 0; j < Grafo->r; j++) GeraPesos (Pesos[j]); 
    for (i = 0; i < Grafo->NumArestas; i++) 
      { Aresta.Peso = i;
        for (j = 0; j < Grafo->r; j++) 
          Aresta.Vertices[j] = h (ConjChaves[i], Pesos[j]); 
        if (VerticesIguais (&Aresta) || ExisteAresta (&Aresta, Grafo)) 
        { GrafoValido = FALSE;  break;  }
        else InsereAresta (&Aresta, Grafo);
      }
    ++(*NGrafosGerados);
  } while(!GrafoValido);
} /* Fim GeraGrafo */

static void Ignore(FILE *Arq, char Delim) 
{ int c = fgetc(Arq);
  while(c != Delim && c != EOF) c = fgetc(Arq);
}

int main(){
    Tipor r;
    TipoGrafo Grafo;
    TipoArranjoArestas L;
    short GAciclico;
    Tipog g;
    TipoTodosPesos Pesos;
    int i, j;
    int NGrafosGerados;
    TipoConjChaves ConjChaves;  
    FILE *ArqEntrada;
    FILE *ArqSaida;
    char NomeArq[100];

    printf ("Nome do arquivo com chaves a serem lidas: ");
    scanf("%s*[^\n]", NomeArq);
    printf("NomeArq = %s\n", NomeArq);
    ArqEntrada = fopen(NomeArq, "r");

    printf ("Nome do arquivo para gravar experimento: ");
    scanf("%s*[^\n]", NomeArq);
    printf("NomeArq = %s\n", NomeArq);
    ArqSaida = fopen(NomeArq, "w");

    NGrafosGerados = 0;  
    i = 0;
    fscanf(ArqEntrada, "%d %d %d*[^\n]", &N, &M, &r); 
    Ignore(ArqEntrada, '\n'); 
    printf("N=%d, M=%d, r=%d\n", N, M, r);
    while ((i < N) && (!feof(ArqEntrada))) 
    { fscanf(ArqEntrada,"%s*[^\n]", ConjChaves[i]); Ignore(ArqEntrada, '\n');
      printf("Chave[%d]=%s\n", i, ConjChaves[i]);
      i++;  
    }
    if (i !=  N) 
    { printf("Erro: entrada com menos do que ', N, ' elementos.\n");
      exit(-1);
    }
    do 
      { GeraGrafo (ConjChaves, N, M, r, Pesos, &NGrafosGerados, &Grafo); 
        ImprimeGrafo (&Grafo);
        /*--Imprime estrutura de dados--*/
        printf ("prim: "); 
        for (i = 0; i < Grafo.NumVertices; i++)  
            printf("%3d ", Grafo.Prim[i]); 
        printf("\n");
        printf ("prox: "); 
        for (i = 0; i < Grafo.NumArestas * Grafo.r; i++)  
            printf("%3d ", Grafo.Prox[i]); 
        printf("\n");
        GrafoAciclico (&Grafo, L, &GAciclico);
      } while (!GAciclico);
    printf ("Grafo aciclico com arestas retiradas:");
    for(i = 0; i < Grafo.NumArestas; i++) printf("%3d ", L[i].Peso);
    printf("\n");
    Atribuig (&Grafo, L, g); 
    fprintf(ArqSaida, "%d  (N)\n", N);
    fprintf(ArqSaida, "%d  (M)\n", M);
    fprintf(ArqSaida, "%d  (r)\n", r);
    for (j = 0; j < Grafo.r; j++) 
    { for (i = 0; i < MAXTAMCHAVE; i++) fprintf(ArqSaida, "%d ", Pesos[j][i]); 
      for (i = 0; i < MAXTAMCHAVE; i++) printf("%d ", Pesos[j][i]); 
      fprintf(ArqSaida, "  (p%d)\n", j); 
      printf("  (p%d)\n", j);
    } 
    for (i = 0; i < M; i++) fprintf(ArqSaida, "%d ", g[i]); 
    for (i = 0; i < M; i++) printf("%d ", g[i]); 
    fprintf(ArqSaida, "  (g)\n");  
    printf("  (g)\n");  
    fprintf(ArqSaida, "No. grafos gerados por GeraGrafo:%d\n", NGrafosGerados);
    printf("No. grafos gerados por GeraGrafo:%d\n", NGrafosGerados);
    fclose (ArqSaida);
    fclose (ArqEntrada);
    return 0;
}