Tag Archives: Graph Theory

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).
Graph containing a cycle
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) {
            /* Adjacent */
            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).
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.

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;
    hamiltonian_circuits_recursive(adjmat, n, circuit, 1, fun);
    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)
{
    unsigned int **adjmat;
    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++) {
            adjmat[i][j] = 1;
        }
    }

    hamiltonian_circuits(adjmat, n, print_circuit);
    for (i = 0; i < n; i++) {
        free(adjmat[i]);
    }
    free(adjmat);

    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 (promising(i, adjmat, colours)) {
        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 */
    vertex_colouring(adjmat, len, m, print_colouring);
    return 0;
}

Graph data structures

Contents

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.

Neighbours and adjacency

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.

Graph showing 5 vertices labelled A to E

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();

    /* Add vertices */
    A = graph1_add(graph, "A", NULL);
    B = graph1_add(graph, "B", NULL);
    C = graph1_add(graph, "C", NULL);
    D = graph1_add(graph, "D", NULL);
    E = graph1_add(graph, "E", NULL);

    /* Add edges */
    graph1_add_edge(graph, A, B);
    graph1_add_edge(graph, A, D);
    graph1_add_edge(graph, B, C);
    graph1_add_edge(graph, C, B);
    graph1_add_edge(graph, D, A);
    graph1_add_edge(graph, D, C);
    graph1_add_edge(graph, D, E);

    /* 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.

    Adjacency List: graph2

    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.

    Adjacency Matrix: graph3

    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.
  • Graph algorithms

    Introduction

    This is a list of graph algorithms with links to references and implementations.
    The graph libraries included are igraph, NetworkX, and Boost Graph Library.

    Contents

    Generators

    Deterministic

    Star

    Wikipedia: https://en.wikipedia.org/wiki/Star_%28graph_theory%29

    Complete

    Wikipedia: https://en.wikipedia.org/wiki/Complete_graph

    Note that the igraph function can produce directed complete graphs, as well as those containing 1 or more self-loops.

    Tree

    Famous

    Bull

    Wikipedia: https://en.wikipedia.org/wiki/Bull_graph

    Chvátal

    Wikipedia: https://en.wikipedia.org/wiki/Chv%C3%A1tal_graph

    Cubic

    Wikipedia: https://en.wikipedia.org/wiki/Cubic_graph

    Diamond

    Wikipedia: https://en.wikipedia.org/wiki/Diamond_graph

    Dodecahedral

    Wolfram MathWorld: http://mathworld.wolfram.com/DodecahedralGraph.html

    Frucht

    Wikipedia: https://en.wikipedia.org/wiki/Frucht_graph

    Heawood

    Wikipedia: https://en.wikipedia.org/wiki/Heawood_graph

    House

    Wolfram MathWorld: http://mathworld.wolfram.com/HouseGraph.html

    Icosahedral

    Wolfram MathWorld: http://mathworld.wolfram.com/IcosahedralGraph.html

    Krackhardt Kite

    Wolfram MathWorld: http://mathworld.wolfram.com/KrackhardtKite.html

    Octahedral

    Wolfram MathWorld: http://mathworld.wolfram.com/OctahedralGraph.html

    Petersen

    Wolfram MathWorld: http://mathworld.wolfram.com/PetersenGraph.html

    Tetrahedral

    Wolfram MathWorld: http://mathworld.wolfram.com/TetrahedralGraph.html

    Tutte

    Wikipedia: https://en.wikipedia.org/wiki/Tutte_graph

    Random

    Erdos-Rényi

    Wikipedia: https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model

    Watts-Strogatz

    Wikipedia: https://en.wikipedia.org/wiki/Watts_and_Strogatz_model

    Barabási–Albert

    Wikipedia: https://en.wikipedia.org/wiki/Barab%C3%A1si%E2%80%93Albert_model

    Traversal

    Lecture notes: http://web.cse.ohio-state.edu/~gurari/course/cis680/cis680Ch14.html

    Depth-first search

    Wikipedia: https://en.wikipedia.org/wiki/Depth-first_search

    Breadth-first search

    Wikipedia: https://en.wikipedia.org/wiki/Breadth-first_search

    Isomorphism

    Wikipedia: https://en.wikipedia.org/wiki/Graph_isomorphism

    Connected components

    Wikipedia: https://en.wikipedia.org/wiki/Connectivity_%28graph_theory%29

    Connectivity

    Connectivity testing

    Decomposition into connected components

    Strong connectivity

    Strong connectivity testing

    Decomposition into strongly connected components

    Weak connectivity

    Weak connectivity testing

    Decomposition into weakly connected components

    Biconnectivity

    Biconnected components

    Articulation points

    Cliques

    Wikipedia: https://en.wikipedia.org/wiki/Clique_%28graph_theory%29

    Cliques

    Maximal cliques

    Clique number

    Number of maximal cliques

    Flows and Cuts

    Lecture notes: http://www.cs.princeton.edu/courses/archive/spr04/cos226/lectures/maxflow.4up.pdf

    Maximum flow

    Maximum flow value

    Minimum cut

    Minimum cut value

    Shortest paths

    Wikipedia: https://en.wikipedia.org/wiki/Shortest_path_problem

    Shortest paths

    Dijkstra

    Bellman-Ford

    Johnson

    A*

    Distance measures

    Wikipedia: https://en.wikipedia.org/wiki/Distance_%28graph_theory%29

    Diameter

    Eccentricity

    Radius

    Centrality measures

    Lecture notes: http://cs.brynmawr.edu/Courses/cs380/spring2013/section02/slides/05_Centrality.pdf

    Closeness

    Betweenness

    Google PageRank

    Paper: http://ilpubs.stanford.edu:8090/422/1/1999-66.pdf

    Directed Acyclic Graphs (DAGs)

    Wikipedia: https://en.wikipedia.org/wiki/Directed_acyclic_graph

    DAG testing

    Topological sort

    Transitive closure

    Bipartite graphs

    Wolfram Mathworld: http://mathworld.wolfram.com/BipartiteGraph.html

    Creation

    Testing

    Creation from adjacency matrix

    Note that the igraph documentation calls this an incidence matrix.

    Conversion to adjacency matrix

    Note that the igraph documentation calls this an incidence matrix.

    Projection

    Cores

    Paper: http://arxiv.org/abs/cs.DS/0310049

    Core number

    Chordal graphs

    Wolfram Mathworld: http://mathworld.wolfram.com/ChordalGraph.html

    Chordal testing

    Maximum cardinality search

    Spanning trees

    Wikipedia: https://en.wikipedia.org/wiki/Spanning_tree

    Note that in NetworkX they are called arborescences (http://networkx.github.io/documentation/networkx-1.10/reference/algorithms.tree.html#recognition-tests).

    Minimum spanning tree

    Clustering

    Article: http://dollar.biz.uiowa.edu/~street/graphClustering.pdf

    Transitivity

    Clustering coefficient (local transitivity)

    Average clustering (average local transitivity)

    Degree sequences

    http://mathworld.wolfram.com/DegreeSequence.html

    Simple graph testing

    Pseudograph testing

    Spectral properties

    Book chapter: http://www.cs.yale.edu/homes/spielman/PAPERS/SGTChapter.pdf

    Laplacian matrix

    Reading and writing graphs

    Edge list

    GraphML

    The GraphML File Format: http://graphml.graphdrawing.org/

    GML

    GML: a portable Graph File Format: http://www.fim.uni-passau.de/fileadmin/files/lehrstuhl/brandenburg/projekte/gml/gml-technical-report.pdf

    Pajek

    Pajek / Pajek-XXL: http://mrvar.fdv.uni-lj.si/pajek/

    GraphViz

    GraphViz: http://www.graphviz.org/