Sitemap
TDS Archive

An archive of data science, data analytics, data engineering, machine learning, and artificial intelligence writing from the former Towards Data Science Medium publication.

Representing Graph Data Structures

It’s really all about the Edges.

4 min readJan 15, 2020

--

When you’re representing a graph structure G, the vertices, V, are very straight forward to store since they are a set and can be represented directly as such. For instance, for a graph of 5 vertices:

V = {0,1,2,3,4}

Things get a little more interesting when you start storing the Edges, E. Here there are three common structures that you can use represent and navigate the edge set:

  • Edge List
  • Adjacency Matrix
  • Adjacency List

We’re going to take a look at a simple graph and step through each representation of it. We will assess each one according to its Space Complexity and Adjacency Complexity.

But First Some Terminology

  • A Graph G(V, E) is a data structure that is defined by a set of Vertices (V) and a set of Edges (E).
  • Vertex (v) or node is an indivisible point, represented by the lettered components on the example graph below
  • An Edge (vu) connects vertex v and vertex u together.
  • The Degree d(v) of vertex v, is the count of edges connected to it.
  • Space Complexity is shown as Θ(G) and represents how much memory is needed to hold a given graph
  • Adjacency Complexity shown by O(G) is how long it takes to find all the adjacent vertices to a give vertex v.

Edge Lists

Given our graph G with vertex set:

V = {0,1,2,3,4}

Lets now give G some edges to make it a proper graph:

Press enter or click to view image in full size
Fig 1. G, all grown up

The Edge List of G is the literal list of edges where each edge is a list of the vertices it connects, in this case:

E = [[0,1],[0,2],[0,4],[3,4]]

Pros

  • Simple!
  • Great space complexity of Θ(G) = |E|

Cons

  • Adjacency complexity of O(G) = |E|. Here |E| is a poor value. You must look at every single edge in order to rule them all out. In some ways the worst possible score here.

Adjacency Matrices

The Adjacency Matrix of G is the square matrix where each v has a corresponding column and row. If two vertices v, u share an edge then there is a 1 in the corresponding location, otherwise a zero.

Fig 2. Adjacency matrices for three different 4 vertex graphs

Get Jackson Gilkey’s stories in your inbox

Join Medium for free to get updates from this writer.

For our graph G that would be:

G = [[0,1,1,0,1],
[1,0,0,0,0],
[1,0,0,0,0],
[0,0,0,0,1],
[1,0,0,1,0]]

Pros

  • Highly interpretable. IE It's symmetrical unless its a directed graph and you can neatly store edge values in each matrix entry.
  • Decent adjacency complexity of O(G) = |V|. In order to find all vertices adjacent to v, we need to scan their whole row with the adjacency matrix.

Cons

  • Terrible space complexity of Θ(G) = |V|². Here we are storing every possible vertex permutation of length 2, including each vertex paired with itself. This is more than double the maximum vertex set of possible combinations, (|V| choose 2)

Adjacency Lists

The Adjacency List of G is another list of lists. This time instead of listing each individual edge we’ll start off by creating a list of empty lists for each v in G.

E = [[],[],[],[],[]]

Here the index of each list element represents its corresponding vertex. Now we need to go through and add in each vertex’s list of adjacent neighbors.

Press enter or click to view image in full size
Fig 3. Back again!
E = [[1,2,4],[0],[0],[4],[0,3]]

While this is simplest as a list I also find it helpful to think of it as a dictionary where each vertex is a key.

E = {0:[1,2,4], 
1:[0],
2:[0],
3:[4],
4:[0,3]}

Pros:

  • It's like a dictionary!
  • Space complexity of Θ(G) = |V|+ 2|E| We have a list for every vertex and in total these lists will store 2|E| elements since each edge will appear in both vertex lists.
  • Great adjacency complexity. For a given vertex v, O(G) is equal to d(v) the Degree of v. When looking for all adjacent neighbors this is in fact the best possible value here.

Optimal Representation

Choosing the optimal data structure to represent a given graph G is actually dependent on the density of edges within G. This can be roughly summarized as follows.

  • If |E|≈|V| ie there are about as many edges as there are vertices then G is considered Sparse and an adjacency list is preferred.
  • If |E|≈(|V| choose 2) ie is close to the maximum number of edges in G then it is considered Dense and the adjacency matrix is preferred.

Edge Lists are rarely used due to their poor adjacency complexity.

--

Jackson Gilkey
Jackson Gilkey

Written by Jackson Gilkey

Data Scientist. Studied at Flatiron in NYC. Strong interest in Graph Theory, Mapping, GIS, NLP, Non-linear Modeling, Python, Urban Agriculture and Mycology.

TDS Archive
TDS Archive

Published in TDS Archive

An archive of data science, data analytics, data engineering, machine learning, and artificial intelligence writing from the former Towards Data Science Medium publication.