Graph Implementation in C

A graph is a collection of nodes and edges. These nodes are connected by links(edges).
These edges may be directed or undirected. Moreover these edges can have weights associated with them

So edges can be categorized as :

1. Directed, weighted edges
2. Directed, unweighted edges
3. Undirected, weighted edges
4. Undirected, unweighted edges

Uses of graphs

Graphs are extremely useful. Look everywhere and one can easily find use of graphs. Listed below are a few of the vast set of practical uses of graphs.

Delhi Metro Rail Map

 Each station is a vertex, the distance in between is a weighted edge.

A Maze

 Each corner is a vertex, Line between two corners is and edge.

A tournament fixture
Courtesy: http://www.squadtd.com/

Each team is a vertex, match between the teams is an edge.

Kind of graphs

There are numerous classifications and types of graphs available. I have collected a few of those types from various sources and organized a list of types of graphs:

• Undirected Graphs

Undirected Graph

     Characteristics:

1. Order of vertices doesn't matter
2. 1-2 is same as 2-1

• Directed Graphs

Directed Graph

     Characteristics:

1. Order of vertices does matter
2. 1-2 is not same as 2-1

• Vertex labeled Graphs.

Vertex Labeled Graph

     Characteristics:

1. Each vertex contains additional information. e.g {2,orange}, {4,green}

• Cyclic Graphs.

Cyclic Graph

     Characteristics:

1. Graph contains at least one cycle.

• Edge labeled Graphs.

Edge Labeled Graph

     Characteristics:

1. Edge has labels e.g an edge in the above graph will be represented as {orange,green,{blue,cyan}}

• Weighted Graphs.

Weighted Graph

     Characteristics:

1. Each edge has some weight associated with it.

• Directed Acyclic Graphs.

Direct Acyclic Graph(DAG)

     Characteristics:

1. Graph has no cycles.

• Disconnected Graphs

Disconnected Graph

     Characteristics:

1. Vertices are disconnected 

• Mixed graph

Mixed Graph

     Characteristics:

1. Some edges may be directed and some may be undirected 

• Multigraph

Multigraph

     Characteristics:

1. Multiple edges (and sometimes loops) are allowed

• Quiver

          

     Characteristics:

1. Directed graph which may have more than one arrow from a given source to a given target. A quiver may also have directed loops in it.

Representation of graphs:

Fig. 1: An undirected graph

Fig 2: A directed graph

In order to use Graphs programatically , they need to be somehow represented in code. Following are the most widely used methods of representing a graph.

Adjacency Matrix : 

For N vertices an adjacency matrix is an NxN array A such that
                       A[i][j] = 1 if there is an edge E(i,j)
                                  = 0 otherwise

For an undirected graph, A[i][j] = A[j][i]

For weighted graphs,
                       A[i][j] = weight of the edge, if there is an edge E(i,j)
                                 = a constant representing no edge (e.g a very large or very small value)

For Fig 1, the adjacency matrix would be 

The adjacency matrix for directed graph in Fig 2 would be:

Adjacency List : 

Adjacency matrix representation consume a lot of memory (O[N²]). If the graph is complete or almost complete(i.e. contains most of the edges between the vertices), then this representation is good to use. But if there are very few edges as compared to number of vertices, it will unnecessarily consume extra space. Adjacency list can handle this situation very optimally.

Every vertex has a linked list of the vertices it is connected with.

Adjacency list for Fig 1 would be:

Adjacency list for Fig 2 would be:

Following is code snippet to implement graphs in C using adjacency list.

/*graph.h*/
#ifndef _GRAPH_H_
#define _GRAPH_H_

typedef enum {UNDIRECTED=0,DIRECTED} graph_type_e;

/* Adjacency list node*/
typedef struct adjlist_node
{
    int vertex;                /*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*/
}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*/
__inline void err_exit(char* msg)
{
    printf("[Fatal Error]: %s \nExiting...\n", msg);
    exit(1);
}

#endif

/*graph.c*/
#include <stdio.h>
#include <stdlib.h>
#include "graph.h"

/* 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->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 * 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].num_members = 0;
    }

    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++;
    }
}

/* Function to print the adjacency list of graph*/
void displayGraph(graph_p graph)
{
    int i;
    for (i = 0; i < graph->num_vertices; i++)
    {
        adjlist_node_p adjListPtr = graph->adjListArr[i].head;
        printf("\n%d: ", i);
        while (adjListPtr)
        {
            printf("%d->", adjListPtr->vertex);
            adjListPtr = adjListPtr->next;
        }
        printf("NULL\n");
    }
}

int main()
{
    graph_p undir_graph = createGraph(5, UNDIRECTED);
    graph_p dir_graph = createGraph(5, DIRECTED);
    addEdge(undir_graph, 0, 1);
    addEdge(undir_graph, 0, 4);
    addEdge(undir_graph, 1, 2);
    addEdge(undir_graph, 1, 3);
    addEdge(undir_graph, 1, 4);
    addEdge(undir_graph, 2, 3);
    addEdge(undir_graph, 3, 4);

    addEdge(dir_graph, 0, 1);
    addEdge(dir_graph, 0, 4);
    addEdge(dir_graph, 1, 2);
    addEdge(dir_graph, 1, 3);
    addEdge(dir_graph, 1, 4);
    addEdge(dir_graph, 2, 3);
    addEdge(dir_graph, 3, 4);

    printf("\nUNDIRECTED GRAPH");
    displayGraph(undir_graph);
    destroyGraph(undir_graph);

    printf("\nDIRECTED GRAPH");
    displayGraph(dir_graph);
    destroyGraph(dir_graph);

    return 0;
}

Sources:
http://en.wikipedia.org/wiki/Graph_(mathematics)
http://web.cecs.pdx.edu/~sheard/course/Cs163/Doc/Graphs.html
http://msdn.microsoft.com/en-us/library/ms379574(v=vs.80).aspx