/* fabiano: 18/mai/2010 */
/* Verifica se grafo e' aciclico, Atribuig usando 2 bits por entrada de g e gera a funcao hpm */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define TRUE 1
#define FALSE 0
#define MAXK 256 /*-- No. maximo de vertices --*/
#define MAXNUMVERTICES 100000 /*--No. maximo de vertices--*/
const static int MAXTAMG = (MAXNUMVERTICES + 3)/4; /* Cada byte armazena 4 vertices */
const static int MAXTAMTABRANK = (MAXNUMVERTICES + MAXK - 1)/MAXK; /* Teto de MAXNUMVERTICES/MAXK */
#define MAXTRVALUE 255
#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
#define NAOATRIBUIDO    3

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 unsigned char Tipog;
typedef unsigned char TipoTr[MAXTRVALUE + 1];
typedef int TipoTabRank;
typedef unsigned short TipoK;
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 est  a  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 est  a  vazia\n");
  else 
  { *Item = Fila->Item[Fila->Frente - 1];
    Fila->Frente = Fila->Frente % MAXTAM + 1;
  }
}  /* Desenfileira */

/*-- Entram aqui os operadores do Programa 7.26 --*/
short ArestasIguais(TipoArranjoVertices V1, TipoValorAresta NumAresta, TipoGrafo *Grafo)
{ Tipor i = 0, j; short Aux = TRUE;
  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. */
} 

/* Assume que todas as entradas de 2 bits do vetor */
/* g foram inicializadas com o valor 3             */
void AtribuiValor2Bits (Tipog *g, 
                        int Indice,
                        unsigned char Valor)
{ int i, Pos;
  i   = Indice / 4;
  Pos = (Indice % 4);
  Pos = Pos * 2;          /* Cada valor ocupa 2 bits */
  g[i] &=  ~(3U << Pos);   /* zera os dois bits a atribuir */
  g[i] |= (Valor << Pos); /* realiza a atribuicao */ 
} /* AtribuiValor2Bits */

char ObtemValor2Bits (Tipog *g, int Indice)
{ int i, Pos;
  i = Indice / 4;
  Pos = (Indice % 4);
  Pos = Pos * 2; /* Cada valor ocupa 2 bits */
  return (g[i] >> Pos) & 3U;  
} /* ObtemValor2Bits */

void Atribuig (TipoGrafo *Grafo,
               TipoArranjoArestas L,
               Tipog *g)
{ int i, j, u, Soma; TipoValorVertice v; TipoAresta a;
  unsigned int valorg2bits; unsigned char Visitado[MAXNUMVERTICES];
  if (Grafo->r <= 3) 
  { /* valores de 2 bits requerem r <= 3 */
    for (i = Grafo->NumVertices - 1; i >= 0; i--)  
    { AtribuiValor2Bits(g, i, Grafo->r);
      Visitado[i] = FALSE;
    }
    for (i = Grafo->NumArestas - 1; i >= 0; i--) 
    { a = L[i];  Soma = 0;
      for (v = Grafo->r - 1; v >= 0; v--) 
      { if (!Visitado[a.Vertices[v]]) 
        { Visitado[a.Vertices[v]] = TRUE;
          u = a.Vertices[v];
          j = v;
        } 
        else Soma += ObtemValor2Bits(g, a.Vertices[v]);
      }
      valorg2bits = (j - Soma) % Grafo->r;
      while (valorg2bits > Grafo->r) valorg2bits += Grafo->r;
      AtribuiValor2Bits (g, u, valorg2bits);
    }
  }
} /*--Fim Atribuig--*/

void GeraTr (TipoTr Tr) 
{ int i, j, v, Soma = 0;
  for (i = 0; i <= MAXTRVALUE; i++) 
  { Soma = 0;  v = i;
    for (j = 1; j <= 4; j++) 
      { if ((v & 3) != NAOATRIBUIDO) Soma = Soma + 1;
        v = v >> 2; 
      }
    Tr[i] = Soma;
  }
} /* GeraTr */

void ImprimeTr (TipoTr Tr) 
{ int i;
    printf ("Tr = {");
    for (i = 0; i <= MAXTRVALUE; i++) 
      { if (i % 16 == 0) printf("\n");
        printf("%d ", Tr[i]);
      }
    printf("\n}\n");
} /* ImprimeTr */

void GeraTabRank (Tipog *g, TipoValorVertice Tamg,
                  TipoK k,  TipoTabRank *TabRank)
{ int i, Soma = 0;
  for (i = 0; i < Tamg; i++) 
    { if (i % k == 0) TabRank[i / k] = Soma;
      if (ObtemValor2Bits(g, i) != NAOATRIBUIDO) Soma = Soma + 1; 
    }
} /* GeraTabRank */

void ImprimeTabRank (TipoTabRank *TabRank, int TamTabRank)
{ int i;
  printf ("TabRank = {");
  for (i = 0; i < TamTabRank; i++) 
    { if (i % 16 == 0) printf("\n");
      printf("%d ", TabRank[i]);
    }
  printf("\n}\n");
} /* ImprimeTabRank */

void GeraGrafo (TipoConjChaves  ConjChaves, TipoValorAresta N,
                TipoValorVertice M, Tipor r, TipoTodosPesos Pesos,
                int *NGrafosGerados, TipoGrafo *Grafo) 
{ /*--GeraGrafo--*/
  /* 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[MAXTAMG]; TipoTr Tr;
  TipoTabRank TabRank[MAXTAMTABRANK]; int TamTabRank;
  TipoK k; 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);
  GeraTr (Tr);
  ImprimeTr (Tr);
  k = MAXK; 
  GeraTabRank (g, Grafo.NumVertices, k, TabRank);
  TamTabRank = (Grafo.NumVertices + k - 1) / k;

  /*-- Salvando a FHPM gerada --*/
  fprintf(ArqSaida, "%d  (N)\n", N);
  fprintf(ArqSaida, "%d  (M)\n", M);
  fprintf(ArqSaida, "%d  (r)\n", r);
  fprintf(ArqSaida, "%d  (k)\n", k);

  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 ", ObtemValor2Bits(g, i)); 
  for (i = 0; i < M; i++) printf("%d ", ObtemValor2Bits(g, i)); 
  fprintf(ArqSaida, "  (g)\n");  
  printf("  (g)\n"); 

  for (i = 0; i < TamTabRank; i++) fprintf(ArqSaida, "%d ", TabRank[i]); 
  for (i = 0; i < TamTabRank; i++) printf("%d ", TabRank[i]); 
  fprintf(ArqSaida, "  (TabRank)\n");  
  printf("  (TabRank)\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;
}