The fancy way to describe a graph | Wikipedia

Let’s Learn: Graph Data Structure

A naive way to look smart

While trying to understanding programming concepts better, one data structure kept coming up either by name or by description. From asking my mentor what he was working on ( some sort of NLP thing ) to wondering how I can create connections between data for my twitter sentiment bot, the graph data structure seemed to be the golden standard for how to structure the data for my worker to “learn” by itself. But what in the world is it?

Note: This is a very basic understanding/explanation of what a graph is and how/why we use it. If you find any errors or misconceptions in this text or the code, PLEASE tell me! And don’t take this article to the bank. I am not sure it’s worth the trip.

A graph is basically a grouping of data that have some sort of connection to each other. Wikipedia talks about edges,nodes, vertices. A whole lot of buzz words that this developer couldn’t grok just by reading. So instead, let’s create a problem that a graph will solve and how we can use these terms to then describe the problem in relation to the graph data structure.

The Problem

We have data points that are connected to each other by different amounts of weights. To put another way, we have a list of people that are either acquaintances, friends, or best friends with other people in the list. We want a way to be able to store the relations between the people in a way that will lend itself for searching for friends of friends or best-friends of best-friends of acquaintances.

We can think of each person as a node on the graph. These nodes or vertices have connections or edges with other nodes or no edges at all. The following image is a decent representation of what we are trying to build:

http://homes.soic.indiana.edu/classes/spring2016/csci/c343-yye/undirectedgraph1.png

Each circle we can imagine as being a person and the numbers are how those people are related. In our structure, we are going to have 1 or 2 numbers per edge ( the line between the circles ) because we want to know how vertex 1 is related to vertex 6 along with how 6 is related 1.

All of this making sense so far? Good! Let’s get into the code.

I figured that the first thing we are going to need is the Node data structure, since that is what our Graph data structure will be composed of. We are going to be using all the fancy cool ES6/7/8/9 stuff that we can so you will need to either use an environment that understands it or use babel to make it work in your current environment. At the end of this article you will find a link to the github repo that has a .babelrc file that makes this code work in node 7.4.0 and you can tweak it how you need it. Finally, onto the code.

Our Node class will take in some sort of data ( any type here since who knows how we will use this in the future ) and will also need a way to keep track of any edges or connections to other nodes that it has. What I came up with was this:

class Node {
  constructor(data = {}){
    this.data = data
    this.edges = []  
  }
}

You will notice that we are not copying the data but rather just keeping a reference to it. That means that if you pass in a non-primitive and you change that value elsewhere, it will also be changed here. We have a default value just because I hate errors that say ‘data is not defined’ or the like so we have an empty object as default. We also have an empty list of edges that we need to figure out a way to add to. Let’s work on that next.

To add an edge from this node to another, we will need to know two things: a node to connect to and the weight of the connection/edge. The first pass of this method looked like this:

addEdge = (node,weight = 1) => this.edges.push({node,weight})

And this works but sometimes we might try to add an edge to something that is already connected. So let’s add a little more logic here just so we can handle that when we inevitably mess up using this abstraction. What we want to do is that if we try to run addEdge and pass in a node that we already have a connection to, we want to actually updateEdge instead of addEdge. Let’s write that method before adding it to addEdge:

updateEdge = (node, newWeight = 1) => {
 const edge = this.edges.find(({node: n}) => n === node)
 if(edge){
  edge.weight = newWeight
 }else {
  this.addEdge(node,newWeight)
 }
}

Since this.edges is an array, we can use the find method on the array to, well, find the edge if it exists. If it does exist, we just want to update the weight of that edge. If it doesn’t exist, we want to addEdge with it. Now we use this inside of our addEdge function and it ended up looking like this when done:

addEdge = (node: Node, weight: number = 1) => {
 const index = this.edges.findIndex(({node: n}) => n === node)
 if(~index){
  this.updateEdge(node,weight)
 }else {
  this.edges.push({node,weight})
 }
}

We use the ~ because we are fancy and want to look cool. Basically it is saying if index >= 0 but with the bitwise not operator instead. Now we have two methods on the node: addEdge and updateEdge which marks two of our specs out.

Now we need a way for us to remove an edge between this node and another one. First we need to find out if we have it and then remove it from this.edges array. Something simple will work:

removeEdge = (node) => {
 const index = this.edges.findIndex(({node: n}) => n === node)
 if(~index){
  this.edges.splice(index,1)
 }
}

This, just like before, checks to see if our index is a valid index and if it is, we remove that item from the array use the splice method. All that is left is for us to add a few utility functions to the node object like being able to see if it is connectedTo a specific node, a way to find a specific node, and then a way to get the weightTo a specific node. The final Node class looks like this ( with flow types ):

Now that we have met the specs for what a single node should be able to do, let’s work on the actual graph data structure.

We are not going to be implementing breadth-first or depth-first search in this iteration but should be able to do so in the future. All we are worried about is matching the specs that wikipedia gave us.

First, we want to be able to construct the Graph given a root node. Let’s start there:

class Graph {
  constructor(root = new Node()){
    this.root = root instanceof Node ? root : new Node(root)
    this.nodes = [this.root]  
  }
}

We pass in some data that will either be a Node or we will turn it into a Node. Then we add that root element to our nodes list. Now let’s think about the methods that this class needs:

1. It needs to be able to connect two nodes and add them to this.nodes list if they are not already.
2. It needs to be able to update the weight of an edge between nodes.
3. It needs to be able to know if it already contains a Node or not.
4. It needs to be able to remove a Node from the graph and also remove any edges to that node that other nodes might have.
5. It needs to be able to find the cost of an edge.

Instead of going method by method like we did above, here’s the finished product:

And bam! There we have it. We have the basic structure of a graph that seems to meet the requirements that wikipedia says a graph data structure should meet. We have not added any sort of ‘Find friends of friends’ but with a little thinking making the algorithms for that should be a cake walk. Maybe that is what I will do for our next Let’s Learn!

As promised, here is the github repo of this code and as I said above, PLEASE let me know how we can make this better! Maybe you have a great graph structure that you use that you think I can learn from? Maybe you’re a real CS person and can point out all the flaws of my code. Respond below or make some PRs/Issues on the github repo! Let’s Learn together!