Graph Traversal in JavaScript

November 02, 2014

Part 2- Async graph traversal

What is a graph?

To use a simplistic definition that suites the purpose of this post- A graph is common data structure where nodes can be connected to one or many other nodes. This could probably best be understood with an example. Take for example LinkedIn. Bob works at Acme together with Tom. Bob connects with Tom on LinkedIn. They now have an equal relationship- Tom is connected to Bob just like Bob is connected to Tom. Additionally Bob connects to his old college roommate Dan who works at ShopRite. Dan, however has never met Tom and they have no connection. Tom starts getting into it, and connects with his coworker at ShopRite, Max. Max already has a connection to his old girlfriend Eve. Eve, happens to be Dan's cousin and is connected to him. Eve is also connected to her former roommate Sue.

If that sounds complex it can more easily visualized like in the graph below.

What does it mean to traverse?

Let's say that Bob now wants to find who everyone in his network is, no matter how distantly they are connected. In order to do that we would need to visit every person he is connected and check who they are connected to, and check who they are connected and so on and so on... If Bob would want to find a person in his network that works at a Piggly Wigglies that would require a graph search, but here Bob just wants a list of names. That is called Graph Traversal since we need to traverse the whole graph.

One implementation

Assume that each member (node) is a simple object with three properties:

var bob = {
 //Member's name
 name : 'Bob',
 //Member's unique id
 id : 321456,
 //id's of the members he is connected to
 connections: [23421, 99221556]
};

All of our members are stored in plain-old key/value map JavaScript object. The key is the member's id and the value is the member object.

var allMembers = {
  321456 : bob
  //etc
};

I went out of my way to try to make each code line short so it can look normal on mobile.


function traverseGraph(memberId, allMembers){
 var visitedIds = {}; //A
 var queue = allMembers[memberId].connections; //B
 while(queue && queue.length > 0){ //C
  var memberId = queue.shift(); //D
  if(!visitedIds[memberId]){ //E
   var member = allMembers[memberId];
   visitedIds[memberId] = member.name; //F
   var nextIds = member.connections; //G
   var len = nextIds.length;
   for(var i = 0; i < len; i++){ //H
    var nextId = nextIds[i];
    if(!visitedIds[nextId]
       && queue.indexOf(nextId) < 0){ //I
     queue.push(nextId); //J
    }
   }
  }
 }
 //K
 var names = Object.keys(obj).map(function (key) {
  return obj[key];
 });
 return names; //L
}

A: keeps tracks of nodes that we have already traversed

B: initialize the queue with the first node we are going to traverse

C: loop until we've traversed the whole graph

D: take the first item out of our queue

E: have we NOT gone down this route already

F: we are now going down it- so add it to the list of visited

G: get the next node associated ids

H: loop through this nodes associated nodes

I: have we NOT gone down this route already and not already in the queue

J: add it to the queue

K: Pulls the values from a map- taken directly from this Answer on Stackoverflow http://stackoverflow.com/a/16643074/189976

L: list of all the nodes that we've been to already

Writings