Greedy Maximum Independent Set in C

An independent set of a graph is some subset of the vertices where no vertex in the subset is connected to another vertex in the subset. For example, in the graph shown below, the set of vertices (0, 2, 4) is an independent set, as is (1, 3, 5).

The Maximimum Independent Set (MIS) problem is to find an independent set with the greatest cardinality in a graph. The problem is NP-complete, but a greedy algorithm gives a good approximation.

The algorithm is:

1. 1. Start with the set of vertices of the graph, $$V$$ and an empty set for the MIS, $$S$$
2. While $$V \ne \emptyset$$:
1. Find a vertex of minimum degree $$v \in V$$
2. Add it to $$S$$
3. Remove it and its neighbours from $$V$$

The following is an implementation in C;

#include <stdlib.h>

/* Graph edge */
typedef struct {
unsigned int first;
unsigned int second;
} edge;

/* State a vertex can be in */
typedef enum {
IN_GRAPH = 0,
IN_MIS = 1,
} vertex_state;

/* Vertex info */
typedef struct {
vertex_state state;
unsigned int degree;
} vertex_info;

/* Create and initialise the data structure for vertices */
static vertex_info *create_vertices(const edge *edges, unsigned int size,
unsigned int order)
{
unsigned int i;
vertex_info *vertices = malloc(order * sizeof(vertex_info));
if (vertices == NULL) {
return 0;
}
for (i = 0; i < order; i++) {
vertices[i].state = IN_GRAPH;
vertices[i].degree = 0;
}
for (i = 0; i < size; i++) {
vertices[edges[i].first].degree++;
vertices[edges[i].second].degree++;
}
return vertices;
}

/* Find a vertex with the lowest degree of any in the graph */
static int min_degree_vertex(const vertex_info *vertices, unsigned int order)
{
unsigned int min_degree = 0;
int min_vertex = -1;
unsigned int i;
for (i = 0; i < order; i++) {
if (vertices[i].state == IN_GRAPH
&& (min_degree == 0
|| vertices[i].degree < min_degree))
{
min_degree = vertices[i].degree;
min_vertex = i;
}
}
return min_vertex;
}

/* Move a vertex from the graph, adjusting the degrees of its neighbours */
static void move_vertex(vertex_info *vertices, unsigned int order, const edge *edges,
unsigned int size, unsigned int v, vertex_state state)
{
unsigned int e;
/* Remove vertex */
vertices[v].state = state;
/* Reduce the degrees of its neighbours */
for (e = 0; e < size; e++) {
if (edges[e].first == v
&& vertices[edges[e].second].state == IN_GRAPH)
{
vertices[edges[e].second].degree--;
}
else if (edges[e].second == v
&& vertices[edges[e].first].state == IN_GRAPH)
{
vertices[edges[e].first].degree--;
}
}
}

/* Create the MIS array from the vertices structure */
static unsigned int *create_mis(const vertex_info *vertices, unsigned int order,
unsigned int m)
{
unsigned int *mis = malloc(m * sizeof(unsigned int));
if (mis) {
unsigned int v, m = 0;
for (v = 0; v < order; v++) {
if (vertices[v].state == IN_MIS) {
mis[m++] = v;
}
}
}
return mis;
}

unsigned int maximum_independent_set(const edge *edges, unsigned int size,
unsigned int order, unsigned int **mis)
{
unsigned int m = 0;
vertex_info *vertices;
unsigned int finished = 0;
unsigned int i;

/* Create vertices structure */
vertices = create_vertices(edges, size, order);

/* Main algorithm */
while (!finished) {
/* Find a vertex of minimum degree */
int v = min_degree_vertex(vertices, order);
if (v != -1) {
/* Put it in the independent set */
move_vertex(vertices, order, edges, size, v, IN_MIS);
m++;
/* Remove its neighbours from the graph */
for (i = 0; i < size; i++) {
if (edges[i].first == v
&& vertices[edges[i].second].state == IN_GRAPH)
{
move_vertex(vertices, order, edges, size,
}
else if (edges[i].second == v
&& vertices[edges[i].first].state == IN_GRAPH)
{
move_vertex(vertices, order, edges, size,
}
}
}
else {
finished = 1;
}
}

/* Create and populate MIS array */
*mis = create_mis(vertices, order, m);
if (*mis == NULL) {
m = 0;
}

free(vertices);

return m;
}


An example program to find an MIS in the graph shown above:

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

/* Create a wheel graph of order n */
unsigned int wheel_graph(unsigned int n, edge **edges)
{
const unsigned int size = 2 * n - 2;
*edges = malloc(size * sizeof(edge));
if (*edges != NULL) {
/* Create the rim */
unsigned int i;
for (i = 0; i < n - 2; i++) {
(*edges)[i].first = i;
(*edges)[i].second = i + 1;
}
(*edges)[i].first = n - 2;
(*edges)[i].second = 0;
/* Create the spokes */
for (i = 0; i < n - 1; i++) {
(*edges)[n + i - 1].first = i;
(*edges)[n + i - 1].second = n - 1;
}
}
return size;
}

static void print_mis(const unsigned int *mis, size_t m)
{
unsigned int i;
for (i = 0; i < m; i++) {
printf("%u ", mis[i]);
}
putchar('\n');
}

int main(void)
{
unsigned int order = 7; /* Vertices */
unsigned int *mis;
edge *edges;
unsigned int size = wheel_graph(order, &edges);
unsigned m = maximum_independent_set(edges, size, order, &mis);
print_mis(mis, m);
free(mis);
free(edges);
return 0;
}


The output:

0 2 4


Graph cycle detection in C

A cycle in a graph is simply a path whereby one can get from a vertex back to itself. For example, in the graph below there is a cycle (0, 1, 2, 3, 0).

A graph containing at least one cycle is called a cyclic graph, and a graph without cycles is called an acyclic graph.

Detecting whether a graph is cyclic or acyclic can be easily performed using a Depth First Search (DFS). We simply start at an arbitrary vertex, visit each of its neighbours, then each of the neighbour’s neighbours, and so on. If at any point we find a neighbour that we have visited already, and we haven’t just come from there, then we have detected a cycle.

Here is an implementation in C. Notice that, because it is a DFS, it is very similar to the connected components algorithm I described earlier, which also does a DFS.

#include <stdlib.h>

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

static unsigned int cyclic_recursive(const edge *edges, unsigned int n, unsigned int *visited,
unsigned int order, unsigned int vertex, unsigned int predecessor)
{
unsigned int i;
unsigned int cycle_found = 0;
visited[vertex] = 1;
for (i = 0; i < n && !cycle_found; i++) {
if (edges[i].first == vertex || edges[i].second == vertex) {
const unsigned int neighbour = edges[i].first == vertex ?
edges[i].second : edges[i].first;
if (visited[neighbour] == 0) {
/* Not yet visited */
cycle_found = cyclic_recursive(edges, n, visited, order, neighbour, vertex);
}
else if (neighbour != predecessor) {
/* Found a cycle */
cycle_found = 1;
}
}
}
return cycle_found;
}

unsigned int cyclic(const edge *edges, unsigned int n, unsigned int order)
{
unsigned int *visited = calloc(order, sizeof(unsigned int));
unsigned int cycle_found;
if (visited == NULL) {
return 0;
}
cycle_found  = cyclic_recursive(edges, n, visited, order, 0, 0);
free(visited);
return cycle_found;
}


An example program to find out if the graph shown at the top is cyclic or acyclic:

#include <stdio.h>

int main(void)
{
const unsigned int order = 6; /* Vertices */
const unsigned int n = 6; /* Edges */
edge *edges;
unsigned int c;

edges = malloc(n * sizeof(edge));
if (edges == NULL) {
return 1;
}

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;
edges[4].first = 3;
edges[4].second = 4;
edges[5].first = 3;
edges[5].second = 5;

c = cyclic(edges, n, order);
printf("Graph is %s.\n", c ? "cyclic" : "acyclic");
free(edges);

return 0;
}


The output:

Graph is cyclic.


Spanning trees of a graph in C

A spanning tree of a graph is a subgraph that includes all of the vertices, but only enough edges to connect them. A connected graph will have more than one spanning tree unless the graph is a tree, in which case it has just one spanning tree which is the graph itself. A spanning tree of a graph of order $$v$$ will contain $$v – 1$$ edges.

In order to list all of the spanning trees of a graph, we could just construct all of the subsets of the edges of size $$v – 1$$, and then check if they form a spanning tree, but that wouldn’t be very efficient. A more efficient method is to use backtracking, which is what the algorithm presented here does.

In order to decide whether or not to add an edge to a partially constructed spanning tree, the algorithm checks that the candidate edge:

1. Has a higher numeric index than its predecessor
2. Doesn’t have both edges in the same connected component of the tree

The first condition prevents duplicates because the edges are always listed in ascending order. The second one ensures that the tree doesn’t contain too many edges, because an edge is superfluous if both of its endpoints are in the same connected component. In order to check this condition, I used the connected components of a graph algorithm I described previously.

The C code is below. The function spanning_trees() takes a graph in edge list representation, the number of edges and vertices, and a user callback that is called for every spanning tree found.

#include <stdlib.h>

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

typedef void (*treefn)(const edge *, unsigned int);

/* Check if vertices v1 and v2 are in different components in the tree */
static unsigned int different_components(const edge *tree, unsigned int t, unsigned int order,
unsigned int v1, unsigned int v2)
{
int *components;
unsigned int different;
connected_components(tree, t, order, &components);
different = components[v1] != components[v2];
free(components);
return different;
}

static void spanning_trees_recursive(const edge *edges, unsigned int n, unsigned int order,
edge *tree, unsigned int t, int predecessor, treefn fun)
{
if (t == order - 1) {
/* Found a tree */
fun(tree, order - 1);
}
else {
unsigned int e;
for (e = predecessor + 1; e < n; e++) {
if (t == 0 /* First edge */
|| different_components(tree, t, order,
edges[e].first, edges[e].second))
{
tree[t] = edges[e];
spanning_trees_recursive(edges, n, order, tree, t + 1, e, fun);
}
}
}
}

void spanning_trees(const edge *edges, unsigned int n, unsigned int order, treefn fun)
{
edge *tree;
tree = malloc((n - 1) * sizeof(edge));
if (tree == NULL) {
return;
}
spanning_trees_recursive(edges, n, order, tree, 0, -1, fun);
free(tree);
}


Here is an example that prints all of the spanning trees of the complete graph on 5 vertices:

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

/* Calculate the nth triangular number T(n) */
unsigned int triangular_number(unsigned int n)
{
return (n * (n + 1)) / 2;
}

/* Construct a complete graph on v vertices */
edge *complete_graph(unsigned int v)
{
const unsigned int n = triangular_number(v - 1);
unsigned int i, j, k;
edge *edges = malloc(n * sizeof(edge));
if (edges != NULL) {
for (i = 0, k = 0; i < v - 1; i++) {
for (j = i + 1; j < v; j++) {
edges[k].first = i;
edges[k].second = j;
k++;
}
}
}
return edges;
}

/* Print the edges in a tree */
static void print_tree(const edge *tree, unsigned int n)
{
unsigned int e;
for (e = 0; e < n; e++) {
printf("(%u, %u) ", tree[e].first, tree[e].second);
}
putchar('\n');
}

int main(void)
{
const unsigned int v = 5;
const unsigned int n = triangular_number(v - 1);
edge *edges;

edges = complete_graph(v);
if (edges == NULL) {
return 1;
}
spanning_trees(edges, n, v, print_tree);
free(edges);

return 0;
}


Here is the output. There are 125 spanning trees of the complete graph on 5 vertices:

(0, 1) (0, 2) (0, 3) (0, 4)
(0, 1) (0, 2) (0, 3) (1, 4)
(0, 1) (0, 2) (0, 3) (2, 4)
(0, 1) (0, 2) (0, 3) (3, 4)
(0, 1) (0, 2) (0, 4) (1, 3)
(0, 1) (0, 2) (0, 4) (2, 3)
(0, 1) (0, 2) (0, 4) (3, 4)
(0, 1) (0, 2) (1, 3) (1, 4)
(0, 1) (0, 2) (1, 3) (2, 4)
(0, 1) (0, 2) (1, 3) (3, 4)
(0, 1) (0, 2) (1, 4) (2, 3)
(0, 1) (0, 2) (1, 4) (3, 4)
(0, 1) (0, 2) (2, 3) (2, 4)
(0, 1) (0, 2) (2, 3) (3, 4)
(0, 1) (0, 2) (2, 4) (3, 4)
(0, 1) (0, 3) (0, 4) (1, 2)
(0, 1) (0, 3) (0, 4) (2, 3)
(0, 1) (0, 3) (0, 4) (2, 4)
(0, 1) (0, 3) (1, 2) (1, 4)
(0, 1) (0, 3) (1, 2) (2, 4)
(0, 1) (0, 3) (1, 2) (3, 4)
(0, 1) (0, 3) (1, 4) (2, 3)
(0, 1) (0, 3) (1, 4) (2, 4)
(0, 1) (0, 3) (2, 3) (2, 4)
(0, 1) (0, 3) (2, 3) (3, 4)
(0, 1) (0, 3) (2, 4) (3, 4)
(0, 1) (0, 4) (1, 2) (1, 3)
(0, 1) (0, 4) (1, 2) (2, 3)
(0, 1) (0, 4) (1, 2) (3, 4)
(0, 1) (0, 4) (1, 3) (2, 3)
(0, 1) (0, 4) (1, 3) (2, 4)
(0, 1) (0, 4) (2, 3) (2, 4)
(0, 1) (0, 4) (2, 3) (3, 4)
(0, 1) (0, 4) (2, 4) (3, 4)
(0, 1) (1, 2) (1, 3) (1, 4)
(0, 1) (1, 2) (1, 3) (2, 4)
(0, 1) (1, 2) (1, 3) (3, 4)
(0, 1) (1, 2) (1, 4) (2, 3)
(0, 1) (1, 2) (1, 4) (3, 4)
(0, 1) (1, 2) (2, 3) (2, 4)
(0, 1) (1, 2) (2, 3) (3, 4)
(0, 1) (1, 2) (2, 4) (3, 4)
(0, 1) (1, 3) (1, 4) (2, 3)
(0, 1) (1, 3) (1, 4) (2, 4)
(0, 1) (1, 3) (2, 3) (2, 4)
(0, 1) (1, 3) (2, 3) (3, 4)
(0, 1) (1, 3) (2, 4) (3, 4)
(0, 1) (1, 4) (2, 3) (2, 4)
(0, 1) (1, 4) (2, 3) (3, 4)
(0, 1) (1, 4) (2, 4) (3, 4)
(0, 2) (0, 3) (0, 4) (1, 2)
(0, 2) (0, 3) (0, 4) (1, 3)
(0, 2) (0, 3) (0, 4) (1, 4)
(0, 2) (0, 3) (1, 2) (1, 4)
(0, 2) (0, 3) (1, 2) (2, 4)
(0, 2) (0, 3) (1, 2) (3, 4)
(0, 2) (0, 3) (1, 3) (1, 4)
(0, 2) (0, 3) (1, 3) (2, 4)
(0, 2) (0, 3) (1, 3) (3, 4)
(0, 2) (0, 3) (1, 4) (2, 4)
(0, 2) (0, 3) (1, 4) (3, 4)
(0, 2) (0, 4) (1, 2) (1, 3)
(0, 2) (0, 4) (1, 2) (2, 3)
(0, 2) (0, 4) (1, 2) (3, 4)
(0, 2) (0, 4) (1, 3) (1, 4)
(0, 2) (0, 4) (1, 3) (2, 3)
(0, 2) (0, 4) (1, 3) (3, 4)
(0, 2) (0, 4) (1, 4) (2, 3)
(0, 2) (0, 4) (1, 4) (3, 4)
(0, 2) (1, 2) (1, 3) (1, 4)
(0, 2) (1, 2) (1, 3) (2, 4)
(0, 2) (1, 2) (1, 3) (3, 4)
(0, 2) (1, 2) (1, 4) (2, 3)
(0, 2) (1, 2) (1, 4) (3, 4)
(0, 2) (1, 2) (2, 3) (2, 4)
(0, 2) (1, 2) (2, 3) (3, 4)
(0, 2) (1, 2) (2, 4) (3, 4)
(0, 2) (1, 3) (1, 4) (2, 3)
(0, 2) (1, 3) (1, 4) (2, 4)
(0, 2) (1, 3) (2, 3) (2, 4)
(0, 2) (1, 3) (2, 3) (3, 4)
(0, 2) (1, 3) (2, 4) (3, 4)
(0, 2) (1, 4) (2, 3) (2, 4)
(0, 2) (1, 4) (2, 3) (3, 4)
(0, 2) (1, 4) (2, 4) (3, 4)
(0, 3) (0, 4) (1, 2) (1, 3)
(0, 3) (0, 4) (1, 2) (1, 4)
(0, 3) (0, 4) (1, 2) (2, 3)
(0, 3) (0, 4) (1, 2) (2, 4)
(0, 3) (0, 4) (1, 3) (2, 3)
(0, 3) (0, 4) (1, 3) (2, 4)
(0, 3) (0, 4) (1, 4) (2, 3)
(0, 3) (0, 4) (1, 4) (2, 4)
(0, 3) (1, 2) (1, 3) (1, 4)
(0, 3) (1, 2) (1, 3) (2, 4)
(0, 3) (1, 2) (1, 3) (3, 4)
(0, 3) (1, 2) (1, 4) (2, 3)
(0, 3) (1, 2) (1, 4) (3, 4)
(0, 3) (1, 2) (2, 3) (2, 4)
(0, 3) (1, 2) (2, 3) (3, 4)
(0, 3) (1, 2) (2, 4) (3, 4)
(0, 3) (1, 3) (1, 4) (2, 3)
(0, 3) (1, 3) (1, 4) (2, 4)
(0, 3) (1, 3) (2, 3) (2, 4)
(0, 3) (1, 3) (2, 3) (3, 4)
(0, 3) (1, 3) (2, 4) (3, 4)
(0, 3) (1, 4) (2, 3) (2, 4)
(0, 3) (1, 4) (2, 3) (3, 4)
(0, 3) (1, 4) (2, 4) (3, 4)
(0, 4) (1, 2) (1, 3) (1, 4)
(0, 4) (1, 2) (1, 3) (2, 4)
(0, 4) (1, 2) (1, 3) (3, 4)
(0, 4) (1, 2) (1, 4) (2, 3)
(0, 4) (1, 2) (1, 4) (3, 4)
(0, 4) (1, 2) (2, 3) (2, 4)
(0, 4) (1, 2) (2, 3) (3, 4)
(0, 4) (1, 2) (2, 4) (3, 4)
(0, 4) (1, 3) (1, 4) (2, 3)
(0, 4) (1, 3) (1, 4) (2, 4)
(0, 4) (1, 3) (2, 3) (2, 4)
(0, 4) (1, 3) (2, 3) (3, 4)
(0, 4) (1, 3) (2, 4) (3, 4)
(0, 4) (1, 4) (2, 3) (2, 4)
(0, 4) (1, 4) (2, 3) (3, 4)
(0, 4) (1, 4) (2, 4) (3, 4)


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).

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) {
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;
}


#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.

Euler circuits using backtracking in C

An Euler circuit on a graph is a tour that traverses every edge before returning to its starting point (compare to a Hamiltonian circuit, which visits every vertex). An Euler circuit may visit vertices more than once.

This is a backtracking algorithm to find all Euler circuits of a graph. It takes the graph in the form of an array of edges, and a user-specified callback, which it calls for every circuit found.

In order to extend a partial circuit with a new edge, the algorithm needs to check that the new edge:

1. Isn’t in the circuit already
2. Contains the terminal vertex of the partial circuit as one of its endpoints

In order to facilitate (2), the algorithm keeps track of the terminal vertex of the partial circuit.

The first edge of every circuit is fixed at edge 0, and the first terminal vertex is its second vertex. These two normalisation conditions ensure that no duplicate circuits are generated.

#include <stdlib.h>

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

static unsigned int circuit_contains(const unsigned int *circuit, unsigned int c, unsigned int e)
{
unsigned int i;
unsigned int contains = 0;
for (i = 0; i < c && !contains; i++) {
contains = circuit[i] == e;
}
return contains;
}

typedef void (*circuitfn)(const edge *, unsigned int, const unsigned int *);

static void euler_circuits_recursive(const edge *edges, unsigned int n, unsigned int *circuit,
unsigned int c, unsigned int tv, circuitfn fun)
{
if (c == n) {
/* Found a circuit */
fun(edges, n, circuit);
}
else {
unsigned int e;
for (e = 1; e < n; e++) {
if (!circuit_contains(circuit, c, e)
&& (edges[e].first == tv || edges[e].second == tv))
{
circuit[ c] = e;
euler_circuits_recursive(edges, n, circuit, c + 1,
edges[e].first == tv ? edges[e].second : edges[e].first,
fun);
}
}
}
}

void euler_circuits(const edge *edges, unsigned int n, circuitfn fun)
{
unsigned int *circuit;
circuit = malloc(n * sizeof(unsigned int));
if (circuit == NULL) {
return;
}
circuit[0] = 0;
euler_circuits_recursive(edges, n, circuit, 1, edges[0].second, fun);
free(circuit);
}


Here is an example program that finds all of the Euler circuits on the complete graph of order 5:

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

/* Calculate the nth triangular number T(n) */
unsigned int triangular_number(unsigned int n)
{
return (n * (n + 1)) / 2;
}

/* Construct a complete graph on v vertices */
edge *complete_graph(unsigned int v)
{
const unsigned int n = triangular_number(v - 1);
unsigned int i, j, k;
edge *edges = malloc(n * sizeof(edge));
if (edges != NULL) {
for (i = 0, k = 0; i < v - 1; i++) {
for (j = i + 1; j < v; j++) {
edges[k].first = i;
edges[k].second = j;
k++;
}
}
}
return edges;
}

/* Print the edges in a circuit */
static void print_circuit(const edge *edges, unsigned int n, const unsigned int *circuit)
{
unsigned int e;
for (e = 0; e < n; e++) {
printf("(%u, %u) ", edges[circuit[e]].first, edges[circuit[e]].second);
}
putchar('\n');
}

int main(void)
{
const unsigned int v = 5;
const unsigned int n = triangular_number(v - 1);
edge *edges;

edges = complete_graph(v);
if (edges == NULL) {
return 1;
}
euler_circuits(edges, n, print_circuit);
free(edges);

return 0;
}


Here is the output. There are 132 Euler circuits on the complete graph of order 5:

(0, 1) (1, 2) (0, 2) (0, 3) (1, 3) (1, 4) (2, 4) (2, 3) (3, 4) (0, 4)
(0, 1) (1, 2) (0, 2) (0, 3) (1, 3) (1, 4) (3, 4) (2, 3) (2, 4) (0, 4)
(0, 1) (1, 2) (0, 2) (0, 3) (2, 3) (2, 4) (1, 4) (1, 3) (3, 4) (0, 4)
(0, 1) (1, 2) (0, 2) (0, 3) (2, 3) (2, 4) (3, 4) (1, 3) (1, 4) (0, 4)
(0, 1) (1, 2) (0, 2) (0, 3) (3, 4) (1, 4) (1, 3) (2, 3) (2, 4) (0, 4)
(0, 1) (1, 2) (0, 2) (0, 3) (3, 4) (2, 4) (2, 3) (1, 3) (1, 4) (0, 4)
(0, 1) (1, 2) (0, 2) (0, 4) (1, 4) (1, 3) (2, 3) (2, 4) (3, 4) (0, 3)
(0, 1) (1, 2) (0, 2) (0, 4) (1, 4) (1, 3) (3, 4) (2, 4) (2, 3) (0, 3)
(0, 1) (1, 2) (0, 2) (0, 4) (2, 4) (2, 3) (1, 3) (1, 4) (3, 4) (0, 3)
(0, 1) (1, 2) (0, 2) (0, 4) (2, 4) (2, 3) (3, 4) (1, 4) (1, 3) (0, 3)
(0, 1) (1, 2) (0, 2) (0, 4) (3, 4) (1, 3) (1, 4) (2, 4) (2, 3) (0, 3)
(0, 1) (1, 2) (0, 2) (0, 4) (3, 4) (2, 3) (2, 4) (1, 4) (1, 3) (0, 3)
(0, 1) (1, 2) (2, 3) (0, 3) (0, 2) (2, 4) (1, 4) (1, 3) (3, 4) (0, 4)
(0, 1) (1, 2) (2, 3) (0, 3) (0, 2) (2, 4) (3, 4) (1, 3) (1, 4) (0, 4)
(0, 1) (1, 2) (2, 3) (0, 3) (0, 4) (1, 4) (1, 3) (3, 4) (2, 4) (0, 2)
(0, 1) (1, 2) (2, 3) (0, 3) (0, 4) (3, 4) (1, 3) (1, 4) (2, 4) (0, 2)
(0, 1) (1, 2) (2, 3) (1, 3) (1, 4) (0, 4) (0, 2) (2, 4) (3, 4) (0, 3)
(0, 1) (1, 2) (2, 3) (1, 3) (1, 4) (0, 4) (0, 3) (3, 4) (2, 4) (0, 2)
(0, 1) (1, 2) (2, 3) (1, 3) (1, 4) (2, 4) (0, 2) (0, 3) (3, 4) (0, 4)
(0, 1) (1, 2) (2, 3) (1, 3) (1, 4) (2, 4) (0, 2) (0, 4) (3, 4) (0, 3)
(0, 1) (1, 2) (2, 3) (1, 3) (1, 4) (3, 4) (0, 3) (0, 2) (2, 4) (0, 4)
(0, 1) (1, 2) (2, 3) (1, 3) (1, 4) (3, 4) (0, 3) (0, 4) (2, 4) (0, 2)
(0, 1) (1, 2) (2, 3) (3, 4) (0, 4) (0, 2) (2, 4) (1, 4) (1, 3) (0, 3)
(0, 1) (1, 2) (2, 3) (3, 4) (0, 4) (0, 3) (1, 3) (1, 4) (2, 4) (0, 2)
(0, 1) (1, 2) (2, 3) (3, 4) (1, 4) (1, 3) (0, 3) (0, 2) (2, 4) (0, 4)
(0, 1) (1, 2) (2, 3) (3, 4) (1, 4) (1, 3) (0, 3) (0, 4) (2, 4) (0, 2)
(0, 1) (1, 2) (2, 3) (3, 4) (2, 4) (0, 2) (0, 3) (1, 3) (1, 4) (0, 4)
(0, 1) (1, 2) (2, 3) (3, 4) (2, 4) (0, 2) (0, 4) (1, 4) (1, 3) (0, 3)
(0, 1) (1, 2) (2, 4) (0, 4) (0, 2) (2, 3) (1, 3) (1, 4) (3, 4) (0, 3)
(0, 1) (1, 2) (2, 4) (0, 4) (0, 2) (2, 3) (3, 4) (1, 4) (1, 3) (0, 3)
(0, 1) (1, 2) (2, 4) (0, 4) (0, 3) (1, 3) (1, 4) (3, 4) (2, 3) (0, 2)
(0, 1) (1, 2) (2, 4) (0, 4) (0, 3) (3, 4) (1, 4) (1, 3) (2, 3) (0, 2)
(0, 1) (1, 2) (2, 4) (1, 4) (1, 3) (0, 3) (0, 2) (2, 3) (3, 4) (0, 4)
(0, 1) (1, 2) (2, 4) (1, 4) (1, 3) (0, 3) (0, 4) (3, 4) (2, 3) (0, 2)
(0, 1) (1, 2) (2, 4) (1, 4) (1, 3) (2, 3) (0, 2) (0, 3) (3, 4) (0, 4)
(0, 1) (1, 2) (2, 4) (1, 4) (1, 3) (2, 3) (0, 2) (0, 4) (3, 4) (0, 3)
(0, 1) (1, 2) (2, 4) (1, 4) (1, 3) (3, 4) (0, 4) (0, 2) (2, 3) (0, 3)
(0, 1) (1, 2) (2, 4) (1, 4) (1, 3) (3, 4) (0, 4) (0, 3) (2, 3) (0, 2)
(0, 1) (1, 2) (2, 4) (3, 4) (0, 3) (0, 2) (2, 3) (1, 3) (1, 4) (0, 4)
(0, 1) (1, 2) (2, 4) (3, 4) (0, 3) (0, 4) (1, 4) (1, 3) (2, 3) (0, 2)
(0, 1) (1, 2) (2, 4) (3, 4) (1, 3) (1, 4) (0, 4) (0, 2) (2, 3) (0, 3)
(0, 1) (1, 2) (2, 4) (3, 4) (1, 3) (1, 4) (0, 4) (0, 3) (2, 3) (0, 2)
(0, 1) (1, 2) (2, 4) (3, 4) (2, 3) (0, 2) (0, 3) (1, 3) (1, 4) (0, 4)
(0, 1) (1, 2) (2, 4) (3, 4) (2, 3) (0, 2) (0, 4) (1, 4) (1, 3) (0, 3)
(0, 1) (1, 3) (0, 3) (0, 2) (1, 2) (1, 4) (2, 4) (2, 3) (3, 4) (0, 4)
(0, 1) (1, 3) (0, 3) (0, 2) (1, 2) (1, 4) (3, 4) (2, 3) (2, 4) (0, 4)
(0, 1) (1, 3) (0, 3) (0, 2) (2, 3) (3, 4) (1, 4) (1, 2) (2, 4) (0, 4)
(0, 1) (1, 3) (0, 3) (0, 2) (2, 3) (3, 4) (2, 4) (1, 2) (1, 4) (0, 4)
(0, 1) (1, 3) (0, 3) (0, 2) (2, 4) (1, 4) (1, 2) (2, 3) (3, 4) (0, 4)
(0, 1) (1, 3) (0, 3) (0, 2) (2, 4) (3, 4) (2, 3) (1, 2) (1, 4) (0, 4)
(0, 1) (1, 3) (0, 3) (0, 4) (1, 4) (1, 2) (2, 3) (3, 4) (2, 4) (0, 2)
(0, 1) (1, 3) (0, 3) (0, 4) (1, 4) (1, 2) (2, 4) (3, 4) (2, 3) (0, 2)
(0, 1) (1, 3) (0, 3) (0, 4) (2, 4) (1, 2) (1, 4) (3, 4) (2, 3) (0, 2)
(0, 1) (1, 3) (0, 3) (0, 4) (2, 4) (2, 3) (3, 4) (1, 4) (1, 2) (0, 2)
(0, 1) (1, 3) (0, 3) (0, 4) (3, 4) (2, 3) (1, 2) (1, 4) (2, 4) (0, 2)
(0, 1) (1, 3) (0, 3) (0, 4) (3, 4) (2, 3) (2, 4) (1, 4) (1, 2) (0, 2)
(0, 1) (1, 3) (2, 3) (0, 2) (0, 3) (3, 4) (1, 4) (1, 2) (2, 4) (0, 4)
(0, 1) (1, 3) (2, 3) (0, 2) (0, 3) (3, 4) (2, 4) (1, 2) (1, 4) (0, 4)
(0, 1) (1, 3) (2, 3) (0, 2) (0, 4) (1, 4) (1, 2) (2, 4) (3, 4) (0, 3)
(0, 1) (1, 3) (2, 3) (0, 2) (0, 4) (2, 4) (1, 2) (1, 4) (3, 4) (0, 3)
(0, 1) (1, 3) (2, 3) (1, 2) (1, 4) (0, 4) (0, 2) (2, 4) (3, 4) (0, 3)
(0, 1) (1, 3) (2, 3) (1, 2) (1, 4) (0, 4) (0, 3) (3, 4) (2, 4) (0, 2)
(0, 1) (1, 3) (2, 3) (1, 2) (1, 4) (2, 4) (0, 2) (0, 3) (3, 4) (0, 4)
(0, 1) (1, 3) (2, 3) (1, 2) (1, 4) (2, 4) (0, 2) (0, 4) (3, 4) (0, 3)
(0, 1) (1, 3) (2, 3) (1, 2) (1, 4) (3, 4) (0, 3) (0, 2) (2, 4) (0, 4)
(0, 1) (1, 3) (2, 3) (1, 2) (1, 4) (3, 4) (0, 3) (0, 4) (2, 4) (0, 2)
(0, 1) (1, 3) (2, 3) (2, 4) (0, 4) (0, 2) (1, 2) (1, 4) (3, 4) (0, 3)
(0, 1) (1, 3) (2, 3) (2, 4) (0, 4) (0, 3) (3, 4) (1, 4) (1, 2) (0, 2)
(0, 1) (1, 3) (2, 3) (2, 4) (1, 4) (1, 2) (0, 2) (0, 3) (3, 4) (0, 4)
(0, 1) (1, 3) (2, 3) (2, 4) (1, 4) (1, 2) (0, 2) (0, 4) (3, 4) (0, 3)
(0, 1) (1, 3) (2, 3) (2, 4) (3, 4) (0, 3) (0, 2) (1, 2) (1, 4) (0, 4)
(0, 1) (1, 3) (2, 3) (2, 4) (3, 4) (0, 3) (0, 4) (1, 4) (1, 2) (0, 2)
(0, 1) (1, 3) (3, 4) (0, 4) (0, 2) (1, 2) (1, 4) (2, 4) (2, 3) (0, 3)
(0, 1) (1, 3) (3, 4) (0, 4) (0, 2) (2, 4) (1, 4) (1, 2) (2, 3) (0, 3)
(0, 1) (1, 3) (3, 4) (0, 4) (0, 3) (2, 3) (1, 2) (1, 4) (2, 4) (0, 2)
(0, 1) (1, 3) (3, 4) (0, 4) (0, 3) (2, 3) (2, 4) (1, 4) (1, 2) (0, 2)
(0, 1) (1, 3) (3, 4) (1, 4) (1, 2) (0, 2) (0, 3) (2, 3) (2, 4) (0, 4)
(0, 1) (1, 3) (3, 4) (1, 4) (1, 2) (0, 2) (0, 4) (2, 4) (2, 3) (0, 3)
(0, 1) (1, 3) (3, 4) (1, 4) (1, 2) (2, 3) (0, 3) (0, 2) (2, 4) (0, 4)
(0, 1) (1, 3) (3, 4) (1, 4) (1, 2) (2, 3) (0, 3) (0, 4) (2, 4) (0, 2)
(0, 1) (1, 3) (3, 4) (1, 4) (1, 2) (2, 4) (0, 4) (0, 2) (2, 3) (0, 3)
(0, 1) (1, 3) (3, 4) (1, 4) (1, 2) (2, 4) (0, 4) (0, 3) (2, 3) (0, 2)
(0, 1) (1, 3) (3, 4) (2, 4) (0, 2) (0, 3) (2, 3) (1, 2) (1, 4) (0, 4)
(0, 1) (1, 3) (3, 4) (2, 4) (0, 2) (0, 4) (1, 4) (1, 2) (2, 3) (0, 3)
(0, 1) (1, 3) (3, 4) (2, 4) (1, 2) (1, 4) (0, 4) (0, 2) (2, 3) (0, 3)
(0, 1) (1, 3) (3, 4) (2, 4) (1, 2) (1, 4) (0, 4) (0, 3) (2, 3) (0, 2)
(0, 1) (1, 3) (3, 4) (2, 4) (2, 3) (0, 3) (0, 2) (1, 2) (1, 4) (0, 4)
(0, 1) (1, 3) (3, 4) (2, 4) (2, 3) (0, 3) (0, 4) (1, 4) (1, 2) (0, 2)
(0, 1) (1, 4) (0, 4) (0, 2) (1, 2) (1, 3) (2, 3) (2, 4) (3, 4) (0, 3)
(0, 1) (1, 4) (0, 4) (0, 2) (1, 2) (1, 3) (3, 4) (2, 4) (2, 3) (0, 3)
(0, 1) (1, 4) (0, 4) (0, 2) (2, 3) (1, 3) (1, 2) (2, 4) (3, 4) (0, 3)
(0, 1) (1, 4) (0, 4) (0, 2) (2, 3) (3, 4) (2, 4) (1, 2) (1, 3) (0, 3)
(0, 1) (1, 4) (0, 4) (0, 2) (2, 4) (3, 4) (1, 3) (1, 2) (2, 3) (0, 3)
(0, 1) (1, 4) (0, 4) (0, 2) (2, 4) (3, 4) (2, 3) (1, 2) (1, 3) (0, 3)
(0, 1) (1, 4) (0, 4) (0, 3) (1, 3) (1, 2) (2, 3) (3, 4) (2, 4) (0, 2)
(0, 1) (1, 4) (0, 4) (0, 3) (1, 3) (1, 2) (2, 4) (3, 4) (2, 3) (0, 2)
(0, 1) (1, 4) (0, 4) (0, 3) (2, 3) (1, 2) (1, 3) (3, 4) (2, 4) (0, 2)
(0, 1) (1, 4) (0, 4) (0, 3) (2, 3) (2, 4) (3, 4) (1, 3) (1, 2) (0, 2)
(0, 1) (1, 4) (0, 4) (0, 3) (3, 4) (2, 4) (1, 2) (1, 3) (2, 3) (0, 2)
(0, 1) (1, 4) (0, 4) (0, 3) (3, 4) (2, 4) (2, 3) (1, 3) (1, 2) (0, 2)
(0, 1) (1, 4) (2, 4) (0, 2) (0, 3) (1, 3) (1, 2) (2, 3) (3, 4) (0, 4)
(0, 1) (1, 4) (2, 4) (0, 2) (0, 3) (2, 3) (1, 2) (1, 3) (3, 4) (0, 4)
(0, 1) (1, 4) (2, 4) (0, 2) (0, 4) (3, 4) (1, 3) (1, 2) (2, 3) (0, 3)
(0, 1) (1, 4) (2, 4) (0, 2) (0, 4) (3, 4) (2, 3) (1, 2) (1, 3) (0, 3)
(0, 1) (1, 4) (2, 4) (1, 2) (1, 3) (0, 3) (0, 2) (2, 3) (3, 4) (0, 4)
(0, 1) (1, 4) (2, 4) (1, 2) (1, 3) (0, 3) (0, 4) (3, 4) (2, 3) (0, 2)
(0, 1) (1, 4) (2, 4) (1, 2) (1, 3) (2, 3) (0, 2) (0, 3) (3, 4) (0, 4)
(0, 1) (1, 4) (2, 4) (1, 2) (1, 3) (2, 3) (0, 2) (0, 4) (3, 4) (0, 3)
(0, 1) (1, 4) (2, 4) (1, 2) (1, 3) (3, 4) (0, 4) (0, 2) (2, 3) (0, 3)
(0, 1) (1, 4) (2, 4) (1, 2) (1, 3) (3, 4) (0, 4) (0, 3) (2, 3) (0, 2)
(0, 1) (1, 4) (2, 4) (2, 3) (0, 3) (0, 2) (1, 2) (1, 3) (3, 4) (0, 4)
(0, 1) (1, 4) (2, 4) (2, 3) (0, 3) (0, 4) (3, 4) (1, 3) (1, 2) (0, 2)
(0, 1) (1, 4) (2, 4) (2, 3) (1, 3) (1, 2) (0, 2) (0, 3) (3, 4) (0, 4)
(0, 1) (1, 4) (2, 4) (2, 3) (1, 3) (1, 2) (0, 2) (0, 4) (3, 4) (0, 3)
(0, 1) (1, 4) (2, 4) (2, 3) (3, 4) (0, 4) (0, 2) (1, 2) (1, 3) (0, 3)
(0, 1) (1, 4) (2, 4) (2, 3) (3, 4) (0, 4) (0, 3) (1, 3) (1, 2) (0, 2)
(0, 1) (1, 4) (3, 4) (0, 3) (0, 2) (1, 2) (1, 3) (2, 3) (2, 4) (0, 4)
(0, 1) (1, 4) (3, 4) (0, 3) (0, 2) (2, 3) (1, 3) (1, 2) (2, 4) (0, 4)
(0, 1) (1, 4) (3, 4) (0, 3) (0, 4) (2, 4) (1, 2) (1, 3) (2, 3) (0, 2)
(0, 1) (1, 4) (3, 4) (0, 3) (0, 4) (2, 4) (2, 3) (1, 3) (1, 2) (0, 2)
(0, 1) (1, 4) (3, 4) (1, 3) (1, 2) (0, 2) (0, 3) (2, 3) (2, 4) (0, 4)
(0, 1) (1, 4) (3, 4) (1, 3) (1, 2) (0, 2) (0, 4) (2, 4) (2, 3) (0, 3)
(0, 1) (1, 4) (3, 4) (1, 3) (1, 2) (2, 3) (0, 3) (0, 2) (2, 4) (0, 4)
(0, 1) (1, 4) (3, 4) (1, 3) (1, 2) (2, 3) (0, 3) (0, 4) (2, 4) (0, 2)
(0, 1) (1, 4) (3, 4) (1, 3) (1, 2) (2, 4) (0, 4) (0, 2) (2, 3) (0, 3)
(0, 1) (1, 4) (3, 4) (1, 3) (1, 2) (2, 4) (0, 4) (0, 3) (2, 3) (0, 2)
(0, 1) (1, 4) (3, 4) (2, 3) (0, 2) (0, 3) (1, 3) (1, 2) (2, 4) (0, 4)
(0, 1) (1, 4) (3, 4) (2, 3) (0, 2) (0, 4) (2, 4) (1, 2) (1, 3) (0, 3)
(0, 1) (1, 4) (3, 4) (2, 3) (1, 2) (1, 3) (0, 3) (0, 2) (2, 4) (0, 4)
(0, 1) (1, 4) (3, 4) (2, 3) (1, 2) (1, 3) (0, 3) (0, 4) (2, 4) (0, 2)
(0, 1) (1, 4) (3, 4) (2, 3) (2, 4) (0, 4) (0, 2) (1, 2) (1, 3) (0, 3)
(0, 1) (1, 4) (3, 4) (2, 3) (2, 4) (0, 4) (0, 3) (1, 3) (1, 2) (0, 2)


Hamiltonian circuits using backtracking in C

A Hamiltonian circuit of a graph is a tour that visits every vertex once, and ends at its starting vertex. Finding out if a graph has a Hamiltonian circuit is an NP-complete problem.

This is a backtracking algorithm to find all of the Hamiltonian circuits in a graph. The input is an adjacency matrix, and it calls a user-specified callback with an array containing the order of vertices for each Hamiltonian circuit it finds.

The first vertex for all circuits is fixed at 0, and the last vertex is limited to being less than the second vertex. These are normalisation conditions that prevent duplicates that are cyclic permutations or reversals respectively.

#include <stdlib.h>

static unsigned int circuit_contains(const unsigned int *circuit, unsigned int c, unsigned int v)
{
unsigned int i;
unsigned int contains = 0;
for (i = 0; i < c && !contains; i++) {
contains = circuit[i] == v;
}
return contains;
}

typedef void (*circuitfn)(const unsigned int *, size_t);

static void hamiltonian_circuits_recursive(unsigned int **adjmat, size_t n, unsigned int *circuit,
unsigned int c, circuitfn fun)
{
if (c == n) {
/* Found a circuit */
fun(circuit, n);
}
else {
unsigned int v;
for (v = 1; v < n; v++) {
if (!circuit_contains(circuit, c, v) /* Vertex is not in the circuit already */
&& adjmat[circuit[ c - 1]][v] == 1 /* Vertex is adjacent to the previous vertex */
&& (c < n - 1 || (adjmat[0][v] == 1 /* Last vertex is adjacent to the first */
&& v < circuit[1]))) /* Last vertex is less than the second */
{
circuit[ c] = v;
hamiltonian_circuits_recursive(adjmat, n, circuit, c + 1, fun);
}
}
}
}

void hamiltonian_circuits(unsigned int **adjmat, size_t n, circuitfn fun)
{
unsigned int *circuit;
circuit = malloc(n * sizeof(unsigned int));
if (circuit == NULL) {
return;
}
circuit[0] = 0;
free(circuit);
}


This is an example program that finds all Hamiltonian circuits on the complete graph of order 5. With the constraints on cyclic permutations and direction mentioned above, there are $$(n – 1)!/2$$ Hamiltonian circuits on a complete graph of order $$n$$.

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

static void print_circuit(const unsigned int *circuit, size_t len)
{
unsigned int v;
for (v = 0; v < len; v++) {
printf("%d ", circuit[v]);
}
putchar('\n');
}

int main(void)
{
const size_t n = 5;
unsigned int i, j;

/* Create a complete graph on 5 vertices */
adjmat = malloc(n * sizeof(unsigned int *));
for (i = 0; i < n; i++) {
adjmat[i] = malloc(n * sizeof(unsigned int));
for (j = 0; j < n; j++) {
}
}

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

return 0;
}


Here is the output. Notice there are $$(5 – 1)!/2 = 12$$ circuits:

0 2 3 4 1
0 2 4 3 1
0 3 1 4 2
0 3 2 4 1
0 3 4 1 2
0 3 4 2 1
0 4 1 2 3
0 4 1 3 2
0 4 2 1 3
0 4 2 3 1
0 4 3 1 2
0 4 3 2 1


Vertex colouring with backtracking in C

The vertex colouring problem is to colour the vertices of a graph in such a way that no two adjacent vertices are the same colour. The decision problem of whether a graph can be coloured in m or fewer colours is NP-complete.

Although the problem is intractable, a bactracking algorithm can be used to reduce the number of colourings that need to be tried. The algorithm works by colouring the vertices one at a time, and backtracking if at any point it becomes impossible to colour the next vertex differently from all of its neighbours.

typedef void(*vertex_colouringfn)(const unsigned int *, size_t);

static unsigned int promising(int i, const unsigned int **adjmat, const unsigned int *colours)
{
int j;
unsigned int ok = 1;

for (j = 0; j < i && ok; j++) {
if (adjmat[i][j] && colours[i] == colours[j]) {
/* Adjacent vertex is the same colour */
ok = 0;
}
}
return ok;
}

static void vertex_colouring_recursive(int i, const unsigned int **adjmat, size_t len,
unsigned int *colours, unsigned int m, vertex_colouringfn fun)
{
unsigned int colour;

if (i == len - 1) {
/* Coloured every vertex successfully */
fun(colours, len);
}
else if (i < (int)len - 1) {
/* Try every colour for the next vertex */
for (colour = 0; colour < m; colour++) {
colours[i + 1] = colour;
vertex_colouring_recursive(i + 1, adjmat, len, colours, m, fun);
}
}
}
}

void vertex_colouring(const unsigned int **adjmat, size_t len, unsigned int m,
vertex_colouringfn fun)
{
unsigned int *colours = calloc(len, sizeof(unsigned int));
if (colours == NULL) {
return;
}
vertex_colouring_recursive(-1, adjmat, len, colours, m, fun);
free(colours);
}


This is an example program with a small graph and m = 3:

static void print_colouring(const unsigned int *colours, size_t len)
{
unsigned int i;
for (i = 0; i < len; i++) {
printf("%d ", colours[i]);
}
printf("\n");
}

int main(void)
{
unsigned int v0[] = {0, 1, 1, 1, 0};
unsigned int v1[] = {1, 0, 1, 0, 1};
unsigned int v2[] = {1, 1, 0, 1, 1};
unsigned int v3[] = {1, 0, 1, 0, 1};
unsigned int v4[] = {0, 1, 1, 1, 0};
const unsigned int *adjmat[] = {v0, v1, v2, v3, v4};
const size_t len = sizeof(adjmat) / sizeof(unsigned int*);
const unsigned int m = 3; /* Number of colours */
return 0;
}


Graph data structures

Introduction

In this post, I introduce the concept of a graph and describe some ways of representing graphs in C.

Definitions

Graphs, vertices and edges

A graph is a collection of nodes called vertices, and the connections between them, called edges.

Undirected and directed graphs

When the edges in a graph have a direction, the graph is called a directed graph or digraph, and the edges are called directed edges or arcs.
Here, I shall be exclusively concerned with directed graphs, and so when I refer to an edge, I mean a directed edge.
This is not a limitation, since an undirected graph can easily be implemented as a directed graph by adding edges between connected vertices in both directions.

A representation can often be simplified if it is only being used for undirected graphs, and I’ll mention in passing how this can be achieved.

A vertex that is the end-point of an edge is called a neighbour of the vertex that is its starting-point.
The first vertex is said to be adjacent to the second.

An example

The following diagram shows a graph with 5 vertices and 7 edges.
The edges between A and D and B and C are pairs that make a bidirectional connection, represented here by a double-headed arrow.

Mathematical definition

More formally, a graph is an ordered pair, G = <V, A>, where V is the set of vertices, and A, the set of arcs, is itself a set of ordered pairs of vertices.

For example, the following expressions describe the graph shown above in set-theoretic language:

V = {A, B, C, D, E}
A = {<A, B>, <A, D>, <B, C>, <C, B>, <D, A>, <D, C>, <D, E>}


Functions

A graph implementation needs a basic set of functions to assemble and modify graphs, and to enumerate vertices, edges and neighbours.

The following functions are provided by each representation.
These are the declarations for the intuitive representation, graph1:

graph1 *graph1_create(void);
Create an empty graph
void graph1_delete(graph1 *graph);
Delete a graph
vertex *graph1_add(graph1 *graph, const char *name, void *data);
Add a vertex to the graph with a name, and optionally some data
vertex *graph1_get_vertex(const graph1 *graph, const char *name);
Retrieve a vertex by name
void *graph1_remove(graph1 *graph, vertex *vertex);
Remove a vertex
void graph1_add_edge(graph1 *graph, vertex *vertex1, vertex *vertex2);
Create a directed edge between vertex1 and vertex2
void graph1_remove_edge(graph1 *graph, vertex *vertex1, vertex *vertex2);
Remove the directed edge from vertex1 to vertex2
unsigned int graph1_get_adjacent(const graph1 *graph, const vertex *vertex1, const vertex *vertex2);
Determine if there is an edge from vertex1 to vertex2
iterator *graph1_get_neighbours(const graph1 *graph, const vertex *vertex);
Get the neighbours of a vertex
iterator *graph1_get_edges(const graph1 *graph);
Get all of the edges in the graph
iterator *graph1_get_vertices(const graph1 *graph);
Get all of the vertices in the graph
unsigned int graph1_get_neighbour_count(const graph1 *graph, const vertex *vertex);
Get the count of neighbours of a vertex
unsigned int graph1_get_edge_count(const graph1 *graph);
Get the count of edges in the graph
unsigned int graph1_get_vertex_count(const graph1 *graph);
Get the count of vertices in the graph

Representation of vertices and edges

Vertices

All of the graph representations use the following definition of a vertex:

typedef struct {
char *name;
void *data;
void *body;
deletefn del;
} vertex;


Note the body field, which is not of interest to clients, but is used by some representations (Adjacency List and Incidence List) to add per-vertex strucure.

The following functions are provided for working with vertices:

const char *vertex_get_name(const vertex *v);
Get the vertex’s name
void *vertex_get_data(const vertex *v);
Get the data associated with a vertex

Edges

How edges are implemented internally varies with the representation.
In fact, in three representations, Adjacency List, Adjacency Matrix and Incidence Matrix, edges do not exist internally as objects at all.
From the viewpoint of clients however, edges, as enumerated by the iterator returned by the function to retrieve edges, are this structure:

typedef struct {
vertex *from;
vertex *to;
} edge;


The following functions are provided for working with edges:

const vertex *edge_get_from(const edge *e);
Get the vertex that is the starting-point of an edge
const vertex * edge_get_to(const edge *e);
Get the vertex that is the end-point of an edge

Example program

The following program constructs the graph shown in the introduction using the intuitive representation, graph1, and then enumerates the vertices, neighbours and edges:

#include <stdio.h>

#include <graph1.h>

int main(void)
{
graph1 *graph;
vertex *v;
vertex *A, *B, *C, *D, *E;
iterator *vertices, *edges;
edge *e;

/* Create a graph */
graph = graph1_create();

/* Display */
printf("Vertices (%d) and their neighbours:\n\n", graph1_get_vertex_count(graph));
vertices = graph1_get_vertices(graph);
while ((v = iterator_get(vertices))) {
iterator *neighbours;
vertex *neighbour;
unsigned int n = 0;
printf("%s (%d): ", vertex_get_name(v), graph1_get_neighbour_count(graph, v));
neighbours = graph1_get_neighbours(graph, v);
while ((neighbour = iterator_get(neighbours))) {
printf("%s", vertex_get_name(neighbour));
if (n < graph1_get_neighbour_count(graph, vertex) - 1) {
fputs(", ", stdout);
}
n++;
}
putchar('\n');
iterator_delete(neighbours);
}
putchar('\n');
iterator_delete(vertices);
printf("Edges (%d):\n\n", graph1_get_edge_count(graph));
edges = graph1_get_edges(graph);
while ((e = iterator_get(edges))) {
printf("<%s, %s>\n", vertex_get_name(edge_get_from(e)), vertex_get_name(edge_get_to(e)));
}
putchar('\n');
iterator_delete(edges);

/* Delete */
graph1_delete(graph);

return 0;
}


Graph representations

There are essentially 5 ways of representing a graph:

The intuitive representation: graph1

What I call the "intuitive" and can also called the "object-oriented" representation is a direct translation of the mathematical definition of a graph into a data type:

typedef struct {
set *vertices;
set *edges;
} graph1;

• Adding a vertex simply requires adding it to the vertex set.
• Adding an edge simply requires adding it to the edge set.
• Removing vertices and edges simply means removing them from the respective sets.
• To find a vertex’s neighbours, search the edge set for edges having the vertex as the from field.
• To determine if two vertices are adjacent, search the edge set for an edge having the first vertex as its from field, and the second vertex as its to field.
• Getting all of the edges is easy; just return an iterator over the edge set.
• For undirected graphs, each edge would be stored only once, and getting neighbours and adjacency testing would look at both vertices.

The edge object would not be from and to but simply first and second, i.e., an unordered pair.

• This is one of the representations where edges exist internally as objects (Incidence List is the other).
• This is most like a sparse Adjacency Matrix, with the edge set holding those pairs that are adjacent, and non-adjacent pairs being absent.

The graph is made up of a set of vertices.
Each vertex contains a set of vertices for its neighbours.

typedef struct {
set *vertices;
} graph2;

typedef struct {
set *neighbours;
} vertex_body;


For the graph shown in the introduction, the sets of neighbours would look like this:

A: {B, D}
B: {C}
C: {B}
D: {A, C, E}
E: {}

• Adding a vertex just means adding it to the vertex set.
• Adding an edge means adding the end-point of it to the starting vertex’s neighbour set.
• It is easy to go from a vertex to its neighbours, because the vertex stores them all.

Just return an iterator over them.

This makes the graph argument in the function to retrieve neighbours unnecessary in this implementation.

• Testing for adjacency is easy; just search the first vertex’s neighbours for the second vertex.
• Getting all edges is more difficult to implement in this representation, because edges don’t exist as objects.

You need to iterate over the neighbours of each vertex in turn, and construct the edge from the vertex and the neighbour.

The graph is made up of a set of vertices and a matrix, whose rows and columns are indexed by vertices, and which contains a 1 entry if the vertices are connected.

typedef struct {
set    *vertices;
matrix *edges;
} graph3;


The adjacency matrix for the graph shown in the introduction would look like this:

$$\begin{array}{c c} & \begin{array}{c c c} A & B & C & D & E \\ \end{array} \\ \begin{array}{c c c} A\\ B\\ C\\ D\\ E\\ \end{array} & \left[ \begin{array}{c c c} 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 \end{array} \right] \end{array}$$

• When adding a vertex, add a row and column to the matrix.
• When removing a vertex, remove its row and column.
As adding and removing rows and columns is expensive, these make the adjacency matrix unsuitable for graphs in which vertices are frequently added and removed.

• Adding and removing edges is easy however, and requires no allocation or deallocation of memory, just setting a matrix element.
• To get neighbours, look along the vertex’s row for 1s.
• To determine adjacency, look for a 1 at the intersection of the first vertex’s row and the second vertex’s column.
• To get the edge set, find all of the 1s in the matrix and construct the edges from the corresponding vertices.
• If the graph is undirected, the matrix will be symmetrical about the main diagonal.
This means that you can drop half of it, making a triangular matrix.

• The vertex set needs to be ordered so that the index number of vertices can be looked up, or the matrix needs to be a 2-d map keyed by the vertices themselves.
• Memory used for edges is a constant |V|2.
The best use of this is a graph that is nearly complete, i.e., has a lot of edges.

• The matrix can be sparse; this relates the memory usage more closely to the number of edges.
It also makes addition and removal of columns easier (no block shifts), but requires renumbering afterwards.

• You can use booleans or bits in the matrix to save memory.

Incidence Matrix: graph4

The graph is made up of a set of vertices and a matrix, as in Adjacency Matrix, but the matrix is vertices × edges, with each column containing two non-zero entries, one for the starting-point vertex and one for the end-point.

typedef struct {
set    *vertices;
matrix *edges;
} graph4;


The incidence matrix for the graph shown in the introduction looks like this (1 means "from" and 2 means "to"):

$$\begin{array}{c c} & \\ \begin{array}{c c c} A\\ B\\ C\\ D\\ E\\ \end{array} & \left[ \begin{array}{c c c} 1 & 1 & 0 & 0 & 2 & 0 & 0 \\ 2 & 0 & 1 & 2 & 0 & 0 & 0 \\ 0 & 0 & 2 & 1 & 0 & 2 & 0 \\ 0 & 2 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 2 \\ \end{array} \right] \end{array}$$

• When you add a vertex, you add a row to the matrix.
• When you add an edge, you add a column to the matrix.
• When you remove a vertex, you need to remove all of the columns containing the vertex from the matrix.
• Getting the edges means iterating over the columns and constructing the edges from the two values.
• To find neighbours, look for 1s in the vertex’s row, and in each such column look for the 2 value, which is the neighbour.
• To determine adjacency, find a column containing a 1 in the starting-point vertex’s row, and a 2 in the end-point’s row.
• For an undirected graph, you have one column per edge, and just the value 1 for "connected", so each column contains two 1s.

Incidence List: graph5

There is a set of vertices as in Adjacency List, but each vertex stores a list of the edges that it is the starting-point of, rather than neighbours.

typedef struct {
set * vertices;
} graph5;

typedef struct {
set *edges;
} vertex_body;


For the graph shown in the introduction, the sets of edges would look like this:

A: {<A, B>, <A, D>}
B: {<B, C>}
C: {<C, B>}
D: {<D, A>, <D, C>, <D, E>}
E: {}

• Adding a vertex just means adding it to the vertex set.
• Adding an edge means adding it to its starting vertex’s edge set.
• Finding if two vertices are adjacent requires searching the first vertex’s edge set for an edge containing the second vertex as its to field.
• Getting the neighbours requires retrieving them from the pairs in the set of edges for the vertex.
• Getting the edge set requires enumerating each of the vertices’ edge sets in turn.
• You can store the edges in the graph object as well as in each vertex.