Graph implementation in C

Question

I've recently been learning C on my own, and I thought I'd try my hand at writing a graph implementation.

// graph.h
#ifndef GRAPH_H
#define GRAPH_H

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

typedef struct node node_t;

typedef struct node {
    int value;
    node_t **links;
    int links_count;
} node_t;

node_t *create_node(int value);
void destroy_node(node_t *node);
void link_nodes(node_t *first_node, node_t *second_node);
void unlink_nodes(node_t *first_node, node_t *second_node);

#endif /* GRAPH_H */

// graph.c
#include "graph.h"

static void remove_link(node_t *node, int index) {
    // If the index is out of bounds, return early
    if (index >= node->links_count || index < 0) return;

    // Move links down the array, overwriting the link's index
    for (int i = index; i < node->links_count - 1; i++) {
        node->links[i] = node->links[i + 1];
    }

    // Get rid of the dangling pointer
    node->links[node->links_count - 1] = NULL;

    if (node->links_count == 1) {
        // If this is the only link, deallocate arrays
        free(node->links);
        node->links = NULL;
    } else {
        // Otherwise, shrink them
        node->links = realloc(node->links, sizeof(node_t *) * --node->links_count);
    }
}

static void increase_link_space(node_t *node) {
    if (node->links_count == 0) {
        // If there isn't an array, create one
        node->links = malloc(sizeof(node_t *));
    } else {
        // Otherwise, expand it
        node->links = realloc(node->links, sizeof(node_t *) * (node->links_count + 1));
    }
}

node_t *create_node(int value) {
    // Allocate memory for the node
    node_t *node = malloc(sizeof(node_t));
    if (node == NULL) exit(-1);

    node->links_count = 0;
    node->value = value;
    return node;
}

void destroy_node(node_t *node) {
    // Remove all links to and from other nodes
    // For each link in this node...
    for (int i = 0; i < node->links_count; i++) {
        // For each link in the link...
        for (int j = 0; j < node->links[i]->links_count; j++) {
            // If a link matches the original node (i.e. loopback)...
            if (node->links[i]->links[j] == node) {
                // Remove the link and break
                remove_link(node->links[i]->links[j], j);
                break;
            }
        }
    }

    // Free up malloc'd memory
    free(node->links);
    free(node);
}

void link_nodes(node_t *first_node, node_t *second_node) {
    // Create space for the new link
    increase_link_space(first_node);
    increase_link_space(second_node);

    // Link the first node to the second node
    first_node->links[first_node->links_count] = second_node;

    // Link the second node to the first
    second_node->links[second_node->links_count] = first_node;
}

void unlink_nodes(node_t *first_node, node_t *second_node) {
    // The index of second_node in first_node's links
    int first_index = -1;
    // The index of first_node in second_node's links
    int second_index = -1;

    // Search through first_node->links
    for (int i = 0; i < first_node->links_count; i++) {
        if (first_node->links[i] == second_node) {
            first_index = i;
            break;
        }
    }

    // If no match was found, return
    if (first_index < 0) return;

    // Search through second_node->links
    for (int i = 0; i < second_node->links_count; i++) {
        if (second_node->links[i] == first_node) {
            second_index = i;
            break;
        }
    }
    // We don't need a second check, because as long as the program is using node_t correctly, one-way links won't exist.
    // Even if a one-way link exists, remove_link has a check for out-of-bounds (including negative) indices.

    // Remove the found indices
    remove_link(first_node, first_index);
    remove_link(second_node, second_index);
}

Here's a test program:

#include "graph.h"

int main(void) {
    node_t *first_node = create_node(5);
    node_t *second_node = create_node(7);
    node_t *third_node = create_node(3);
    /*
        3
                7

          5
    */

    link_nodes(first_node, second_node);
    link_nodes(first_node, third_node);
    /*
        3
        ^        7
        |        ^
        ->5<-----|
    */

    destroy_node(third_node);
    /*

                 7
                 ^
          5<-----|
    */

    unlink_nodes(first_node, second_node);
    /*

                 7

          5
    */

    destroy_node(first_node);
    destroy_node(second_node);
}

This is my first data structure implementation, so any and all tips/criticism would be really helpful.

Can you show a usage example so that reviewers can easily test it? — L. F.
– L. F., Commented Oct 1, 2020 at 8:38

G. Sliepen · Accepted Answer · 2020-10-01 19:50:24Z

Only `#include` what you need, where you need it

In graph.h, you #include <stdlib.h> and <string.h>, but you don't use anything from those headers inside graph.h itself, so you should not #include anything there. Instead, in graph.c, you need to #include <stdlib.h> in order to use malloc() and free(), but you don't need anything else.

Avoid unnecessary forward declarations

You are doing a typedef struct node node_t twice. The first one was needed to be able to write node_t inside the definition of struct node. But you can avoid this by just writing:

typedef struct node {
    int value;
    struct node **links;
    int links_count;
} node_t;

This avoids the duplication (GCC will warn about it if you compile with -std=c99 -pedantic).

Improve `struct` packing

On a 64-bit machine, your struct node will use 24 bytes, but you can reduce that to only 16 bytes by writing:

typdef struct node {
    int value;
    int links_count;
    node_t **links;
} node_t;

This is because the ints are only 4 bytes, but pointers are 8 bytes, and need to be aligned to 8 bytes.

Remove redundant comments

Comments should be added when the code itself is not clear on its own. However, just repeating in English exactly what a C statement does is not helpful. For example, in destroy_node(), I would only keep the first comment:

void destroy_node(node_t *node) {
    // Remove all links to and from other nodes
    for (int i = 0; i < node->links_count; i++) {
        for (int j = 0; j < node->links[i]->links_count; j++) {
            if (node->links[i]->links[j] == node) {
                remove_link(node->links[i]->links[j], j);
                break;
            }
        }
    }

    free(node->links);
    free(node);
}

Optimizing link addition/removal

Adding a link is potentially slow, because you reallocate just enough for one more link at a time. Since realloc() might not be able to grow the allocation in-place, this means your link addition becomes \$\mathcal{O}(D^2)\$, where \$D\$ is the average number of links per node. A common trick to reduce the overhead from memory allocation is to double the size of the array whenever it is full, so the more links you have the less often you have to reallocate it.

Removal has a similar performance problem, because you have to scan the list of links to find a match, and then in the node that you linked to you have to do the same. Furthermore, when deleting a link, you are shifting all remaining elements in the array links by one.

Depending on how often you add or remove links, you might have different ways to optimize this. For example, if you rarely remove links, then I would just optimize how you remove an element from an array: instead of shifting down the remaining elements, just copy the last element into the place of the deleted element. If you often remove links, then you might benefit from keeping the array links sorted, so that looking up a link is \$\mathcal{O}(\log D)\$. The drawback is of course that inserting a link becomes more complicated, but for large, dense graphs this should be much faster. You can also consider only sorting the array right before you need to search it. Have a look at these standard C functions that help you do binary searches:

Another thing to think about is whether you really need both nodes have a link to each other. You could also treat it as a directed graph, and then you don't need to keep links in sync.

Use `size_t` for counts, sizes and array indices

An int might not be large enough to handle all possible array sizes. Use a size_t instead, it is guaranteed to be able to uniquely index all elements of an array that fit inside the memory accessible to your program. This means changing the type of links_count, and using size_t i in for-loops. Avoid using -1 as a special value indicating that you didn't find an element, instead use the fact that links_count is an index that doesn't point to a valid element, or use a separate variable to keep track of whether you found an element or not.

Thank you for the thorough review! 🙂 The <string.h> include was a remnant from when I used to store strings before I genericised the structure; I guess I forgot to remove it. The way I'm attempting to use this requires bidirectional links. What do you mean by "use the fact that links_count is an index that doesn't point to a valid element"? — dropbear
– dropbear, Commented Oct 1, 2020 at 19:57
Instead of using int first_index = -1, you can write size_t first_index = first_node->link_count, and then check if you didn't find a match like so: if (first_index == first_node->link_count) return. — G. Sliepen
– G. Sliepen, Commented Oct 1, 2020 at 20:12
I see. Wouldn't that be less efficient since it involves a dereference? (I'm genuinely asking; I don't know if such a difference would even be important.) — dropbear
– dropbear, Commented Oct 1, 2020 at 20:19
You already use first_node->link_count in the for-statement. The compiler can see that it only needs to read the value once, and can keep it in a register. — G. Sliepen
– G. Sliepen, Commented Oct 1, 2020 at 20:42

Stack Exchange Network

Graph implementation in C

1 Answer 1

Only `#include` what you need, where you need it

Avoid unnecessary forward declarations

Improve `struct` packing

Remove redundant comments

Optimizing link addition/removal

Use `size_t` for counts, sizes and array indices

You must log in to answer this question.

Hot Network Questions

Graph implementation in C

1 Answer 1

Only #include what you need, where you need it

Avoid unnecessary forward declarations

Improve struct packing

Remove redundant comments

Optimizing link addition/removal

Use size_t for counts, sizes and array indices

You must log in to answer this question.

Related

Hot Network Questions

Only `#include` what you need, where you need it

Improve `struct` packing

Use `size_t` for counts, sizes and array indices