#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include "grafo.h"

typedef struct _viz Viz;

struct _viz {
  int noj;
  float peso;
  Viz*  prox;
};

struct _grafo {
  int nv;           /* numero de nos ou vertices */
  int na;           /* numero de arestas */
  Viz** viz;         /* viz[i] aponta para a lista de arestas vizinhas do no i */
};

/* aux para fila e pilha */
typedef struct _sq SQ;
struct _sq {
  int info;
  SQ* prox;
};

static SQ* newList (){
  return NULL;
}

static SQ* enqueue(SQ* queue, int info){
  SQ* novo = (SQ*)malloc(sizeof(SQ));
  SQ* aux = queue;
  assert(novo);
  novo->info = info;
  novo->prox = NULL;
  if (!queue){
    return novo;
  }
  while (aux->prox){
    aux = aux->prox;
  }
  aux->prox = novo;
  return queue;
}

static SQ* dequeue(SQ* queue,int* info){
  SQ* libera;
  if (!queue){
    *info = -1;
    return NULL;
  }
  *info = queue->info;
  libera = queue;
  queue = queue->prox;
  free(libera);
  return queue;
}

static SQ* pop(SQ* stack,int* popped_info){
  SQ* libera;
  if (!stack){
    *popped_info = -1;
    return NULL;
  }
  *popped_info = stack->info;
  libera = stack;
  stack = stack->prox;
  free(libera);
  return stack;
}

static SQ* push(SQ* stack, int info){
  SQ* novo = (SQ*)malloc(sizeof(SQ));
  assert(novo);
  novo->info = info;
  novo->prox = stack;
  return novo;
}

static Viz* criaViz(Viz* head, int noj, float peso) {
/* insere vizinho no inicio da lista */
  Viz* no = (Viz*) malloc(sizeof(Viz));
  assert(no);
  no->noj = noj;
  no->peso = peso;
  no->prox = head;
  return no;
}

static Grafo* grafoCria(int nv, int na) {

  int i;
  Grafo* g = (Grafo *) malloc(sizeof(Grafo));
  g->nv = nv;
  g->na = na;
  g->viz = (Viz **) malloc(sizeof(Viz *) * nv);
  for (i = 0; i < nv; i++)
    g->viz[i] = NULL;
  return g;
}


Grafo* grafoLe( char* filename ) {
/* cria grafo não orientado - supõe que arquivo está correto! */

  FILE *arq = fopen(filename,"rt");
  int nv, na, no1, no2 = 0;
  float peso;
  Grafo* novo;
	
  fscanf(arq, "%d %d", &nv, &na);
  novo = grafoCria(nv, na);
  assert(novo);
  while (fscanf(arq, "%d %d %f", &no1, &no2, &peso) == 3) {
    novo->viz[no1] = criaViz(novo->viz[no1], no2, peso);
    novo->viz[no2] = criaViz(novo->viz[no2], no1, peso);
  }
  return novo;
}

Grafo*   grafoLibera(Grafo* grafo) {
  if (grafo) {
    int i = 0;
    Viz* no,*aux;
    for (i = 0; i < grafo->nv; i++){
      no = grafo->viz[i];
      while (no){
        aux = no->prox;
        free(no);
        no = aux;
      }
    }
    free(grafo->viz);
    free(grafo);
  }
  return NULL;
}

void grafoMostra (char* title, Grafo * grafo) {
  int i;
  if (title)
    printf("%s", title);
  if (grafo) {
    printf("NV: %d, NA: %d\n", grafo->nv, grafo->na);
    for (i = 0; i < grafo->nv; i++){
    Viz* viz = grafo->viz[i];
    printf("[%d]->", i);
    while (viz) {
      printf("{%d, %g}->", viz->noj, viz->peso);
      viz = viz->prox;
    }
    printf("NULL\n");
    }
  }
}

static void visitaprof (Viz** vizinhos, int no, char *visitado){
  Viz *noviz = vizinhos[no];
  printf("%d ", no); 
  visitado[no] = 1;
  while (noviz!=NULL){
    if (!visitado[noviz->noj]) visitaprof(vizinhos, noviz->noj, visitado);
    noviz = noviz->prox;
  }
}

void grafoPercorreProfundidade(Grafo *grafo, int no_inicial){
  int no;  
  char *visitado;
  if (grafo == NULL) return;
  visitado = (char*) malloc(sizeof(int)*grafo->nv);
  assert(visitado);
  for (no=0;no<(grafo->nv);no++) visitado[no] = 0;
  visitaprof (grafo->viz, no_inicial, visitado);
  printf ("\n");
} 


Grafo* criaArvoreGeradora (Grafo *grafo, int no_inicial) {
  return NULL;
}

void grafoPercorreLargura(Grafo *grafo, int no_inicial){
  SQ *q = newList();
  Viz *v; int no;  
  int *enfileirado;
  if (grafo == NULL) return;
  enfileirado = (int*) malloc(sizeof(int)*grafo->nv);
  for (no=0;no<(grafo->nv);no++) enfileirado[no] = 0;
  q = enqueue (q, no_inicial);
  enfileirado[no_inicial] = 1;
  q = dequeue(q, &no);
  while (no>=0) {
    printf ("%d-", no);
    v = grafo->viz[no];
    while (v!=NULL) {
      if (!enfileirado[(v->noj)]) {
        q = enqueue (q, v->noj);
        enfileirado[v->noj] = 1;
      }
      v = v->prox;
    }
    q=dequeue(q, &no);
  }
 printf ("\n");
} 

void grafoPercorreProfundidade2 (Grafo *grafo, int no_inicial){
  SQ *q = newList();
  Viz *v; int no;  
  int *visitado;
  if (grafo == NULL) return;
  visitado = (int*) malloc(sizeof(int)*grafo->nv);
  for (no=0;no<(grafo->nv);no++) visitado[no] = 0;
  q = push (q, no_inicial);
  q = pop(q, &no);
  while (no>=0) {
    if (!visitado[no]){
      visitado[no] = 1;
      printf ("%d-", no);
      v = grafo->viz[no];
      while (v!=NULL) {
        q = push (q, v->noj);
        v = v->prox;
      }
    }
    q=pop(q, &no);
  }
 printf ("\n");
}