Why should you know graph data structures and algorithms?

Written by Rijad Pedljak , Software Developer at Softray Solutions

Not interested in graphs? Whether you like them or not, practical use of graph data structures and graph algorithms is all around us. They are powerful, versatile, widely spread and used by everyone, without even knowing it: Google maps uses graphs for building transportation systems, Facebooks friend suggestion uses graph theory (Facebook users are vertices and if they are friends there is an edge running between them), every modelling of social networks, Windows file explorer; you’re even using graph algorithms while reading this — the internet is a collection of hosts and routers connected by various links, for host A to find host B it must find an optimal path through all this mess. Other than the IT world, graphs have very wide usage in linguistics, chemistry, physics, biology and, of course, mathematics.

Graphs in computer science

Number of problems solved by graph theory is countless, but the focus here will be the problems related to computer science and programming. In computer science, a graph is an abstract data type that consists of finite set of vertices together with a set of edges that represent links between vertices.

We use graphs for numerous things, such as representing networks of communication, data organization, computational devices, flow of computation, etc. We can represent website link structures as directed graphs (digraph — graph in which edges have directions) where vertices represent web pages and the directed edges represent links from one page to another.

Implementing a basic social media network using graphs

If you’re still not interested in graphs, let’s see how easy it is to implement a basic social media network with the application of graphs. Since Facebook has this monopoly over social networks, you decide that you want to create a private social network for your company. Thinking logically, like the engineer you are, you can keep things simple and create a Facebook group instead. But also being an engineer, you like a challenge, so you throw that KISS principle out of the window.

First, you need storage for your graph. There are multiple ways you can represent a graph data structure, but you decide to go with a list that will store each person as a key and all their connections as associated values (adjacency list; another commonly used representation is adjacency matrix).

Now that you have the representation, you need to add people somehow when they sign up and store any future connections they may have, so you make users keys on the objects and use an object with edges property to keep a list of their connections.

Now our graph looks something like this:

In practice, you’ll want to store records with unique user id instead of names that couldn’t be overwritten by other users with the same name.

A nice feature to have is a check whether a user already exists in the graph, so we will add a contain method to prevent overwriting of existing users and relationships as the network grows.

Now we need some sort of method to let the users connect with each other by creating friendships (edges). Edges aren’t directed (friendships don’t work that way, otherwise it’s a bad friendship). We end up with something like this:

And now our graph looks like this:

This all looks great, but at some point Jon says “Rijad, who is this Ryan guy, I thought he was your friend?”, and you have no way to remove a connection. So, we need a remove Edge method.

Now Jon can delete Ryan from his friends list. Great. But now Ryan got his feelings hurt and wants to delete his account, but we don’t have support for that. So we need a method to remove a node.

There we go. Even though we lost a potentially valuable user, we were able to implement a basic graph system to keep track of all users and their connections.

Let’s do a time complexity analysis using Big-O notation. The addNode has O(1) complexity, we’re just creating a property on an object so it’s constant time, addEdge is also O(1) since our nodes and edges are represented as properties. RemoveNode is O(n) since we need to iterate over the node edges to remove their existence, removeEdge is O(1) since we can access the properties in constant time and just delete the edges also accessible in constant time. Contains is also O(1) as well as hasEdge method. As we can see, we only have one method which has a non-constant time complexity, therefore we can conclude that graphs really are powerful for this purpose.

Still not interested in learning graphs?

If you enjoyed reading this, click on the clap button so others can find this post.