graph.h

/*

Source code is from Varun Gupta's blog
http://simplestcodings.blogspot.tw/2013/09/graphs.html?view=sidebar

*/
#ifndef _GRAPH_H_
#define _GRAPH_H_
 
typedef enum {UNDIRECTED = 0,DIRECTED} graph_type_e;
/* Adjacency list node*/
typedef struct adjlist_node
{
    int vertex, endTime;                /*Index to adjacency list array*/
    struct adjlist_node *next;          /*Pointer to the next node*/
}adjlist_node_t, *adjlist_node_p;
 
/* Adjacency list */
typedef struct adjlist
{
    int num_members;           /*number of members in the list (for future use)*/
    adjlist_node_t *head;      /*head of the adjacency linked list*/
    int vertex;
    int endTime_1st, endTime_2nd;
    int leader;
}adjlist_t, *adjlist_p;
 
/* Graph structure. A graph is an array of adjacency lists.
   Size of array will be number of vertices in graph*/
typedef struct graph
{
    graph_type_e type;        /*Directed or undirected graph */
    int num_vertices;         /*Number of vertices*/
    adjlist_p adjListArr;     /*Adjacency lists' array*/
}graph_t, *graph_p;
 
/* Exit function to handle fatal errors*/
void err_exit(char* msg)
{
    printf("[Fatal Error]: %s \nExiting...\n", msg);
    exit(1);
}

/* Function to create an adjacency list node*/
adjlist_node_p createNode(int v)
{
    adjlist_node_p newNode = (adjlist_node_p)malloc(sizeof(adjlist_node_t));
    if(!newNode)
        err_exit("Unable to allocate memory for new node");
 
    newNode->vertex = v;
    newNode->endTime = -1;
    newNode->next = NULL;
 
    return newNode;
}
 
/* Function to create a graph with n vertices; Creates both directed and undirected graphs*/
graph_p createGraph(int n, graph_type_e type)
{
    int i;
    graph_p graph = (graph_p)malloc(sizeof(graph_t));
    if(!graph)
        err_exit("Unable to allocate memory for graph");
    graph->num_vertices = n;
    graph->type = type;
 
    /* Create an array of adjacency lists*/
    graph->adjListArr = (adjlist_p)malloc((n + 1) * sizeof(adjlist_t));
    if(!graph->adjListArr)
        err_exit("Unable to allocate memory for adjacency list array");
 
    for(i = 0; i <= n; i++)
    {
        graph->adjListArr[i].head = NULL;
        graph->adjListArr[i].vertex = i;
        graph->adjListArr[i].num_members = 0;
        graph->adjListArr[i].endTime_1st = -1;
        graph->adjListArr[i].endTime_2nd = -1;
        graph->adjListArr[i].leader = -1;
    }
    return graph;
}
 
/*Destroys the graph*/
void destroyGraph(graph_p graph)
{
    if(graph)
    {
        if(graph->adjListArr)
        {
            int v;
            /*Free up the nodes*/
            for (v = 0; v <= graph->num_vertices; v++)
            {
                adjlist_node_p adjListPtr = graph->adjListArr[v].head;
                while (adjListPtr)
                {
                    adjlist_node_p tmp = adjListPtr;
                    adjListPtr = adjListPtr->next;
                    free(tmp);
                }
            }
            /*Free the adjacency list array*/
            free(graph->adjListArr);
        }
        /*Free the graph*/
        free(graph);
    }
}
 
/* Adds an edge to a graph*/
void addEdge(graph_t *graph, int src, int dest)
{
    /* Add an edge from src to dst in the adjacency list*/
    adjlist_node_p newNode = createNode(dest);
    newNode->next = graph->adjListArr[src].head;
    graph->adjListArr[src].head = newNode;
    graph->adjListArr[src].num_members++;
 
    if(graph->type == UNDIRECTED)
    {
        /* Add an edge from dest to src also*/
        newNode = createNode(src);
        newNode->next = graph->adjListArr[dest].head;
        graph->adjListArr[dest].head = newNode;
        graph->adjListArr[dest].num_members++;
    }
}

#endif