Tag Archives: Queue

Connected components of a graph in C

Introduction

A connected component of a graph is a maximal subgraph in which the vertices are all connected, and there are no connections between the subgraph and the rest of the graph. A connected graph has only one connected component, which is the graph itself, while unconnected graphs have more than one component. For example, the graph shown below has three components, (0, 1, 2, 3), (4, 5, 6), and (7, 8).
Graph with three connected components
The connected components of a graph can be found using either a depth-first search (DFS), or a breadth-first search (BFS). We start at an arbitrary vertex, and visit every vertex adjacent to it recursively, adding them to the first component. Once this search has finished, we have visited all of the vertices in the first connected component, so we choose another unvisited vertex (if any) and perform the same search starting from it, adding the vertices we find to the second component. This process continues until all vertices have been visited, at which point we know the number of connected components in the graph, and which vertices they contain.

These are implementations of both connected components algorithms in C. An array is used to store the number of the connected component for each vertex, starting with component 0. The array elements are initialised to -1 so the array is also used to determine which vertices have not yet been visited, as their component number will still be -1.
The graph edges are represented as a struct as follows:

typedef struct {
    unsigned int first;
    unsigned int second;
} edge;

Depth-first search

#include <stdlib.h>

void connected_components_recursive(const edge *edges, unsigned int n, 
        int *components, unsigned int order, unsigned int vertex,
        unsigned int component)
{
    unsigned int i;
    /* Put this vertex in the current component */
    components[vertex] = component; 
    for (i = 0; i < n; i++) {
        if (edges[i].first == vertex || edges[i].second == vertex) {
            /* Adjacent */
            const unsigned int neighbour = edges[i].first == vertex ?
                    edges[i].second : edges[i].first;
            if (components[neighbour] == -1) {
                /* Not yet visited */
                connected_components_recursive(edges, n, components, order, neighbour, component);
            }
        }
    }
}

unsigned int connected_components(const edge *edges, unsigned int n, unsigned int order, 
        int **components)
{
    unsigned int i;
    unsigned int component = 0;
    *components = malloc(order * sizeof(int));
    if (components == NULL) {
        return 0;
    }
    for (i = 0; i < order; i++) {
        (*components)[i] = -1;
    }
    
    for (i = 0; i < order; i++) {
        if ((*components)[i] == -1) {
            connected_components_recursive(edges, n, *components, order, i, component);
            component++;
        }
    }
    return component;
}

Breadth-first search

#include <stdlib.h>

#include <cirque.h>

static void connected_components_internal(const edge *edges, unsigned int n,
        int *components, unsigned int order, unsigned int vertex,
        unsigned int component)
{
    unsigned int i;
    /* Put this vertex in the current component */
    components[vertex] = component;
    cirque *queue = cirque_create();
    if (!queue) {
        cirque_delete(queue);
        return;
    }
    cirque_insert(queue, &vertex);
    while (cirque_get_count(queue)) {
        unsigned int e;
        unsigned int *current = cirque_remove(queue);
        for (e = 0; e < n; e++) {
            if (edges[e].first == *current || edges[e].second == *current) {
                const unsigned int *neighbour = edges[e].first == *current ?
                    &edges[e].second : &edges[e].first;
                if (components[*neighbour] == -1) {
                    components[*neighbour] = component;
                    cirque_insert(queue, (void*)neighbour);
                }
            }
        }
    }
    cirque_delete(queue);
}

unsigned int connected_components(const edge *edges, unsigned int n, unsigned int order,
   int **components)
{
    unsigned int i;
    unsigned int component = 0;
    *components = malloc(order * sizeof(int));
    if (components == NULL) {
        return 0;
    }
    for (i = 0; i < order; i++) {
        (*components)[i] = -1;
    }

    for (i = 0; i < order; i++) {
        if ((*components)[i] == -1) {
            connected_components_internal(edges, n, *components, order, i, component);
            component++;
        }
    }
    return component;
}

Example program

Here is an example program that constructs the graph shown above and then finds its connected components:

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

static void print_components(int *components, unsigned int order)
{
    unsigned int i;
    for (i = 0; i < order; i++) {
        printf("Vertex %u is in component %d\n", i, components[i]);
    }
}

int main(void)
{
    const unsigned int order = 9; /* Vertices */
    const unsigned int n = 8; /* Edges */
    edge *edges;
    int *components;
    unsigned int c;
   
    edges = malloc(n * sizeof(edge));
    if (edges == NULL) {
        return 1;
    }

    /* Square */
    edges[0].first = 0;
    edges[0].second = 1;
    edges[1].first = 1;
    edges[1].second = 2;
    edges[2].first = 2;
    edges[2].second = 3;
    edges[3].first = 3;
    edges[3].second = 0;

    /* Triangle */
    edges[4].first = 4;
    edges[4].second = 5;
    edges[5].first = 5;
    edges[5].second = 6;
    edges[6].first = 6;
    edges[6].second = 4;

    /* Line */
    edges[7].first = 7;
    edges[7].second = 8;

    c = connected_components(edges, n, order, &components);
    if (components == NULL) {
        free(edges);
        return 1;
    }
    printf("There are %u components:\n", c);
    print_components(components, order);
    free(edges);
    free(components);

    return 0;
}

The output:

There are 3 components:
Vertex 0 is in component 0
Vertex 1 is in component 0
Vertex 2 is in component 0
Vertex 3 is in component 0
Vertex 4 is in component 1
Vertex 5 is in component 1
Vertex 6 is in component 1
Vertex 7 is in component 2
Vertex 8 is in component 2

The connected components of a graph can also be represented as sets of edges, rather than vertices. This is called the spanning forest of a graph.

Circular queue in C

A circular queue, or ring buffer is an array that wraps around, so that it can be used as a queue without walking backwards in memory.

This implementation reallocates the buffer when it becomes full (i.e., when the head and tail of the queue meet).

The header file:

#ifndef CIRQUE_H
#define CIRQUE_H

struct cirque {
	unsigned int head; /* First element */
	unsigned int tail; /* 1 past the last element */
	unsigned int is_full;
	void ** entries;
	unsigned int size;
};
typedef struct cirque cirque;

typedef void (*cirque_forfn)(void*);

cirque * cirque_create(void);
void cirque_delete(cirque * queue);
unsigned int cirque_insert(cirque * queue, void * data);
void *  cirque_remove(cirque * queue);
void *cirque_peek(const cirque * queue);
unsigned int cirque_get_count(const cirque * queue);
void cirque_for_each(const cirque * queue, cirque_forfn fun);

#endif /* CIRQUE_H */

Implementation:

#include <stdlib.h>

#include <cirque.h>

cirque * cirque_create(void)
{
    const unsigned int size = 4;
	cirque * queue = malloc(sizeof(cirque));
	if (queue) {
		queue->entries = malloc(size * sizeof(void *));
		if (queue->entries) {
			queue->size = size;
			queue->head = 0;
			queue->tail = 0;
			queue->is_full = 0;
		}
		else {
			free(queue);
			queue = NULL;
		}
	}
	return queue;
}

void cirque_delete(cirque * queue)
{
	if (queue) {
		free(queue->entries);
		free(queue);
	}
}

static void cirque_resize(cirque * queue)
{
	void **temp = malloc(queue->size * 2 * sizeof(void *));
	if (temp) {
		unsigned int i = 0;
		unsigned int h = queue->head;
		do {
			temp[i] = queue->entries[h++];
			if (h == queue->size) {
				h = 0;
			}
			i++;
		} while (h != queue->tail);
		free(queue->entries);
		queue->entries = temp;
		queue->head = 0;
		queue->tail = queue->size;
		queue->size *= 2;
		queue->is_full = 0;
	}
}

static unsigned int cirque_is_empty(const cirque * queue)
{
	return (queue->head == queue->tail) && !queue->is_full;
}

unsigned int cirque_insert(cirque * queue, void * data)
{
	unsigned int result;
	if (queue->is_full) {
		cirque_resize(queue);
		if (queue->is_full) {
			result = 0;
		}
	}
	if (!queue->is_full) {
		queue->entries[queue->tail++] = data;
		if (queue->tail == queue->size) {
			queue->tail = 0;
		}
		if (queue->tail == queue->head) {
			queue->is_full = 1;
		}
		result = 1;
	}
	return result;
}

void * cirque_remove(cirque * queue)
{
	void * data = NULL;
	if (!cirque_is_empty(queue)) {
		if (queue->is_full) {
			queue->is_full = 0;
		} 
		data = queue->entries[queue->head++];
		if (queue->head == queue->size) {
			queue->head = 0;
		}
	}
	return data;
}
  
void *cirque_peek(const cirque * queue)
{
	void *data = NULL;
	if (!cirque_is_empty(queue)) {
		data = queue->entries[queue->head];
	}
	return data;
}

unsigned int cirque_get_count(const cirque * queue)
{
	unsigned int count;
   	if (cirque_is_empty(queue)) {
		count = 0;
	}
	else if (queue->is_full) {
		count = queue->size;
	}
	else if (queue->tail > queue->head) {
		count = queue->tail - queue->head;
	}
	else {
		count = queue->size - queue->head;
		if (queue->tail > 0) {
			count += queue->tail - 1;
		}
	}
	return count;
}

void cirque_for_each(const cirque * queue, cirque_forfn fun)
{
	if (!cirque_is_empty(queue)) {
		unsigned int h = queue->head;
		do {
			fun(queue->entries[h++]);
			if (h == queue->size) {
				h = 0;
			}
		} while (h != queue->tail);
	}
}

An example program:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#include <cirque.h>

int main(void)
{
    cirque * queue;
    char buf[16];
    unsigned int f;
    const unsigned int max = 32;
    const unsigned int limit = 16;

    queue = cirque_create();
    for (f = 0; f < max; f++) {
        sprintf(buf, "Item %d", f);
        if (f >= limit) {
            /* Start removing at limit to show the queue doesn't keep growing */
            char *data = cirque_remove(queue);
            printf("Removed %s\n", data);
            free(data);
        }
        printf("Inserting %s\n", buf);
        cirque_insert(queue, strdup(buf));
    }
    cirque_for_each(queue, (cirque_forfn)puts);
    printf("Size is %d (should be %d)\n", queue->size, limit);
    cirque_for_each(queue, free);
    cirque_delete(queue);

    return 0;
}