# 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.

## Table of contents

## Introduction

A graph consists of a set of vertices and a set of edges [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 () is incident to the vertices and .*

Typical graph operations are:

operation | description |
---|---|

`add_edge(x,y)` | Add the edge to . |

`remove_edge(x,y)` | Remove the edge from . |

`has_edge(x,y)` | Check if edge . |

`out_edges(x)` | Return a List of all integers such that . |

`in_edges(x)` | Return a List of all integers such that . |

## 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 is undirected if an edge in set means that is also in set . 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 :

- Adjacency matrix
- Adjacency list

### Adjacency matrix

An **adjacency matrix** is an x matrix , where is the number of vertices.

if is an edge of , and if it isn’t [1, P. 151].

Common operations like `add_edge()`

, `remove_edge()`

, and `has_edge()`

are 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 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.

### Adjacency list

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;
```

A directed edge is represented as a `edgenode`

in ’s adjacency list (at `g->edges[x]`

). An undirected edge appears twice, once in ’s list as , and once in ’s list as [1, P. 153].

The following code initializes an adjacency list with 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] S. Skiena,
*The Algorithm Design Manual*, 2nd ed. Springer, 2008. - [2] P. Morin,
*Open Data Structures*, 1st ed. AU Press, 2013.