Graphs understanding in JS

Graphs data structure, terminologies, usages and code examples

What are graphs

Finite set of nodes and the nodes’s connections

Uses of graphs

social networks
locaiton/mapping
routing
recommendation engine

Terminology

vertex -> node
edge -> connection between nodes
weighted/unweighted -> values assigned to distances between vertices
directed/undirected -> directions assigned to distanced between vertices

undirected - a <-> b / a is connected to b and b is connected to a (2-way) directed - a -> b / a is connected to b but b is not connected to a (1-way)

weighted graph - edges have values / for example distances between 2 vertices can be the values. Google maps unweighted graph -edges have no values

Storing/representing graphs in code

Using an adjacency matrix

2d matrix represented by 0 and 1. 1 meaning there is a connection between 2 vertices
Takes up more space( in sparse graphs)
Slower to iterate over all edges
Faster to lookup specific edge

Using an adjacency list

Using a hash table {}. Key being the vertex and the value being the array of edges connection
Can take up less space(in sparse graphs)
Faster to iterate over all edges
Can be slower to lookup/query specific edge

Build out graph using adjacency list

Graph.js

class Graph {
  constructor() {
    this.adjacencyList = {};
  }

  addVertex(node) {
    if (this.adjacencyList[node]) {
      return;
    }

    this.adjacencyList[node] = [];
  }

  addEdge(vertex1, vertex2) {
    if (!this.adjacencyList[vertex1]) return;

    if (this.adjacencyList[vertex1]) {
      if (this.adjacencyList[vertex1].includes(vertex2)) {
        return;
      }
      this.adjacencyList[vertex1].push(vertex2);
    }

    if (!this.adjacencyList[vertex2]) return;

    if (this.adjacencyList[vertex2]) {
      if (this.adjacencyList[vertex2].includes(vertex1)) {
        return;
      }
      this.adjacencyList[vertex2] = [];
      this.adjacencyList[vertex2].push(vertex1);
    }
  }

  removeEdge(vertex1, vertex2) {
    if (!this.adjacencyList[vertex1] || !this.adjacencyList[vertex2]) return;

    if (
      this.adjacencyList[vertex1].includes(vertex2) &&
      this.adjacencyList[vertex2].includes(vertex1)
    ) {
      this.adjacencyList[vertex1] = this.adjacencyList[vertex1].filter(
        (v) => v !== vertex2
      );
      this.adjacencyList[vertex2] = this.adjacencyList[vertex2].filter(
        (v) => v !== vertex1
      );
      // const index = this.adjacencyList[vertex2].indexOf(vertex1);
      // this.adjacencyList[vertex2].splice(index, 1);
    }
  }

  removeVertex(vertex) {
    if (!this.adjacencyList[vertex]) return;

    while (this.adjacencyList[vertex]) {
      this.adjacencyList[vertex].forEach((element) => {
        this.removeEdge(vertex, element);
      });

      delete this.adjacencyList[vertex];
    }
  }
}

const g = new Graph();
g.addVertex("Tokyo");
g.addVertex("Dallas");
g.addVertex("Aspen");
g.addVertex("Hong Kong");
g.addVertex("Los Angeles");

g.addEdge("Tokyo", "Dallas");
g.addEdge("Tokyo", "Hong Kong");

g.addEdge("Dallas", "Tokyo");
g.addEdge("Dallas", "Aspen");
g.addEdge("Dallas", "Hong Kong");
g.addEdge("Dallas", "Los Angeles");

g.addEdge("Aspen", "Dallas");

g.addEdge("Hong Kong", "Tokyo");
g.addEdge("Hong Kong", "Dallas");
g.addEdge("Hong Kong", "Los Angeles");
g.addEdge("Los Angeles", "Hong Kong");
g.addEdge("Los Angeles", "Dallas");

{
  Tokyo: [ 'Dallas', 'Hong Kong' ],
  Dallas: [ 'Tokyo', 'Aspen', 'Hong Kong', 'Los Angeles' ],
  Aspen: [ 'Dallas' ],
  'Hong Kong': [ 'Dallas', 'Tokyo', 'Los Angeles' ],
  'Los Angeles': [ 'Hong Kong', 'Dallas' ]
}

g.removeVertex("Hong Kong");

{
  Tokyo: [ 'Dallas' ],
  Dallas: [ 'Tokyo', 'Aspen', 'Los Angeles' ],
  Aspen: [ 'Dallas' ],
  'Los Angeles': [ 'Dallas' ]
}

Traversal of graphs

Uses of traversal
- finding closest matches/recommendations
- shortest path problems
  - gps navigation
  - shortest path to win a game logic

Depth-first traversal

Pseuodcode flow for recursive

The function should accept a starting node
Create an array to store the end result, to be returned at the very end
Create an object to store visited vertices
Create a helper function which accepts a vertex
- The helper function should return early if the vertex is empty
- The helper function should place the vertex it accepts into the visited object and push that vertex into the result array.
- Loop over all the values in the adjacencyList for that vertex
- If any of those values have not been visited, recursively invoke the helper function with that vertex
Invoke the helper function with the starting vertex
Return the result array

Using class properties
class Graph{
  constructor(){
    this.result = []
    this.visitedVertices = {};
    this.adjacencyList = {}
  }

 depthFirstTraversal(vertex) {
    this.dfsRecur(vertex);
    return this.result;
  }

  dfsRecur(vertex) {
    if (!vertex) return;

    this.result.push(vertex);
    this.visitedVertices[vertex] = true;

    this.adjacencyList[vertex].forEach((n) => {
      if (!this.visitedVertices[n]) {
        this.dfsRecur(n);
      }
    });
  }
}


Using functions/closures

  depthFirstTraversal(vertex) {
    const result = [];
    const visitedVertices = {};

    const dfsRecur = (vertex) => {
      if (!vertex) return;
      visitedVertices[vertex] = true;
      result.push(vertex);

      this.adjacencyList[vertex].forEach((n) => {
        if (!visitedVertices[n]) {
          return dfsRecur(n);
        }
      });
    }
    dfsRecur(vertex);
    return result;
  }

Pseudocode for DFS iterative

function accepts a start vertex
Create stack to help keep track of vertices in the form of array (LIFO)
Create a result array to store results, returned at the very end
Create an object to store visited vertices
Add starting vertex to stack and mark it visited
while stack is not empty
- pop next vertex from stack
- push vertex into result array
- loop over vertex neighbours
  - check if neighbour have not been visited
    - mark neighbour as visited
    - push neighbour into stack

  dfsIterative(vertex) {
    const stack = [];
    const discovered = {};
    const result = [];
    let currentVertex;

    stack.push(vertex);
    discovered[vertex] = true;

    while (stack.length !== 0) {
      currentVertex = stack.pop();
      result.push(currentVertex);

      this.adjacencyList[currentVertex].forEach((neighbor) => {
        if (!discovered[neighbor]) {
          discovered[neighbor] = true;
          stack.push(neighbor);
        }
      });
    }
    return result;
  }

Breadth first traversal

use a queue to keep track of vertices

Pseudocode for BFS

Function should accept a starting vertex
Create a queue and place starting vertex in it (FIFO)
Create an array to store the nodes visited and return at end of function
Create an object to store nodes visited
Make starting vertex as visited
Loop as long as there is something in the queue
- Remove the first vertex from the queue and push it into the array that stores nodes visited
- Loop over the vertex in the adjacency list for the vertex that you are visiting
- if it is not inside the object that stores the nodes visited, mark it as visited and enqueue that vertex
Return result array of visited nodes

 bfs(vertex) {
    const visited = {};
    const queue = [vertex];
    const result = [];
    let currentVertex;

    visited[vertex] = true;

    while (queue.length) {
      currentVertex = queue.shift();
      result.push(currentVertex);

      this.adjacencyList[currentVertex].forEach((neighbor) => {
        if (!visited[neighbor]) {
          visited[neighbor] = true;
          queue.push(neighbor);
        }
      });
    }
    return result;
  }

Using an adjacency matrix#

Using an adjacency list#

Build out graph using adjacency list#

Traversal of graphs#

Depth-first traversal#

Breadth first traversal#