Graphs

Graphs can be used to represent almost any relationship: from road networks, to social relationships, to electronic circuits. 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 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.

Figure: A graph

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 .

[2, P. 248]

Graph properties

Different graph properties affect the data structure used to represent them 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].

Figure: An undirected graph and a directed graph

Directed graphs are common when representing roads, which are often one-way only [1, P. 146].

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

Figure: A weighted graph

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

Figure: A non-simple graph with a self-loop and multiple edges

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 lists

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

Figure: A graph and its adjacency matrix

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];
}

[2, P. 249]

out_edges and 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;

[1, P. 153]

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

Figure: A graph and its adjacency list

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