## CodingBison

Before we go further, let us see how a graph looks like. Well, to put it simply, we can consider a graph to be a collection of vertices and edges. We provide a simple (undirected) graph that has 5 vertices and 4 edges; each vertex is identified by a number. Figure: An undirected Graph

The adjacency list for the above graph starts with a linked list for vertices -- this list would have all the 5 vertices. Further, for each vertex, the representation would also have all the edges that are connected to them. As an example, the vertex 280 has one edge: 280-101. So, for the vertex 280, we would see that its linked-list for edges would have one entry: 101. Please note that for an undirected graph, every edge would show up twice in the graph, one time with each vertex. Thus, 280-101 edge would mean an edge of 101 added to the vertex 280 and an edge of 280 added to the vertex 101. This is how the adjacency list would look like for the above graph. Besides undirected graphs, a graph can also additional behavior as well.

The graph can also have loops. In this case, we would have edges connected to each other so that it forms a loop. In the above example, if we were to add an edge between 680 and 880 vertices, then we would have a loop. An adjacency list can accommodate graphs with loops. As an extreme case, it is possible that we can have loops that start on a vertex and end at the same very vertex. For example, if we had an edge starting at vertex 101 and ending at 101, then we would have a loop starting at 101 and ending at 101.

The graph can also have directed edges. In that case, it is not a given that one can go in either direction. In the above example, if we were to make the edge 101-680 undirected such that we can go only from 101 to 680, then the picture would have an arrow going from 101 to 680. In terms of adjacency list, we would have 680 edge-node added to vertex 101, but we would not add edge-node 101 to vertex 680.

In terms of data-structures, the adjacency list implementation should offer data structures for both edges and vertices. In terms of functionality, the implementation should offer APIs for adding vertices, adding edges, at the very least. We start by providing the implementation and go over is details after that.

Before we get into the implementation, we would like to note that the implementation on this page has various elements so that it becomes generic and dense. If you would like to see an implementation that is simpler, then you can find it here: Simple Implementation of Adjacency List.

Our implementation consists of three files: (a) a header file that publishes the data-structures and the APIs, (b) a C file that contains the implementation of the published APIs, and (c) another C file that contains the main() routine and uses the adjacency list implementation. When we use this implementation for various applications, having the implementation in three different files allows applications to reuse the header file and the implementation file.

Our implementation provides various APIs (public functions) for doing various basic operations for adjacency list. The adjlist_add_vertex() takes a value and then adds a vertex with that value to the graph. The adjlist_add_edge() takes values of the two vertices and the edge weight. The implementation also has adjlist_free() function that frees up all vertices and edges belonging to the graph. Lastly, adjlist_print() prints all the vertices and edges belonging to the graph -- we can use this to dump all edges and vertices belonging to a graph.

``` adjlist_add_vertex(): Add a Vertex to an Adjacency List
```

Let us begin with the header file. We provide the file below; we will go over its description after that.

``` #ifndef __ADJACENCY_LIST_H___

#define COLOR_WHITE     1
#define COLOR_GRAY      2
#define COLOR_BLACK     3

typedef struct vertex_node_ {
int val;                         /* Holds an int. Can we extended, if needed. */
void *data;                      /* Holds satellite data associated with this vertex */
unsigned char       color;       /* For visited/unvisited state. */
unsigned int        set_number;  /* For partitioned Graphs. See Kruskal's algorithm. */
struct edge_node_   *list_enode; /* This is a linked list for all connected edges. */
struct vertex_node_ *next_vnode; /* This is the vertical linked list for all vertices. */
} vertex_node;

typedef struct edge_node_ {
void              *parent_vnode; /* Pointer to the parent vertex node. */
int               weight;        /* Weight of the link. */
struct edge_node_ *next_enode;   /* This is a linked list. */
} edge_node;

/* Free the Adjacency List */

/* Print the Adjacency List */
```

The above header file starts with two data structures: vertex_node for vertices and edge_node for edges. The vertex_node data-structures supports two linked lists -- one for the vertices and one for the edges belonging to a given vertex. The next_vnode pointer enables linked list for vertices and all the vertices of a graph are added to this linked list. The list_enode pointer enables linked list for all edges that belong to a given vertex.

Besides the linked list pointer (next_enode), the edge_node contains two additional members. The "parent_vnode" pointer holds the the address of the vertex node that is added to the edge list. Thus, if an edge is formed by vertices A-B, then when we add the edge to the vertex A, the parent_vnode of the edge would point to the vertex B. Likewise, when we add the edge A-B to the vertex B, the parent_vnode of the edge would point to the vertex A. Depending upon the use-case, it is possible to simplify this where the edge node contains the value (identifier) of the vertex. However, keeping a pointer allows us to have the edge node access the entire data associated with the vertex node and for cases, where we need to store more than an integer (the "val" member), a pointer would be more efficient.

The above header uses an integer for representing the identification (let us say, key) of a vertex. If need be, one can easily extend the value of the vertex to be a non-integer. Accordingly, we would need to update both adjlist_add_vertex() and adjlist_add_edge() to accept the values as non-integer and not an integer. Lastly, the adjlist_print() also assumes that the value of each vertex is an integer -- we would need to modify that as well. Our implementation also allows application to store a satellite data for each key.

The vertex_node and edge_node data-structure contain additional members for holding miscellaneous information. The vertex node has a member "color" which is used for marking the edge. Algorithms can use this to indicate the state of the vertex. Typically, we would do initialization by marking all vertices as white. For nodes that have been selected, we mark them as black. Lastly, for nodes that are being considered, we mark them as gray. The header file contains macros for all of these three colors as well. We choose to keep the color as "unsigned char" since that would accommodate up-to 256 colors and that is more than enough! The vertex_node also contains another member "set_number" -- this is used for graphs that are partitioned and we can use this value to indicate the set number that holds a vertex. Lastly, the edge_node also contains a member "weight" to indicate the weight of the edge.

Next, we provide the implementation of the adjacency list itself. Let us see the contents of the file first and then go over its description.

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

vertex_node *new_vnode, *vnode;

if (!graph_root)
return;

vnode = *graph_root;
while (vnode && vnode->next_vnode) {
if (vnode->val == current_value) {
/* If the value already exists, then return. */
return;
}
vnode = vnode->next_vnode;
}

printf("[%s] Adding Vertex Node (%d)\n", __FUNCTION__, current_value);
new_vnode = (vertex_node *)malloc(sizeof(vertex_node));
if (!new_vnode) {
fprintf(stderr, "[%s] Malloc failed \n", __FUNCTION__);
return;
}
new_vnode->val = current_value;
new_vnode->list_enode = NULL;
new_vnode->next_vnode = NULL;
new_vnode->color = 0;
new_vnode->data = data;

if (!*graph_root) {
*graph_root = new_vnode;
return;
}
vnode->next_vnode = new_vnode;
}

/* Add an Edge to a Vertex */
vertex_node *second_vnode,
int val_second_vertex, int weight) {
edge_node *enode, *prev_enode, *new_enode;

if (!first_vnode || !second_vnode)
return;

prev_enode = enode = first_vnode->list_enode;
while (enode) {
if (((vertex_node *)enode->parent_vnode)->val == val_second_vertex) {
return;
}
prev_enode = enode;
enode = enode->next_enode;
}

new_enode = (edge_node *)malloc(sizeof(edge_node));
if (!new_enode) {
fprintf(stderr, "[%s] Malloc failed \n", __FUNCTION__);
return;
}
new_enode->parent_vnode = second_vnode;
new_enode->next_enode = NULL;
new_enode->weight = weight;
if (prev_enode) {
prev_enode->next_enode = (void *)new_enode;
} else {
/* prev_enode is NULL means new_enode is the first enode for this vertex */
first_vnode->list_enode = (void *)new_enode;
}
}

vertex_node *vertex_nodeA = NULL;
vertex_node *vertex_nodeB = NULL;
vertex_node *vnode;

if (!graph_root)
return;

/*
* First, find the vnode for both vertices in the edge. We will
* add an enode to both of these vnodes.
*/
for (vnode = graph_root; vnode != NULL; vnode = vnode->next_vnode) {
if (vnode->val == vertexA) {
vertex_nodeA = vnode;
}
if (vnode->val == vertexB) {
vertex_nodeB = vnode;
}
if ((vertex_nodeA) && (vertex_nodeB)) {
break;
}
}

if (!vertex_nodeA) {
return;
}

if (!vertex_nodeB) {
return;
}

/* Add Edge to VertexA. When added, this edge would point to VertexB */
printf("\t[%s] Adding Edge (%d-%d) to Vertex Node (%d) \n",
__FUNCTION__, vertexA, vertexB, vertexA);

/* Add Edge to VertexB. When added, this edge would point to VertexA */
printf("\t[%s] Adding Edge (%d-%d) to Vertex Node (%d) \n",
__FUNCTION__, vertexA, vertexB, vertexB);
}

/* Free the Adjacency List */
vertex_node *vnode = NULL;
vertex_node *prev_vnode = NULL;
edge_node *enode = NULL;
edge_node *prev_enode = NULL;

if (!graph_root)
return;

vnode = *graph_root;
/* Walk the list of vertex nodes. */
while (vnode) {
/* For each vertex node, walk the list of edge nodes. */
enode = vnode->list_enode;
while (enode) {
prev_enode = enode;
enode = enode->next_enode;
free(prev_enode);
}
prev_vnode = vnode;
vnode = vnode->next_vnode;
free(prev_vnode);
}
*graph_root = NULL;
}

/* Print the Adjacency List */
vertex_node *vnode = NULL;
edge_node *enode = NULL;

printf("[%s] Print the Adjacency List", __FUNCTION__);
if (!graph_root) {
printf("\n[%s] Nothing to print. Return\n", __FUNCTION__);
return;
}

for (vnode = graph_root; vnode != NULL; vnode = vnode->next_vnode) {
printf("\n\tVertex [%3d][Color: %d]:", vnode->val, vnode->color);
for (enode = vnode->list_enode; enode != NULL; enode = enode->next_enode) {
printf(" -- Edge [%3d (%1d)]", ((vertex_node *)enode->parent_vnode)->val, enode->weight);
}
}
printf("\n");
}
```

In the above code, adjlist_add_vertex() is the function that adds a vertex to the adjacency list. It starts by walking the vertices linked list. If it finds an existing vertex with the same identifier (value), then it bails out. If not, then it walks to the last node of the list. If the vertex is not found, then it mallocs a new vertex node and adds it to the last vertex node and thus, extends the linked list.

Astute readers might also notice that for adjlist_add_vertex(), we pass the graph_root as a pointer to a pointer. However, for adjlist_add_edge(), we simply pass a pointer to the graph_root. The simple reason for that is the adjlist_add_vertex() function would end up modifying the graph_root, when adding the first vertex. But, adjlist_add_edge() does no such thing and so there is no need to pass a pointer to a pointer; a regular pointer does the job just fine!

The adjlist_print() and adjlist_free() are in some ways traversal routines. They walk over each vertex and edge of the graph. While the print routine prints each one of them, the free routine frees each one of them.

One minor detail. The implementation also comes with a global boolean, adjlist_print_debug, that controls the level of debugs. If we want to have minimal debug messages, then we should set it to false.

In the end, let us provide a simple user of the adjacency list implementation. Accordingly, we add our last C file that includes the adjacency header file (let us call it, "adjacency_list.h") and then invokes its APIs to add vertices, add edges, print the adjacency list, and then in the end, free the graph. Let us provide the file first and then we would go through the details.

``` #include <stdio.h>

int main() {
int vertices[] = {101, 237, 880, 680, 280};
int edges[] = {{237, 880, 10}, {101, 680, 4}, {101, 280, 8}, {237, 101, 2}};
int len = sizeof(vertices)/sizeof(vertices);
int i;

/* Root of the graph */
vertex_node *graph_root = NULL;

for (i = 0; i < len; i++) {
}

len = sizeof(edges)/sizeof(edges);
for (i = 0; i < len; i++) {
}

/* Done with the Adjacency List. Free it*/
}
```

The above file has two arrays, one for the vertices and one for the edges. Each element of the edge array contains three values -- one for each of the two vertices that it connects and one for the weight of that edge. Next, it calls adjlist_add_vertex() to add all of the vertices, one by one. Following that, it calls adjlist_add_edge() to add all of the edges to the previously added vertices list. To see the adjacency list, it also calls adjlist_print() after each of the steps. And in the end, it calls adjlist_free() to free the earlier allocated memory for various vertices and edges.

Here is the compilation step and the output. The output (provided below) is similar to the earlier case, except that now we see color for each vertex and weight for each edge.

``` user@codingtree\$ gcc main_adjacency_list.c adjacency_list.c -o adjacency

Vertex [Color: 0]:
Vertex [Color: 0]:
Vertex [Color: 0]:
Vertex [Color: 0]:
Vertex [Color: 0]: