Devin Roché

JavaScript Graphs

A graph is a non-linear data structure. Graphs have nodes and edges. Nodes are the values while the edges connect the values. I like to think of this as a social network. Think of the graph as Facebook, the nodes are people, and the edges are connections. You are a node and will be connected with your friends, who are also nodes. Everyone has a connection with their friends. Almost like one big giant spider web

There are a few different kinds, we are starting with an undirected graph, meaning if I’m connected to you then you are connected to me.

So first we need to create our nodes.

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

Pretty self explainatory but we are creating nodes with a value property and an array of edges.

Next, we need to create our undirected graph class!

class UndirectedGraph {
  constructor() {
    this.vertices = {}
  }
}

Again not much to it, but vertices will reference our node values. We need a way to add nodes to our graph. To do this we can use the following

addNode(value){
  if (!this.vertices[value]) {
    return this.vertices[value] = new Node(value)
  }
}

We don’t want duplicates in our graph so we need to make sure the value doesn’t exist first if it doesn’t then we create a new Node and assign it to its correct vertices.

Now we need a way to form connections! We call these edges, and can be created pretty easily.

addEdge(from, to){
  if (this.vertices[from] && this.vertices[to]) {
    this.vertices[from].edges.push({node: to})
    this.vertices[to].edges.push({node: from})
  }
  return
}

Basically, if both values exist on our graph we can add our “connection” to each nodes.

By now our full code should look like the following,

class UndirectedGraph {
  constructor(){
    this.vertices = {}
  }

  addNode(value){
    if(!this.vertices[value])
      return this.vertices[value] = new Node(value)
  }

  addEdge(from, to){
    if(this.vertices[from] && this.vertices[to]){
      this.vertices[from].edges.push({node: to})
      this.vertices[to].edges.push({node: from})
    }
    return
 }
}

This is how you create undirected graphs!

In a later article I’m going to go over directed + weighted graphs as well.


twitter |github