/***********************************************************
 *
 * Author: Carla N. Lintzmayer, carla.negri@ufabc.edu.br
 *
 ***********************************************************/

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

struct node {
    int rotulo;
    struct node *prox;
};

struct grafo {
    int n;
    int m;
    node_t **lista_adj;
};

grafo_t* cria_grafo(int n, int m) {
    grafo_t* G = malloc(sizeof(grafo_t));
    G->n = n;
    G->m = m;
    G->lista_adj = malloc(n * sizeof(node_t*));

    for (int u = 0; u < n; u++)
        G->lista_adj[u] = NULL;

    return G;
}

void adiciona_aresta(grafo_t *G, int u, int v) {
    node_t *x;

    /* Vertice u eh vizinho do v: adiciona node com rotulo u na lista de v */
    x = malloc(sizeof(node_t));
    x->rotulo = u;
    x->prox = G->lista_adj[v];
    G->lista_adj[v] = x;

    /* Vertice v eh vizinho do u: adiciona node com rotulo v na lista de u */
    x = malloc(sizeof(node_t));
    x->rotulo = v;
    x->prox = G->lista_adj[u];
    G->lista_adj[u] = x;
}

void imprime_grafo(grafo_t *G) {
    node_t *x;

    /* Para cada vertice u, imprime os vertices vizinhos dele */
    for (int u = 0; u < G->n; u++) {
        printf("%d:", u);
        x = G->lista_adj[u];
        while (x) {
            printf(" %d", x->rotulo);
            x = x->prox;
        }
        printf("\n");
    }
}

void deleta_grafo(grafo_t *G) {
    /* Libera memoria que foi alocada */
    node_t *x, *y;

    for (int u = 0; u < G->n; u++) {
        x = G->lista_adj[u];
        while (x) {
            y = x->prox;
            free(x);
            x = y;
        }
    }

    free(G->lista_adj);
    free(G);
}

int grau_vertice(grafo_t *G, int u) {
    node_t *x;
    int grau = 0;

    /* Percorre a lista do vertice u */
    x = G->lista_adj[u];
    while (x) {
        grau++;
        x = x->prox;
    }

    return grau;
}