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).
A wheel graph on 7 vertices showing an independent set
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,
    DISCARDED = 2
} 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, 
                            edges[i].second, DISCARDED);
                }
                else if (edges[i].second == v
                        && vertices[edges[i].first].state == IN_GRAPH)
                {
                    move_vertex(vertices, order, edges, size,
                            edges[i].first, DISCARDED);
                }
            }
        }
        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).
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.

Partial Latin square completion using backtracking in C

The partial Latin square completion problem is to take a partially-filled Latin square and to determine if it can be completed successfully. For example, below is a 1-based order 5 partial Latin square:

\(
\left( \begin{array}{ccc}
\cdot & 2 & \cdot & \cdot & \cdot \\
\cdot & \cdot & \cdot & \cdot & 3 \\
\cdot & \cdot & 5 & \cdot & \cdot \\
4 & \cdot & \cdot & \cdot & \cdot \\
\cdot & \cdot & \cdot & 2 & \cdot \end{array} \right)
\)

 

The problem is to find out if it can be completed, which in this case it can, to this square:

\(
\left( \begin{array}{ccc}
1 & 2 & 3 & 4 & 5 \\
2 & 1 & 4 & 5 & 3 \\
3 & 4 & 5 & 1 & 2 \\
4 & 5 & 2 & 3 & 1 \\
5 & 3 & 1 & 2 & 4 \end{array} \right)
\)

 

The partial Latin square completion problem is NP-complete, but can be solved using backtracking.

Here is an implementation in C. It takes a partial Latin square in the form of a 1-dimensional array, with 0s for the unfilled cells, and a callback function which is called with the solution, if found.

#include <stdlib.h>

static void get_row_column(unsigned int cell, unsigned int *row, unsigned int *column, size_t size)
{
    *row = cell / size;
    *column =  cell % size;
}

static unsigned int get_value(const unsigned int *square, size_t size, unsigned int row,
        unsigned int column)
{
    return square[row * size + column];
}

static unsigned int unique_in_column(const unsigned int *square, size_t size, unsigned int cell)
{
    unsigned int row;
    unsigned int column;
    get_row_column(cell, &row, &column, size);
    unsigned int r;
    unsigned int unique = 1;
    for (r = 0; r < size && unique; r++) {
        unique = r == row || get_value(square, size, r, column) != square[cell];
    } 
    return unique;
}

static unsigned int unique_in_row(const unsigned int *square, size_t size, unsigned int cell)
{
    unsigned int row;
    unsigned int column;
    get_row_column(cell, &row, &column, size);
    unsigned int c;
    unsigned int unique = 1;
    for (c = 0; c < size && unique; c++) {
        unique = c == column || get_value(square, size, row, c) != square[cell];
    } 
    return unique;
}

static unsigned int promising(const unsigned int *square, size_t size, unsigned int cell)
{
    return square[cell] == 0
        || (unique_in_row(square, size, cell)
                && unique_in_column(square, size, cell));
}

static unsigned int get_next_cell(const unsigned int *square, size_t size, unsigned int *cell)
{
    unsigned int found = 0;
    unsigned int i;
    for (i = *cell; i < size * size && !found; i++) {
        if (square[i] == 0) {
            found = 1;
            *cell = i;
        }
    }
    return found;
}

static void latin_square_completion_recursive(unsigned int *square, size_t size, unsigned int cell,
        unsigned int *succeeded, latin_square_completionfn fun)
{
    if (!get_next_cell(square, size, &cell)) {
        *succeeded = 1;
        fun(square, size);
    }
    else {
        unsigned int i;
        for (i = 1; i <= size && !*succeeded; i++) {
            unsigned int temp = square[cell];
            square[cell] = i;
            if (promising(square, size, cell)) {
                latin_square_completion_recursive(square, size, cell + 1, succeeded, fun);
            }
            square[cell] = temp;
        }
    }
}

void latin_square_completion(unsigned int *square, size_t size,
        latin_square_completionfn fun)
{
    unsigned int cell = 0;
    unsigned int succeeded = 0;
    latin_square_completion_recursive(square, size, cell, &succeeded, fun);
}

Here is a program to complete the partial Latin square shown at the beginning:

#include <stdio.h>

static void print(const unsigned int *square, size_t size)
{
    unsigned int i;
    for (i = 0; i < size * size; i++) {
        printf("%d ", square[i]);
        if (i % size == size - 1) {
            printf("\n");
        }
    }
    printf("\n");
}

int main(void)
{
    unsigned int square[] = {0, 2, 0, 0, 0,
                             0, 0, 0, 0, 3,
                             0, 0, 5, 0, 0,
                             4, 0, 0, 0, 0,
                             0, 0, 0, 2, 0};
    latin_square_completion(square, 5, print);
    return 0;
}

The output:

1 2 3 4 5
2 1 4 5 3
3 4 5 1 2
4 5 2 3 1
5 3 1 2 4

Sudoku using backtracking in C

The title says it all. Here is the code:

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

static void get_row_column(unsigned int cell, unsigned int *row, unsigned int *column)
{
    *row = cell / 9;
    *column =  cell % 9;
}

static unsigned int get_value(const unsigned int *grid, unsigned int row, unsigned int column)
{
    return grid[row * 9 + column];
}

static unsigned int unique_in_column(const unsigned int *grid, unsigned int cell)
{
    unsigned int row;
    unsigned int column;
    get_row_column(cell, &row, &column);
    unsigned int r;
    unsigned int unique = 1;
    for (r = 0; r < 9 && unique; r++) {
        unique = r == row || get_value(grid, r, column) != grid[cell];
    } 
    return unique;
}

static unsigned int unique_in_row(const unsigned int *grid, unsigned int cell)
{
    unsigned int row;
    unsigned int column;
    get_row_column(cell, &row, &column);
    unsigned int c;
    unsigned int unique = 1;
    for (c = 0; c < 9 && unique; c++) {
        unique = c == column || get_value(grid, row, c) != grid[cell];
    } 
    return unique;
}

static void get_box(unsigned int cell, unsigned int *row, unsigned int *column)
{
    get_row_column(cell, row, column);
    *row = (*row / 3) * 3;
    *column = (*column / 3) * 3;
}

static unsigned int unique_in_box(const unsigned int *grid, unsigned int cell)
{
    unsigned int row, column;
    unsigned int top, left;
    unsigned int r, c;
    unsigned int unique = 1;
    get_row_column(cell, &row, &column);
    get_box(cell, &top, &left);
    for (r = top; r < top + 3 && unique; r++) {
        for (c = left; c < left + 3 && unique; c++) {
            if (r != row && c != column) {
                unique = get_value(grid, r, c) != grid[cell];
            }
        }
    }
    return unique;
}

static unsigned int promising(const unsigned int *grid, unsigned int cell)
{
    return grid[cell] == 0 
        || (unique_in_row(grid, cell)
        && unique_in_column(grid, cell)
        && unique_in_box(grid, cell)); 
}

static unsigned int get_next_cell(const unsigned int *grid, unsigned int *cell)
{
    unsigned int found = 0;
    unsigned int i;
    for (i = *cell; i < 81 && !found; i++) {
        if (grid[i] == 0) {
            found = 1;
            *cell = i;
        }
    }
    return found;
}

static void print_grid(const unsigned int *grid)
{
    unsigned int i;
    for (i = 0; i < 81; i++) {
        printf("%d ", grid[i]);
        if (i % 9 == 8) {
            printf("\n");
        }
    }
    printf("\n");
}

static void sudoku_recursive(unsigned int *grid, unsigned int cell,
        unsigned int *succeeded)
{
    if (!get_next_cell(grid, &cell)) {
        *succeeded = 1;
        print_grid(grid);
    }
    else {
        unsigned int i;
        for (i = 1; i <= 9 && !*succeeded; i++) {
            unsigned int temp = grid[cell];
            grid[cell] = i;
            if (promising(grid, cell)) {
                sudoku_recursive(grid, cell + 1, succeeded);
            }
            grid[cell] = temp;
        }
    }
}

void sudoku(unsigned int *grid)
{
    unsigned int cell = 0;
    unsigned int succeeded = 0;
    sudoku_recursive(grid, cell, &succeeded);
}

An example program with the “World’s hardest sudoku“:

#include <stdio.h>

int main(void)
{
    unsigned int grid[] = {
        8, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 3, 6, 0, 0, 0, 0, 0,
        0, 7, 0, 0, 9, 0, 2, 0, 0,
        0, 5, 0, 0, 0, 7, 0, 0, 0,
        0, 0, 0, 0, 4, 5, 7, 0, 0,
        0, 0, 0, 1, 0, 0, 0, 3, 0,
        0, 0, 1, 0, 0, 0, 0, 6, 8,
        0, 0, 8, 5, 0, 0, 0, 1, 0,
        0, 9, 0, 0, 0, 0, 4, 0, 0
    };
    sudoku(grid);
    return 0;
}

The output:

8 1 2 7 5 3 6 4 9
9 4 3 6 8 2 1 7 5
6 7 5 4 9 1 2 8 3
1 5 4 2 3 7 8 9 6
3 6 9 8 4 5 7 2 1
2 8 7 1 6 9 5 3 4
5 2 1 9 7 4 3 6 8
4 3 8 5 2 6 9 1 7
7 9 6 3 1 8 4 5 2

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

Shortest Common Supersequence via LCS in C

In my Shortest Common Supersequence post I gave a dynamic programming algorithm that computes the SCS in a manner very similar to the Longest Common Subsequence algorithm. Another way of computing the SCS is to find the LCS first, and then insert into it those characters from the two strings that are not in the LCS.

As an example, given the two strings “pAqBrCs”, and “wAxByCz”, their LCS is “ABC”, and we can form their SCS by inserting the remaining characters from each string into it in the correct order. One such SCS would be “pwAqxBryCsz”, but there are several possibilities because it doesn’t matter whether we insert the characters from the first string first or the second string at any point, as long as we add them in the order they occur in that string.

The algorithm just needs to scan the two strings, adding the characters not in the LCS while keeping track of where the LCS characters are, and making sure they are only added once. This is how it looks in C:

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

char *shortest_common_supersequence_by_lcs(const char *str1, const char *str2)
{
    char *lcs = longest_common_subsequence(str1, str2);
    const size_t lcs_len = strlen(lcs);
    const size_t scs_len = lcs_len + (strlen(str1) - lcs_len) + (strlen(str2) - lcs_len);
    char *scs = malloc(scs_len + 1);
    unsigned int lcs_pos = 0, str1_pos = 0, str2_pos = 0, scs_pos = 0;

    /* Add the characters up to the last LCS character */
    while (lcs_pos < lcs_len) {
        while (str1[str1_pos] != lcs[lcs_pos]) {
            scs[scs_pos++] = str1[str1_pos++];
        }
        while (str2[str2_pos] != lcs[lcs_pos]) {
            scs[scs_pos++] = str2[str2_pos++];
        }
        scs[scs_pos++] = lcs[lcs_pos++];
        str1_pos++;
        str2_pos++;
    }
    /* Add the characters after the LCS */
    while (str1[str1_pos]) {
        scs[scs_pos++] = str1[str1_pos++];
    }
    while (str2[str2_pos]) {
        scs[scs_pos++] = str2[str2_pos++];
    }
    scs[scs_pos] = '\0';
    free(lcs);
    return scs;
}

An example program:

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

int main(void)
{
    char a[] = "pAqBrCs";
    char b[] = "wAxByCz";
    char *scs = shortest_common_supersequence_by_lcs(a, b);
    printf("Shortest Common Supersequence is %s\n", scs);
    free(scs);
    return 0;
}

Output:

Shortest Common Supersequence is pwAqxBryCsz

Max subarray sum using dynamic programming in C

The maximum subarray problem is to find the subarray within an array of integers with the largest sum. There is a linear time dynamic programming algorithm for solving it invented by Joseph Kadane.

Here it is in C:

int max(int a, int b)
{
    return a > b ? a : b;
}

int max_subarray(int *array, size_t n)
{
    int max_ending_here = 0;
    int max_so_far = 0;
    unsigned int i;

    for (i = 0; i < n; i++) {
        max_ending_here = max(0, max_ending_here + array[i]);
        max_so_far = max(max_so_far, max_ending_here);
    }
    return max_so_far;
}

Example program:

int main(void)
{
    int array[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    const size_t n = sizeof(array) / sizeof(int);
    printf("Max subarray sum is %d\n", max_subarray(array, n));
    return 0;
}

Output:

6