# Graphs

Graphs can be used to represent almost any relationship: from road networks, to social relationships, to module dependencies. Many algorithmic problems can be solved by modelling data as a graph.

## Introduction

A graph $G=(V,E)$ consists of a set of vertices $V$ and a set of edges $E$ [1, P. 145].

A vertex is a node in a graph. An edge represents a path between two vertices.

The degree of a vertex is the number of edges that are incident to the vertex [1, P. 150].

Definition: an edge ($u,v$) is incident to the vertices $u$ and $v$.

Typical graph operations are:

operation description
add_edge(x,y) Add the edge $(x,y)$ to $E$.
remove_edge(x,y) Remove the edge $(x,y)$ from $E$.
has_edge(x,y) Check if edge $(x,y)\in E$.
out_edges(x) Return a List of all integers $y$ such that $(x,y)\in E$.
in_edges(x) Return a List of all integers $y$ such that $(y,x)\in E$.

[2, P. 248]

## Graph properties

Graph properties affect the data structure used to represent the graph and the algorithms available to interact with them.

### Undirected vs directed

A graph $G=(V,E)$ is undirected if an edge $(x,y)$ in set $E$ means that $(x,y)$ is also in set $E$. If this is not the case, then the graph is a directed graph [1, P. 146].

Directed graphs are common when representing dependencies, which have a parent-child relationship.

### Weighted vs unweighted

In a weighted graph each edge is assigned a value (a weight). For example, the edge in a road network might be assigned a cost for drive time [1, P. 146].

In an unweighted graph there is no value associated with an edge [1, P. 147].

### Simple vs non-simple

A simple graph is a graph without self-loops or multiple edges [1, P. 147].

A non-simple graph can contain these types of edges [1, P. 147].

### Sparse vs dense

A graph is sparse if only a small number of the possible vertex pairs have edges defined between them.

A dense graph is a graph where lots of the possible vertex pairs have edges defined between them [1, P. 148].

Dense graphs typically have a quadratic number of edges [1, P. 148].

### Cyclic vs acyclic

Cyclic graphs contain cycles, Acyclic graphs don’t [1, P. 148].

Trees are acyclic graphs [1, P. 148].

### Labelled vs unlabelled

In a labelled graph, each vertex is assigned a unique name. In an unlabelled graph, vertices do not have an associated name [1, P. 149].

## Representing a graph

There are two common ways to represent a graph $G=(V,E)$:

An adjacency matrix is an $n$x$n$ matrix $M$, where $n$ is the number of vertices.

$M[x, y] = 1$ if $(x, y)$ is an edge of $G$, and $0$ if it isn’t [1, P. 151].

Common operations like add_edge(), remove_edge(), and has_edge() are $O(1)$ operations:

void add_edge(int x, int y) {
a[x][y] = 1;
}

void remove_edge(int x, int y) {
a[x][y] = 0;
}

bool has_edge(int ix, int y) {
return a[x][y];
}


Methods returning edges for a given node, e.g. out_edges()/in_edges(), are $O(n)$ operations. An entire row/column must be checked to find the edges.

Another problem with adjacency matrices is that they quickly grow large. For this reason they are often impractical.

An adjacency list is a data structure that uses an array of lists to store the edges of vertices.

Adjacency lists are more efficient at representing sparse graphs than adjacency matrices [1, P. 152].

An adjacency list can be represented with a graph struct and an edgenode struct. Each vertex is assigned a unique identifier from 1 to nvertices. The edges on a vertex x are included as a linked list of edgenodes starting at the edgenode at nvertices[x] [1, P. 153]:

const int MAXV = 1000;

typedef struct {
int y;
int weight;
struct edgenode *next;
} edgenode;

typedef struct {
edgenode *edges[MAXV+1];
int degree[MAXV+1];
int nvertices;
bool directed;
} graph;


[1, P. 153]

A directed edge $(x, y)$ is represented as a $y$ edgenode in $x$’s adjacency list (at g->edges[x]). An undirected edge appears twice, once in $x$’s list as $y$, and once in $y$’s list as $x$ [1, P. 153].

The following code initializes an adjacency list with $m$ vertices:

void initialize_graph(graph *g, bool directed, int m) {
int i;
int x;
int y;

g->nvertices = n;
g->nedges = m;
g->directed = directed;

for (i=1; i <= m; i++) {
g->degree[i] = 0;
}

for (i=1; i <= m; i++) {
g->edges[i] = NULL;
}
}


Edges can be added from a 2D array:


int example_edges[4][2] = { {1, 2}, {1, 4}, {1, 3}, {3, 4} };

void add_edges(graph *g, bool directed, int m, int edges[][2]) {
int x;
int y;

for (int i = 0; i < m; i++) {
x = edges[i][0];
y = edges[i][1];
insert_edge(g, x, y, directed);
}
}

void insert_edge(graph *g, int x, int y, bool directed) {
edgenode *p;
p = malloc(sizeof(edgenode));
p->weight = 0;
p->y = y;
p->next = g->edges[x];
g->edges[x] = p;
g->degree[x]++;

if (directed == false) {
insert_edge(g, y, x, true);
} else {
g->nedges++;
}
}


## References

1. [1] S. Skiena, The Algorithm Design Manual, 2nd ed. Springer, 2008.
2. [2] P. Morin, Open Data Structures, 1st ed. AU Press, 2013.