Javascript graph data structure

Posted on | by Prashant Yadav

Posted in ,

Data structures are the building blocks of computer programming, they are used to store the data in organized way and use it to implement algorithms (programs) while solving problems.

In this tutorial we are going to explore one of the most important data structure, Graph and implement it in Javascript.

It is one of the most widely used data structure in programming, mathematics, geography, physics, and other related fields.

What is graph?.

What is the first thing that comes to your mind when you hear this term?, Well if you are an Indian like me then probably you will be thinking of conventional graphs which are used to model data, (what we used to do in mathematics and exams), (also called as charts), But in computer science graph is completely different concept.

In programming, (mathematically speaking )a graph is a common data structure that consists of a finite set of nodes (or vertices) and edges.

The edges connect the nodes (or vertices) to form a network, it can be either uni-directional or bi-directional and may contain certain values which are the required cost to travel from one vertex to other.

Thing of vertex as a pair (x, y) where vertex x is connected to vertex y. Assuming this we can create implement the graph data structure.

Imagine google maps, they are graphs, connecting one place to another. They are also weighted graphs which helps us to decide the long and short routes (Distance to reach from SRC to DESTINATION), thanks to that you reach faster to destinations.

Or Imagine rail networks they are also giant graph, connecting cities with railways and tracks. Roadways are graph, ship routes, air routes, etc are all graphs.

Your are surrounded by graphs, your facebook mutual friend recommendation is also done with the help of graphs.

Graph terminology and their types

In order to better understand graphs and solve complex problems with them, one should be thoroughly familiar with key terms to develop a grasp of how different properties interact with each other relationally.

Graph Data structure in Javascript

Degree of vertex: The total number of edges connected to a vertex. There are two types of degrees:

  1. In-Degree: The total number connected to a vertex.
  2. Out-Degree: The total of outgoing edges connected to a vertex.

Adjacency: Two vertices are said to be adjacent if there is an edge connecting them directly.

Parallel Edges: Two undirected edges are parallel​ if they have the same end vertices. Two directed edges are parallel if they have the same origin and destination.

Self Loop: This occurs when an edge starts and ends on the same vertex.

Isolated vertex: A vertex with zero degree, meaning it is not an endpoint of an edge.

Type of graphs

Uni-directional

In uni-directional or directed graph, the edges are unidirectional; for example, with the pair (0,1), it means there exists an edge from vertex 0 towards vertex 1, and the only way to traverse is to go from 0 to 1.

This changes to the number of edges that can exist in the graph. For a directed graph with n vertices, the minimum number of edges that can connect a vertex with every other vertex is nβˆ’1. So, if you have n vertices, then the possible edges is nβˆ—(nβˆ’1).

directed graph in javascript

Bi-directional

In bi-directional or un-directed graph, the edges are bi-directional by default; for example, with the pair (0,1), it means there exists an edge between vertex 0 and 1 without any specific direction. You can go from vertex 0 to 1, or vice versa.

The maximum possible edges of a graph with n vertices will be all possible pairs of vertices. There are C(n,2) possible pairs of vertices, solving by binomial coefficients gives us (n * (n-1)) / 2 gmaximum possible edges in an undirected graph.

un-directed graph

Representing graphs

A graph can be represented in two ways Adjacency List and Adjacency Matrix.

Adjacency Matrix

The adjacency matrix is a two-dimensional matrix where each cell can contain a 0 or a 1.​ The row and column headings represent the source and destination vertices respectively. If a cell contains 1, that means there’s an edge between the corresponding vertices. Edge operations are performed in constant time, as we only need to manipulate the value in the particular cell.

Adjacency Matrix for directed graph

Adjacency List

In an Adjacency List, a map of arrays is used to store edges between two vertices. The size of the map is equal to the number of vertices. Each key in this map represents a specific vertex in the graph. If a new vertex is added to the graph, it is simply added to the map as well.

Adjacency list for directed graph

Both representations are suitable for different situations. If your model frequently manipulates vertices, the adjacency list is a better choice. If you are dealing primarily with edges, the adjacency matrix is the more efficient approach.

Implementing graph data structure in Javascript

The implementation below will be based on the Adjacency List representation.

As we know, the Graph class consists of two data members:

  • The total number of vertices in the graph
  • A map of arrays to store adjacent vertices

We can also use an array of linked list to represent the graph but it has limitations, in this the vertices and edges has to be numeric always, also removing the vertices from it takes (V + E) because after removing any entry we have to re-index the array.

Using hashmap with linkedlist or array is much better because we can use either number or character as the vertices or edges, also delete operation takes O(E) time, where E is the no of edges.

Following is the list of operations we are going to perform.

  • Graph class: Creates graph with given nodes.
  • Add: adds a new node to the graph.
  • Print: prints the graph.
  • Remove: removes the node.

Un-weighted graph

Directed graph

/*Directed graph*/

function Edge(src, dest){
  this.src = src;
  this.dest = dest;
}

const Graph = function(edges){
  // A list of lists to represent an adjacency list
  let adj = new Map();

  // add edges to the directed graph
  for (let current of edges) {
    // allocate new node in adjacency list from src to dest
    const {src, dest} = current;
    if(adj.has(src)){
      adj.get(src).push(dest);
    }else{
      adj.set(src, [dest]);  
    }
  }
  
  this.add = function(edge) {
    const {src, dest} = edge;
    if(adj.has(src)){
      adj.get(src).push(dest);
    }else{
      adj.set(src, [dest]);  
    }
  }
  
  this.remove = function(edge) {
    const {src, dest} = edge;
    let srcList = adj.get(src);
    srcList = srcList.filter(e => e !== dest);
    
    if(srcList.length === 0){
      adj.delete(src);
    }else{
      adj.set(src, srcList);
    }
 
    return true;
  }
  
  this.print = function() {
    let n = adj.size;
 
    for (let src of adj.keys()) {
      // print current vertex and all its neighboring vertices
      let str = "";
      for (let dest of adj.get(src)) {
        str += "(" + src + " β€”β€”> " + dest + ")";
      }
      console.log(str);
    }
  }

  //Return graph
  this.getList = () => adj;
}

Input:
const arr = [new Edge(0, 1), new Edge(1, 2),
                new Edge(2, 0), new Edge(2, 1), new Edge(3, 2),
                new Edge(4, 5), new Edge(5, 4)];

const graph = new Graph(arr);
graph.add(new Edge('c', 'd'));
graph.print();

Output:
"(0 β€”β€”> 1)"
"(1 β€”β€”> 2)"
"(2 β€”β€”> 0)(2 β€”β€”> 1)"
"(3 β€”β€”> 2)"
"(4 β€”β€”> 5)"
"(5 β€”β€”> 4)"
"(c β€”β€”> d)"

Undirected graph

As we now that in undirected graph we go from src to destination and vice versa, we can do the same in the implementation.

function Edge(src, dest){
  this.src = src;
  this.dest = dest;
}

const Graph = function(edges){
  // A list of lists to represent an adjacency list
  let adj = new Map();

  // add edges to the directed graph
  for (let current of edges) {
    // allocate new node in adjacency list from src to dest
    const {src, dest} = current;
    if(adj.has(src)){
      adj.get(src).push(dest);
    }else{
      adj.set(src, [dest]);  
    }
    
    // uncomment next lines for undirected graph
    // allocate new node in adjacency list from dest to src
    if(adj.has(dest)){
      adj.get(dest).push(src);
    }else{
      adj.set(dest, [src]);  
    }
  }
  
  this.add = function(edge) {
    const {src, dest} = edge;
    if(adj.has(src)){
      adj.get(src).push(dest);
    }else{
      adj.set(src, [dest]);  
    }

    // uncomment next lines for undirected graph
    // allocate new node in adjacency list from dest to src
    if(adj.has(dest)){
      adj.get(dest).push(src);
    }else{
      adj.set(dest, [src]); 
    }
    
  }
  
  this.remove = function(edge) {
    const {src, dest} = edge;
    let srcList = adj.get(src);
    srcList = srcList.filter(e => e !== dest);
    
    if(srcList.length === 0){
      adj.delete(src);
    }else{
      adj.set(src, srcList);
    }

    // uncomment next lines for undirected graph
     let destList = adj.get(dest);
     destList = destList.filter(e => e !== src);
    
     if(destList.length === 0){
       adj.delete(dest);
     }else{
       adj.set(dest, destList);
     }
    
    return true;
  }
  
  this.print = function() {
    let n = adj.size;
 
    for (let src of adj.keys()) {
      // print current vertex and all its neighboring vertices
      let str = "";
      for (let dest of adj.get(src)) {
        str += "(" + src + " β€”β€”> " + dest + ")";
      }
      console.log(str);
    }
  }

  //Return graph
  this.getList = () => adj;
}

Input:
const arr = [new Edge(0, 1), new Edge(2, 0), 
             new Edge(2, 1), new Edge(3, 2),
             new Edge(4, 5), new Edge(5, 4)];

const graph = new Graph(arr);
graph.add(new Edge('c', 'd'));
graph.print();

Output:
"(0 β€”β€”> 1)(0 β€”β€”> 2)"
"(1 β€”β€”> 0)(1 β€”β€”> 2)"
"(2 β€”β€”> 0)(2 β€”β€”> 1)(2 β€”β€”> 3)"
"(3 β€”β€”> 2)"
"(4 β€”β€”> 5)(4 β€”β€”> 5)"
"(5 β€”β€”> 4)(5 β€”β€”> 4)"
"(c β€”β€”> d)"
"(d β€”β€”> c)"

Weighted graph data structure in Javascript

Un-directed and directed combined.

/*
Weigthed driected and un-directed graph
*/
//Edge
function Edge(src, dest, weight){
  this.src = src;
  this.dest = dest;
  this.weight = weight;
}

// A class to store adjacency list nodes
function Node(value, weight) { 
  this.value = value;
  this.weight = weight;
      
  this.toString = function() {
    return this.value + " (" + this.weight + ")";
  }
}

// A class to represent a graph object
const Graph = function(edges) {
  // A list of lists to represent an adjacency list
  let adj = new Map();
 
  // add edges to the directed graph
  for (let e of edges) {
    const {src, dest, weight} = e;
    // allocate new node in adjacency list from src to dest
    if(adj.has(src)){
      adj.get(src).push(new Node(dest, weight));
    }else{
      adj.set(src, [new Node(dest, weight)]);
    }

    // uncomment next lines for undirected graph
    // allocate new node in adjacency list from dest to src
    
    // if(adj.has(dest)){
    //   adj.get(dest).push(new Node(src, weight));
    // }else{
    //   adj.set(dest, [new Node(src, weight)]);
    // }
  }
  
  this.add = function(edge){
    const {src, dest, weight} = edge;
    // allocate new node in adjacency list from src to dest
    if(adj.has(src)){
      adj.get(src).push(new Node(dest, weight));
    }else{
      adj.set(src, [new Node(dest, weight)]);
    }
    
    
    // uncomment next lines for undirected graph
    // allocate new node in adjacency list from dest to src
    
    // if(adj.has(dest)){
    //   adj.get(dest).push(new Node(src, weight));
    // }else{
    //   adj.set(dest, [new Node(src, weight)]);
    // }
  }

  this.remove = function(edge) {
    const {src, dest} = edge;
    let srcList = adj.get(src);
    srcList = srcList.filter(e => e !== dest);
    
    if(srcList.length === 0){
      adj.delete(src);
    }else{
      adj.set(src, srcList);
    }

    // uncomment next lines for undirected graph
//     let destList = adj.get(dest);
//     destList = destList.filter(e => e !== src);
    
//     if(destList.length === 0){
//       adj.delete(dest);
//     }else{
//       adj.set(dest, destList);
//     }
    
    return true;
  }
  
    
  // Function to print adjacency list representation of a graph
  this.print = function(){
    let n = adj.size;
 
    for (let src of adj.keys()) {
      // print current vertex and all its neighboring vertices
      let str = "";
      for (let edge of adj.get(src)) {
        str += "(" + src + " β€”β€”> " + edge + ")";
      }
      console.log(str);
    }
  }

  //Return graph
  this.getList = () => adj;
}

Input:
const arr = [new Edge(0, 1, 6), new Edge(1, 2, 7),
                new Edge(2, 0, 5), new Edge(2, 1, 4),
                new Edge(3, 2, 10), new Edge(4, 5, 1),
                new Edge(5, 4, 3)];
const graph = new Graph(arr);
graph.add(new Edge('a', 'b', 122));
graph.print();

Output:
"(0 β€”β€”> 1 (6))"
"(1 β€”β€”> 2 (7))"
"(2 β€”β€”> 0 (5))(2 β€”β€”> 1 (4))"
"(3 β€”β€”> 2 (10))"
"(4 β€”β€”> 5 (1))"
"(5 β€”β€”> 4 (3))"
"(a β€”β€”> b (122))"

Time complexity

# Insert Search Delete
Average Θ(1) Θ(E) Θ(E)
Worst O(1) O(E) O(E)

Space complexity

# Space
Worst O(V + E)

Introducing frontend system design course πŸ”₯ where you will learn to design frontend of 30+ applications.