#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>


#include "graph.h"



// insere um nó no início da lista
ALNode *addList(ALNode *list, int node, Info p) {
  ALNode *aux;

  aux = (ALNode*) malloc(sizeof(ALNode));
  aux->vert = node;
  aux->info = p;
  aux->next = list;

  return aux;
}


ALNode *findList(ALNode *list, int node) {
  ALNode *aux;

  for (aux=list; aux!=NULL ; aux=aux->next)
    if (aux->vert == node) return aux;

  return NULL;
}

void freeList(ALNode *list) {
  if (list!=NULL) {
    freeList(list->next);
    free(list);
  }
}


ALNode *dupList(ALNode *list) {
  ALNode *aux=NULL;
  if (list!=NULL) {
    aux = (ALNode*) malloc(sizeof(ALNode));
    aux->vert = list->vert;
    aux->info = list->info;
    aux->next = dupList(list->next);
  }

  return aux;
}



AMGraph converse_am(AMGraph g) {
  int i,j,aux;
  for (i=0; i<g.nVert; i++)
    for (j=0; j<i; j++) {
      aux = g.arco[i][j];
      g.arco[i][j] = g.arco[j][i];
      g.arco[j][i] = aux;
    }
  return g;
}
      

AMGraph init_am(int n) {
  AMGraph g;
  int i,j;

  g.nVert = n;
  for (i=0; i<n; i++)
    for (j=0; j<n; j++)
      g.arco[i][j]=0;

  return g;
}

ALGraph init_al(int n) {
  ALGraph g;
  int i;

  g.nVert = n;
  for (i=0; i<n; i++)
    g.adjL[i] = NULL;

  return g;
}

ALGraph am2al(AMGraph g1) {
  ALGraph g2=init_al(g1.nVert);

  int i,j;

  for (i=0; i<g1.nVert; i++)
    for (j=0; j<g1.nVert; j++)
      if (g1.arco[i][j]!=0) g2.adjL[i] = addList(g2.adjL[i],j,g1.arco[i][j]);

  return g2;
}


AMGraph al2am(ALGraph g1) {
  AMGraph g2=init_am(g1.nVert);

  printf("\nDEVE CONVERTER GRAFO PARA LISTAS DE ADJACÊNCIA\n");

  return g2;
}


ALNode *preds_am(AMGraph g, int node) {
  int i;
  ALNode* aux=NULL;

  for (i=0; i<g.nVert; i++)
    if (g.arco[i][node]!=0) aux = addList(aux, i, g.arco[i][node]);

  return aux;
}


ALNode *sucs_am(AMGraph g, int node) {
  int j;
  ALNode* aux=NULL;

  for (j=0; j<g.nVert; j++)
    if (g.arco[node][j]!=0) aux = addList(aux, j, g.arco[node][j]);

  return aux;
}

ALNode *sucs_al(ALGraph g, int node) {
  return dupList(g.adjL[node]);
}

ALNode *preds_al(ALGraph g, int node) {
  ALNode *res=NULL;

  printf("\nDEVE CALCULAR PREDECESSORES DO VÉRTICE %d\n",node);

  return res;
}


//Função auxiliar com informação dos vértices visitados
static ALNode* daCaminhoAux_al(ALGraph g, int orig, int dest, bool visit[]) {
  ALNode *res=NULL;

  printf("\nDEVE CALCULAR O CAMINHO DE %d PARA %d\n\n",orig,dest);

  return res;
}

  

ALNode* daCaminho_al(ALGraph g, int orig, int dest) {
  bool visit[MaxVert];
  ALNode *res=NULL;
  int i;

  //Inicializa array de visitados...
  for (i=0; i<g.nVert; i++)
    visit[i] = false;

  if (orig!=dest)
    res = daCaminhoAux_al(g,orig,dest,visit);

  // Se existir caminho, insere primeiro nó (origem) na lista...
  if (res!=NULL || orig==dest)
    res = addList(res,orig,0);

  return res;
}


void show_am(AMGraph g) {
  int i,j;

  printf("\n");
  for (i=0; i<g.nVert; i++) {
    for (j=0; j<g.nVert; j++)
      printf("%d ",g.arco[i][j]);
    printf("\n");
  }
}

void showList(ALNode *node) {
  if (node!=NULL) {
    printf("(%d:%d) ",node->vert,node->info);
    showList(node->next);
  }
}

void show_al(ALGraph g) {
  int i;
  printf("\n");
  for (i=0; i<g.nVert; i++) {
    showList(g.adjL[i]);
    printf("\n");
  }
}