Mathematically, a graph is a set of vertices and edges, thus a graph G is usually written as G(V,E). Besides linking vertices in the graph, edges can also carry a specific value which may be interpreted as cost, weight, distance etc.
In computer science, we’re interested in the (abstract) data structure used to implement the graph mathematical concept. Let’s first discuss the basic elements in a graph – vertices and edges:
typedef struct vertex
{
unsigned long id;
int status;
double x,y;
void* data;
} vertex;
Vertices should be able to hold any kind of data, so we’ll just throw in a void pointer for that. Other than that we have an id, status (marked or unmarked – more on that later) and 2D coordinates so we can draw the vertices somewhere.
typedef struct edge
{
vertex* from, *to;
int cost;
} edge;
Edges consist of just pointers to the vertices they link and an optional value used as weight, distance, cost etc. Strictly speaking we could use a void pointer for that value as well, as long as we also defined a comparison function. But let’s save the hassle and just use an integer instead – most algorithms will be fine with that.
Those two structs together with their allocation and compare functions comprise the basic code we need to start building a graph. Full code can be found in graphs/graph_ve.c .
Now that we have a way to represent edges and vertices, we need a convenient way to represent the graph itself. Namely, we need to be able to quickly and conveniently identify, add and remove vertices and edges. There are two traditional approaches to do that, each with its own appropriate usages: adjacency matrix and adjacency list.
Adjacency matrices use a matrix to represent edges (and possibly the edge’s value), e.g. if graph G has v vertices, matrix E(v x v) represents G’s edges, each matrix element representing if the edge exists and if so what value it has. This is a fast and straightforward approach to representing edges, but the fixed n² space requirement is very bad if we have a sparse graph, which unfortunately is often the case.
Adjacency lists on the other hand use lists to represent edges. Each vertex has it’s own list holding pointers to all of its neighbors. In its simplest form, a graph G(V,E) will have an |V| sized array with lists containing only integers (corresponding to the vertex id) – adj_list[a] would contain the ids to every neighbor of vertex v with id=a. We’re using linked lists with our edge struct.
Adding and identifying vertices is trivial: vertex v with id=i is located at vertices[i]. Adding edges is also trivial (adding edge* to the linked list). If we have an undirected graph, we add 2 edges instead, one at adj_list[vertex_from] and one at adj_list[vertex_to].
Testing code can be found in the test folder together with some drawing functions that print the graph with our BurgerGFX utility.
/*
File: al_graph.c
Dependencies: linked_list.c, graph_ve.c
This is a graph implementation with adjacency lists.
A graph with nv vertices will have nv (readable) adjacency lists,
located at the adj_list array (double pointer to linked list).
adj_list[idx] contains all edges originating from vertex v with
v->id = idx. If G is an undirected graph, adding an edge from
vertex vf to vertex vt will add equivalent edges to the both lists,
i.e. adj_list[vf->id] and adj_list[vt->id].
Copyright (c) 2014 Leonardo Brito <lbrito@gmail.com>
This software is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License along
with this program; if not, write the Free Software Foundation, Inc., 51
Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
*/
#define DIRECTED 0
#define UNDIRECTED 1
#include "graph_ve.c"
#include "../data_structures/linked_list.c"
typedef struct graph
{
vertex** vertices;
int directed;
unsigned long max_vertices;
unsigned long n_edges;
unsigned long nv;
linked_list** adj_list;
void (*printvert) (void*);
} graph;
typedef struct edge_iter
{
graph* g;
vertex* origin;
element* head;
int idx, length;
} edge_iter;
/**
* @brief
*
* @param [in] n_vertices max n vertices
* @param [in] directed DIRECTED or UNDIRECTED graph
* @return
*/
graph* new_graph(int n_vertices, int directed)
{
graph* g_p = malloc(sizeof(graph));
g_p->directed = directed;
g_p->max_vertices = n_vertices;
g_p->vertices = malloc(sizeof(vertex*)*g_p->max_vertices);
g_p->nv = 0;
g_p->n_edges = 0;
g_p->adj_list = malloc(sizeof(linked_list*)*g_p->max_vertices);
int i=0;
for (;i<g_p->max_vertices;i++) g_p->adj_list[i] = new_list(compare_e);
return g_p;
}
/**
* @brief Edge iterator: all neighbors of vertex 'from'
*
* @param [in] g
* @param [in] from
* @return
*/
edge_iter* new_edge_it(graph* g, vertex* from)
{
edge_iter* it = malloc(sizeof(edge_iter));
it->g = g;
it->origin = from;
it->head = g->adj_list[from->id]->head->next;
it->idx = 0;
it->length = g->adj_list[from->id]->size;
return it;
}
/**
* @brief Next edge in list
*
* @param [in] it
* @return
*/
edge* next_edge(edge_iter* it)
{
if (++it->idx < it->length)
{
edge* e = (edge*) it->head->data;
it->head = it->head->next;
return e;
}
else return NULL;
}
/**
* @brief Get edge from adjacency list
*
* @param [in] g
* @param [in] from
* @param [in] to
* @return
*/
edge* get_edge(graph* g, int from, int to)
{
element* e = g->adj_list[from]->head;
while ((e=e->next) != NULL) if (((((edge*) e->data)->to)->id) == to) return ((edge*) e->data);
return NULL;
}
/**
* @brief Get vertex from array @idx
*
* @param [in] g
* @param [in] idx
* @return
*/
vertex* get_vertex(graph* g, int idx)
{
if (idx>g->nv) return NULL;
return g->vertices[idx];
}
/**
* @brief Add vertex to graph
*
* @param [in] g
* @param [in] data vertex data
* @return created vertex
*/
vertex* add_vertex(graph* g, void* data)
{
vertex* v;
int pos = g->nv;
if (pos < g->max_vertices)
{
v = (g->vertices[pos] = new_vertex(pos, data));
add((g->adj_list[pos]), NULL); //prepare adjlist
g->nv++;
}
else return NULL;
return v;
}
/**
* @brief Add edge to graph
*
* @param [in] g
* @param [in] vf
* @param [in] vt
* @param [in] cost
* @return
*/
void add_edge(graph* g, vertex* vf, vertex* vt, int cost)
{
add((g->adj_list[vf->id]), new_edge(vf,vt,cost));
if (g->directed == UNDIRECTED) add((g->adj_list[vt->id]), new_edge(vt,vf,cost));
}
/**
* @brief Get number of vertices in graph
*
* @param [in] g
* @return
*/
int get_nv(graph* g)
{
return g->nv;
}
/**
* @brief Visit vertex @idx
*
* @param [in] g
* @param [in] idx
* @return
*/
int visit_vert(graph* g, int idx)
{
return visit(g->vertices[idx]);
}
CodeDeposit 