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

1. Introduction
2. Graph properties
   1. Undirected vs directed
   2. Weighted vs unweighted
   3. Simple vs non-simple
   4. Sparse vs dense
   5. Cyclic vs acyclic
   6. Labelled vs unlabelled
3. Representing a graph
   1. Adjacency matrix
   2. Adjacency list
4. References

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:

[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)$:

• Adjacency matrix
• Adjacency list

Adjacency matrix

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.

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;

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