Realising a graph degree sequence in C

An example graph

The degree sequence of a graph is the sequence of the degrees of each if its vertices. It is usually written in non-increasing order. For example, the degree sequence of the graph shown above is <4, 2, 2, 2, 2, 1, 1, 1, 1>. It’s easy to find the degree sequence of a graph – count the number of times each vertex occurs as an endpoint in the edge list, and then sort the results. The following C function will return the degree sequence of graph in edge list form:

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

int compare_unsigned_ints_decreasing(const unsigned int *p1, const unsigned int *p2)
{
    if (*p1 > *p2) {
        return -1;
    }
    if (*p1 < *p2) {
        return 1;
    }
    return 0;
}

unsigned int *degree_sequence(const edge *edges, unsigned int size, unsigned int order)
{
    unsigned int *sequence = calloc(order, sizeof(unsigned int));
    if (sequence != NULL) {
        unsigned int e;
        for (e = 0; e < size; e++) {
            sequence[edges[e].first]++;
            sequence[edges[e].second]++;
        }
    }
    qsort(sequence, order, sizeof(unsigned int),
            (int(*)(const void *, const void *))compare_unsigned_ints_decreasing);
    return sequence;
}

The sum of the numbers in a graph’s degree sequence will divide by 2 because every edge has 2 endpoints, but other than that it isn’t easy to tell if a given sequence of integers can be the degree sequence of a graph. A sequence that can be the degree sequence of a graph is called a graphic sequence. One way to find out if a sequence is graphic is to simulate constructing a graph out of it, treating the vertex degrees as a resource to use up by adding edges. This process is called realising the sequence. There is an algorithm by Havel and Hakimi to do this, which goes as follows:

  1. While there are non-0 numbers in the degree sequence:
    1. Connect the first vertex to as many of the following vertices as its degree, decrementing their degrees accordingly
    2. Make the first vertex’s degree 0 – it is now finished with
    3. Sort the vertices in descending order
  2. If at any point you run out of vertices because you need to decrement a 0-degree vertex or there are not enough vertices in the sequence, then the sequence is not graphical

There are many possible graphs for any given graphical degree sequence, so given the degree sequence of a graph the algorithm will not in general reconstruct the same graph. For example, given the degree sequence of the graph at the top, the algorithm will produce this graph:

Another graph with the same degree sequence

Below is an implementation of the Havel-Hakimi algorithm in C. It takes a degree sequence and it length, a callback function to call when each edge would be added, and a void pointer for user data to be passed to the callback. It doesn’t actually construct a graph data structure but instead leaves it to the client to realise edge-addition events in any way it sees fit.

#include <stdlib.h>

typedef struct {
    unsigned int id;
    unsigned int degree;
} vertex;

int compare_vertices_decreasing(const vertex *v1, const vertex *v2)
{
     return compare_unsigned_ints_decreasing(&v1->degree,
             &v2->degree);
}

unsigned int sum(const unsigned int *numbers, size_t len)
{
    unsigned int i, total = 0;
    for (i = 0; i < len; i++) {
        total += numbers[i];
    }
    return total;
}

typedef void(*realisefn)(unsigned int, unsigned int, void *);

unsigned int realise_sequence(const unsigned int *degrees, size_t len, realisefn fun, void *data)
{
    unsigned int i;
    unsigned int failed = 0;
    unsigned int unused_vertices = len;
    vertex *vertices;
    /* Check for even sum of degrees */
    if (sum(degrees, len) % 2 != 0) {
        return 0;
    }
    /* Initialise vertices */
    vertices = malloc(len * sizeof(vertex));
    if (vertices == NULL) {
        return 0;
    }
    for (i = 0; i < len; i++) {
        vertices[i].id = i;
        vertices[i].degree = degrees[i];
    }
    /* Main loop */
    while (unused_vertices > 0 && !failed) {
        /* Sort vertices in decreasing order of degree */
        qsort(vertices, len, sizeof(vertex), 
                (int(*)(const void *, const void *))compare_vertices_decreasing);
        /* Connect the first vertex to as many others as its degree */
        for (i = 1; i <= vertices[0].degree && !failed; i++) {
            if (i < len && vertices[i].degree > 0) {
                vertices[i].degree -= 1;
                /* Call callback */
                fun(vertices[0].id, vertices[i].id, data);
                if (vertices[i].degree == 0) {
                    unused_vertices--;
                }
            }
            else {
                /* Ran out of vertices */            
                failed = 1;
            }
        }
        /* Finished with first vertex */
        vertices[0].degree = 0;
        unused_vertices--;
    }
    free(vertices);
    return !failed;
}

Below is an example program. It constructs the graph shown at the top, gets its degree sequence, and then passes this to the algorithm, along with a callback and data that will construct the realisation of the degree sequence. The degree sequence of the new graph is then retrieved and is shown to be the same as that of the original graph.

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

/* Connect two edges */
void edge_connect(edge *edges, unsigned int first, unsigned int second, 
        unsigned int *pos)
{
    edges[*pos].first = first;
    edges[*pos].second = second;
    (*pos)++;
}


/* Structure to hold edge list and keep track of current edge */
typedef struct {
    edge *edges;
    unsigned int i;
} edge_list;

/* Callback function to connect two edges */
void connect(unsigned int v1, unsigned int v2, edge_list *graph)
{
    edge_connect(graph->edges, v1, v2, &graph->i);
}

int main(void)
{
    const unsigned int size = 8; /* Edges */
    const unsigned int order = 9; /* Vertices */
    edge *edges = malloc(size * sizeof(edge));
    unsigned int *sequence;
    unsigned int i = 0;
    edge_list graph;

    /* Construct the graph */
    edge_connect(edges, 0, 1, &i);
    edge_connect(edges, 0, 2, &i);
    edge_connect(edges, 0, 3, &i);
    edge_connect(edges, 0, 4, &i);
    edge_connect(edges, 1, 5, &i);
    edge_connect(edges, 2, 6, &i);
    edge_connect(edges, 3, 7, &i);
    edge_connect(edges, 4, 8, &i);

    /* Get the degree sequence */
    sequence = degree_sequence(edges, size, order);
    for (i = 0; i < order; i++) {
        printf("%u ", sequence[i]);
    }
    putchar('\n');
    
    /* Realise the sequence */
    graph.edges = edges;
    graph.i = 0;
    realise_sequence(sequence, order, (realisefn)connect, &graph);

    /* Get the degree sequence again */
    free(sequence);
    sequence = degree_sequence(edges, size, order);
    for (i = 0; i < order; i++) {
        printf("%u ", sequence[i]);
    }
    putchar('\n');

    free(sequence);
    free(edges);
    return 0;

Output:

4 2 2 2 2 1 1 1 1
4 2 2 2 2 1 1 1 1