#include "graph.h"

/* Thdse functions can use for both direct or undirect graph,
 * only be affected by argument 'directed' we give
 */

void retreat(char * str)
{
    fprintf(stderr,"%s\n",str);
    exit(EXIT_FAILURE);
}

void initializeGraph(graph * g, bool directed)
{
    int i;  /* counter */

    g->nvertices = 0;
    g->nedges = 0;
    g->directed = directed;

    for (i = 1; i <= MAXV; i++)
        g->degree[i] = 0;
    
    for (i = 1; i <= MAXV; i++)
        g->edges[i] = NULL;
}

/* x, y is a pair of vertices */
void insertEdge(graph * g, int x, int y, bool directed)
{
    edgeNode * p;       /* temporary pointer */

    p = (edgeNode *) malloc (sizeof(edgeNode));
    if (!p)
        retreat("Error allocate memory p");
    
    p->weight = 0;
    p->y = y;

    p->next = g->edges[x];      /* insert at head */
    g->edges[x] = p;

    g->degree[x]++;

    if (!directed)
        insertEdge(g,y,x,true);         /* add another one for undirected */
    else
        g->nedges++;
}

void readGraph(graph * g, bool directed)
{
    int i;      /* counter */
    int m;      /* number of edges */
    int x, y;   /* vertices in edge (x, y) / <x, y> */

    printf("Enter number of vertices and edges: ");
    scanf ("%d%d", &(g->nvertices), &m);    /* read number of vertices and edges */

    printf("Enter two vertices consist one edge: ");
    for (i = 1; i <= m; i++)
    {
        scanf("%d %d", &x, &y);             /* readindex and vertex */
        insertEdge(g,x,y,directed);         /* this is the one to make a graph */
    }
}

void printGraph(graph * g)
{
    int i;          /* counter */
    edgeNode * p;   /* temporary pointer */

    for (i = 1; i <= g->nvertices; i++)
    {
        printf("%d: ",i);
        p = g->edges[i];
        while (p)
        {
            printf(" %d", p->y);
            p = p->next;
        }
        putchar('\n');
    }
}

void purgeGraph(graph * g)
{
    int i;          /* counter */
    edgeNode * p, * q;   /* temporary pointer */

    for (i = 1; i < g->nvertices; i++)
    {
        p = g->edges[i];
        while (p)
        {
            q = p;
            p = p->next;
            free(q);
        }
    }
}

void initializeSearch(graph * g)
{
    int i;

//    time = 0;

    for (i = 0; i <= g->nvertices; i++)
    {
        g->processed[i] = false;
        g->discovered[i] = false;
        g->parent[i] = -1;
    }
}

void processVertexEarly(int v)
{
    printf("processed vertex %d\n",v);
}
void processVertexLate(int v)
{
}
void processEdge(int v, int y)
{
    printf("Process edge (%d,%d)\n",v,y);
}

void bfs(graph * g, int start)
{
    queue q;    /* queue of vertices to visit */
    int v;      /* current vertex */
    int y;      /* successor vertex */
    edgeNode * p; /* temporary pointer */

    initializeSearch(g);

    initQueue(&q);
    enQueue(&q,start);
    g->discovered[start] = true;

    while (!emptyQueue(&q))
    {
        v = deQueue(&q);
        processVertexEarly(v);
        g->processed[v] = true;
        p = g->edges[v];

        while (p)
        {
            y = p->y;
            if (!g->processed[y] || g->directed)
                processEdge(v,y);
            if (!g->discovered[y])
            {
                enQueue(&q,y);
                g->discovered[y] = true;
                g->parent[y] = v;
            }
            p = p->next;
        }
        processVertexLate(v);
    }
}