Graph in C

This is a an implementation of a graph data structure, using what might be called the "intuitive" or "object-orented" representation, in which the graph is stored in memory as a set of vertices and a set of edges. It uses a sorted array as the set data structure.

Here is the header file (graph1.h):

#ifndef GRAPH1_H
#define GRAPH1_H

#include <sortedarray.h>
#include <vertex.h>
#include <edge.h>
#include <iterator.h>

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

graph1 *graph1_create(void);
void graph1_delete(graph1 *graph);
vertex * graph1_add(graph1 *graph, const char *name, void *data);
vertex * graph1_get_vertex(const graph1 *graph, const char *name);
void * graph1_remove(graph1 *graph, vertex *v);
void graph1_add_edge(graph1 *graph, vertex *vertex1, vertex *vertex2);
void graph1_remove_edge(graph1 *graph, vertex *vertex1, vertex *vertex2);
unsigned int graph1_get_adjacent(const graph1 *graph, const vertex *vertex1, const vertex *vertex2);
iterator *graph1_get_neighbours(const graph1 *graph, const vertex *v);
iterator *graph1_get_edges(const graph1 *graph);
iterator *graph1_get_vertices(const graph1 *graph);
unsigned int graph1_get_neighbour_count(const graph1 * graph, const vertex * v);
unsigned int graph1_get_edge_count(const graph1 * graph);
unsigned int graph1_get_vertex_count(const graph1 * graph);

#endif /* GRAPH1_H */

And here is an example program:

#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, v) - 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;
}

This is the output:

Vertices (5) and their neighbours:

A (2): B, D
B (1): C
C (1): B
D (3): A, C, E
E (0):

Edges (7):

A -> B
A -> D
B -> C
C -> B
D -> A
D -> C
D -> E

This is the implementation (graph1.c):

#include <stdlib.h>

#include <edge.h>
#include <sortedarray-iterator.h>

#include <graph1.h>

graph1 *graph1_create(void)
{
	graph1 *graph = malloc(sizeof(graph1));
	if (graph) {
		graph->vertices = sortedarray_create((sortedarray_cmpfn)vertex_compare);
		graph->edges = sortedarray_create((sortedarray_cmpfn)edge_compare);
	}
	return graph;
}

void graph1_delete(graph1 *graph)
{
	if (graph) {
		sortedarray_for_each(graph->vertices, (sortedarray_forfn)vertex_delete);
		sortedarray_delete(graph->vertices);
		sortedarray_for_each(graph->edges, (sortedarray_forfn)edge_delete);
		sortedarray_delete(graph->edges);
		free(graph);
	}
}

vertex *graph1_add(graph1 *graph, const char *name, void *data)
{
	vertex *v = vertex_create(name, data, NULL, NULL);
	vertex *existing = sortedarray_add(graph->vertices, v);
	vertex_delete(existing);
	return v;
}

vertex *graph1_get_vertex(const graph1 *graph, const char *name)
{
	vertex *v = sortedarray_find(graph->vertices, &name);
	return v;
}

void *graph1_remove(graph1 *graph, vertex *v)
{
	vertex * removed;
	void *data;
	unsigned int e = 0;

	/* Remove the edges belonging to this vertex */
	while (e < sortedarray_get_count(graph->edges)) {
		edge *edge = sortedarray_get(graph->edges, e);
		if (edge->from == v || edge->to == v) {
			sortedarray_remove_at(graph->edges, e);
			edge_delete(edge);
		}
		else {
			e++;
		}
	}
	/* Remove the vertex */
	removed = sortedarray_remove(graph->vertices, v);
	if (removed) {
		data = removed->data;
		vertex_delete(removed);
	}

	return data;
}

void graph1_add_edge(graph1 *graph, vertex *vertex1, vertex *vertex2)
{
	edge *e = edge_create(vertex1, vertex2);
	edge *existing = sortedarray_add(graph->edges, e);
	edge_delete(existing);
}

void graph1_remove_edge(graph1 *graph, vertex *vertex1, vertex *vertex2)
{
	unsigned int i;
	unsigned int removed = 0;

	for (i = 0; i < sortedarray_get_count(graph->edges) && !removed; i++) {
		edge *e = sortedarray_get(graph->edges, i);
		if (e->from == vertex1 && e->to == vertex2) {
			sortedarray_remove_at(graph->edges, i);
			edge_delete(e);
			removed = 1;
		}
	}
}

unsigned int graph1_get_adjacent(const graph1 *graph, const vertex *vertex1, const vertex *vertex2)
{
	unsigned int adjacent = 0;
	unsigned int i;

	for (i = 0; i < sortedarray_get_count(graph->edges) && !adjacent; i++) {
		const edge *e = sortedarray_get(graph->edges, i);
		adjacent = e->from == vertex1 && e->to == vertex2;
	}

	return adjacent;
}

unsigned int graph1_get_neighbour_count(const graph1 * graph, const vertex * vertex)
{
	/* The neighbour count is the count of edges that are from this vertex */
	unsigned int i;
	unsigned int edges = 0;

	for (i = 0; i < sortedarray_get_count(graph->edges); i++) {
		const edge *e = sortedarray_get(graph->edges, i);
		edges += e->from == vertex;
	}

	return edges;
}

unsigned int graph1_get_edge_count(const graph1 * graph)
{
	return sortedarray_get_count(graph->edges);
}

unsigned int graph1_get_vertex_count(const graph1 * graph)
{
	return sortedarray_get_count(graph->vertices);
}

typedef struct {
	const graph1 *graph;
	const vertex *v;
	unsigned int current;
} neighbour_iterator;

static neighbour_iterator *neighbour_iterator_create(const graph1 *graph, const vertex *v)
{
	neighbour_iterator *it = malloc(sizeof(neighbour_iterator));
	if (it) {
		it->graph = graph;
		it->v = v;
		it->current = 0;
	}
	return it;
}

static void neighbour_iterator_delete(neighbour_iterator *it)
{
	free(it);
}

static void *neighbour_iterator_get(neighbour_iterator *it)
{
	vertex *neighbour = NULL;
	for (;it->current < sortedarray_get_count(it->graph->edges) && neighbour == NULL; it->current++) {
		const edge *e = sortedarray_get(it->graph->edges, it->current);
		if (e->from == it->v) {
			neighbour = e->to;
		}	
	}
	return neighbour;
}

iterator *graph1_get_neighbours(const graph1 *graph, const vertex *v)
{
	return iterator_create(neighbour_iterator_create(graph, v), 
		(iterator_getfn)neighbour_iterator_get, (iterator_deletefn)neighbour_iterator_delete);
}

iterator *graph1_get_edges(const graph1 *graph)
{
	return sortedarray_get_iterator(graph->edges);
}

iterator *graph1_get_vertices(const graph1 *graph)
{
	return sortedarray_get_iterator(graph->vertices);
}

This is the header file for a polymorphic vertex type that can be used by several different graph representations (vertex.h):

#ifndef VERTEX_H
#define VERTEX_H

typedef void (*vertex_deletefn)(void *);

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

vertex *vertex_create(const char *name, void *data, void *body, vertex_deletefn del);
void vertex_delete(vertex *v);
int vertex_compare(const vertex *vertex1, const vertex *vertex2);
const char *vertex_get_name(const vertex *v);
void *vertex_get_data(const vertex *v);

#endif /* VERTEX_H */

And this is its implementation (vertex.c):

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

#include <vertex.h>

vertex * vertex_create(const char *name, void *data, void *body, vertex_deletefn del)
{
	vertex *v = malloc(sizeof(vertex));
	if (v) {
		v->name = strdup(name);
		v->data = data;
		v->body = body;
		v->del = del;
	}
	return v;
}

void vertex_delete(vertex *v)
{
	if (v) {
		free(v->name);
		if (v->del) {
			v->del(v->body);
		}
		free(v);
	}
}

int vertex_compare(const vertex *vertex1, const vertex *vertex2)
{
	return strcmp(vertex1->name, vertex2->name);
}

const char * vertex_get_name(const vertex *v)
{
	return v->name;
}

void * vertex_get_data(const vertex *v)
{
	return v->data;
}

This is the header file for the edge type (edge.h):

#ifndef EDGE_H
#define EDGE_H

#include <vertex.h>

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

edge *edge_create(vertex* from, vertex *to);
void edge_delete(edge *e);
int edge_compare(const edge *edge1, const edge *edge2);
const vertex *edge_get_from(const edge * e);
const vertex *edge_get_to(const edge * e);

#endif /* EDGE_H */

And this is the implementation (edge.c):

#include <stdlib.h>

#include <edge.h>

edge *edge_create(vertex* from, vertex *to)
{
	edge *e = malloc(sizeof(edge));
	if (e) {
		e->from = from;
		e->to = to;
	}

	return e;
}

void edge_delete(edge *e) 
{
	free(e);
}

int edge_compare(const edge *edge1, const edge *edge2)
{
	int result = vertex_compare(edge1->from, edge2->from);
	if (result == 0) {
		result = vertex_compare(edge1->to, edge2->to);
	}
	return result;
}

const vertex * edge_get_from(const edge * e)
{
	return e->from;
}

const vertex * edge_get_to(const edge * e)
{
	return e->to;
}

This is the header file for polymorphic iterators (iterator.h):

#ifndef ITERATOR_H
#define ITERATOR_H

typedef void (*iterator_deletefn)(void *);
typedef void *(*iterator_getfn)(void *);

struct iterator {
	void *      body;
	iterator_getfn     get;
	iterator_deletefn  del;
};
typedef struct iterator iterator;

iterator *iterator_create(void *body, iterator_getfn get, iterator_deletefn del);
void iterator_delete(iterator *it);
void *iterator_get(iterator *it);

#endif /* ITERATOR_H */

And this is the implementation (iterator.c):

#include <stdlib.h>

#include <iterator.h>

iterator *iterator_create(void *body, iterator_getfn get, iterator_deletefn del)
{
	iterator *it = malloc(sizeof(iterator));
	if (it) {
		it->body = body;
		it->get = get;
		it->del = del;
	}

	return it;
}

void iterator_delete(iterator *it)
{
	if (it) {
		if (it->del) {
			it->del(it->body);
		}
		free(it);
	}
}

void *iterator_get(iterator *it)
{
	return it->get(it->body);
}

This is the header file for the sorted array iterator (sortedarray-iterator.h):

#ifndef SORTEDARRAY_ITERATOR_H
#define SORTEDARRAY_ITERATOR_H

#include <iterator.h>
#include <sortedarray.h>

iterator *sortedarray_get_iterator(const sortedarray * array);

#endif /* SORTEDARRAY_ITERATOR_H */

And the implementation (sortedarray-iterator.c):

#include <dynarray-iterator.h>

#include <sortedarray-iterator.h>

iterator * sortedarray_get_iterator(const sortedarray * array)
{
	return dynarray_get_iterator(array->array);
}

This is the header file for the dynamic array iterator (dynarray-iterator.h):

#ifndef DYNARRAY_ITERATOR_H
#define DYNARRAY_ITERATOR_H

#include <iterator.h>
#include <dynarray.h>

iterator *dynarray_get_iterator(const dynarray *array);

#endif /* DYNARRAY_ITERATOR_H */

And this is the implementation (dynarray-iterator.c):

#include <stdlib.h>

#include <dynarray-iterator.h>

typedef struct {
	const dynarray *array;
	unsigned int current;
} dynarray_iterator;

static dynarray_iterator *dynarray_iterator_create(const dynarray *array)
{
	dynarray_iterator *it = malloc(sizeof(dynarray_iterator));
	if (it) {
		it->array = array;
		it->current = 0;
	}
	return it;
}

static void dynarray_iterator_delete(dynarray_iterator *it)
{
	free(it);
}

static void *dynarray_iterator_get(dynarray_iterator *it)
{
	void *data = NULL;
	if (it->current < it->array->count) {
		data = dynarray_get(it->array, it->current);
		it->current++;
	}
	return data;
}

iterator *dynarray_get_iterator(const dynarray *array)
{
	return iterator_create(dynarray_iterator_create(array), (iterator_getfn)dynarray_iterator_get, 
		(iterator_deletefn)dynarray_iterator_delete);
}