How to Build Graphs in JavaScript: Step by Step Tutorial

Introduction

Graphs are everywhere. They are not just the bar charts and line graphs you see in your math textbooks but intricate data structures that play a pivotal role in a multitude of real-world applications. If you've ever used social media, navigated with a GPS app, or worked with recommendation systems, you've already encountered graphs, often without realizing it.

In this article, take a shallow dive into the world of graph data structures by trying to develop a simple graph using the JavaScript programming language. By the end, you'll have a foundational understanding of graphs and how they can be implemented and applied in JavaScript. Whether you're a newcomer to programming or an experienced developer looking to expand your toolkit, this article will demystify the intriguing world of graphs in a simple and approachable manner.

Note: Understanding and working knowledge of basic JavaScript and basic data structures is important to continue with this article.

What are Graphs

Graphs are a fundamental data structure used to represent and model various types of relationships between objects. Unlike linear data structures like arrays or linked lists, graphs allow us to capture more complex connections between elements. Think of graphs as a collection of nodes (also called vertices) connected by edges. Each node can be related to other nodes through these edges, forming a network of interconnected data.

In a graph, nodes represent entities, and edges represent the relationships or connections between those entities. Graphs are incredibly versatile and can be used to model a wide range of scenarios, from social networks and road networks to recommendation systems and dependency tracking.

In this article, we'll walk through how to build a basic graph data structure using JavaScript. We'll create a simple implementation step by step, which you can use as a foundation for more complex graph-related projects.

Create a Graph using JavaScript

To build a basic graph data structure in JavaScript, we'll use a step-by-step approach using Functional Programming. We'll create a graph object that supports adding nodes, adding edges, adding directed edges, and displaying the graph.

Initialize the Graph Object

Start by defining a function that initializes the graph object. This function will set up the data structures needed to represent the graph. In the provided code, the createGraph function accomplishes this task.

function createGraph() {
  // here we will create our graph
}

const graph = createGraph();        

Develop graph test scenarios

As a personal fan of TDD, I want to build test scenarios first and once we have the graph in mind, its easier to develop. The graph shown in the image below is the one we will be trying to develop

In order to build the above graphs, we will consider the following test scenarios:

graph.addNode("A");
graph.addNode("B");
graph.addNode("C");
graph.addNode("D");
graph.addNode("E");

graph.addEdge("A", "C");
graph.addEdge("A", "B");
graph.addDirectedEdge("A", "D");
graph.addEdge("D", "E");

graph.display();        

This should provide us with the following output:

A->C, B, D
B->A
C->A
D->E
E->D        

Add Nodes to the Graph

You need a way to add nodes (or vertices) to the graph. The addNode function creates a node and maintains a list of all nodes in the nodes array. An edge (or link) of a graph is one of the connections between the nodes (or vertices) of the network and hence, in the addNode function, we are also adding a key for that node.

function createGraph() {
  const edges = {};
  const nodes = [];

  function addNode(node) {
    nodes.push(node);
    edges[node] = [];
  }
}

const graph = createGraph();        

Add Undirected Edges

Since we are building a simple graph data structure, in a simple graph, you often want to connect nodes with undirected edges, meaning the connection goes both ways. The addEdge function is responsible for adding undirected edges between two nodes. It updates the edges object accordingly.

function createGraph() {
  const edges = {};
  const nodes = [];

  function addNode(node) {
    nodes.push(node);
    edges[node] = [];
  }

  function addEdge(node1, node2) {
    edges[node1].push(node2);
    edges[node2].push(node1);
  }
}

const graph = createGraph();        

Add Directed Edges

As you can see, we have a case where A to D has a one way flow. Thats called a directed edge. The addDirectedEdge function allows you to add directed edges from one node to another.

function createGraph() {
  const edges = {};
  const nodes = [];

  function addNode(node) {
    nodes.push(node);
    edges[node] = [];
  }

  function addEdge(node1, node2) {
    edges[node1].push(node2);
    edges[node2].push(node1);
  }

  function addDirectedEdge(node1, node2) {
    edges[node1].push(node2);
  }
}

const graph = createGraph();        

Display the Graph

Finally, the display function is used to visualize the graph. It iterates through the nodes and their connected edges to display the graph's structure.

function createGraph() {
  const edges = {};
  const nodes = [];

  function addNode(node) {
    nodes.push(node);
    edges[node] = [];
  }

  function addEdge(node1, node2) {
    edges[node1].push(node2);
    edges[node2].push(node1);
  }

  function addDirectedEdge(node1, node2) {
    edges[node1].push(node2);
  }

  function display() {
    let graph = "";
    nodes.forEach(node => {
      graph += node + "->" + edges[node].join(", ") + "\n";
    });
    console.log(graph);
  }
}

const graph = createGraph();        

Expose the Graph Methods

All the functions, addNode, addEdge etc are enclosed within the provided function and are abstracted from the external environment. It is important to expose them to the world to use. For this purpose, whenever the graph is initialized, we want the value of the graph to contain all the functions that are exposed. Hence, we will return the functions from the graph

function createGraph() {
  const edges = {};
  const nodes = [];

  function addNode(node) {
    nodes.push(node);
    edges[node] = [];
  }

  function addEdge(node1, node2) {
    edges[node1].push(node2);
    edges[node2].push(node1);
  }

  function addDirectedEdge(node1, node2) {
    edges[node1].push(node2);
  }

  function display() {
    let graph = "";
    nodes.forEach(node => {
      graph += node + "->" + edges[node].join(", ") + "\n";
    });
    console.log(graph);
  }

  return {
    addNode,
    addEdge,
    addDirectedEdge,
    display,
  };
}

const graph = createGraph();        

Final Code

Now that our code is complete, let us combine everything we know:

function createGraph() {
  const edges = {};
  const nodes = [];

  function addNode(node) {
    nodes.push(node);
    edges[node] = [];
  }

  function addEdge(node1, node2) {
    edges[node1].push(node2);
    edges[node2].push(node1);
  }

  function addDirectedEdge(node1, node2) {
    edges[node1].push(node2);
  }

  function display() {
    let graph = "";
    nodes.forEach(node => {
      graph += node + "->" + edges[node].join(", ") + "\n";
    });
    console.log(graph);
  }

  return {
    addNode,
    addEdge,
    addDirectedEdge,
    display,
  };
}

const graph = createGraph();

graph.addNode("A");
graph.addNode("B");
graph.addNode("C");
graph.addNode("D");
graph.addNode("E");

graph.addEdge("A", "C");
graph.addEdge("A", "B");
graph.addDirectedEdge("A", "D");
graph.addEdge("D", "E");

graph.display();        

And the output that we should recieve is the following:

A->C, B, D
B->A
C->A
D->E
E->D        

Conclusion

In conclusion, graphs are powerful data structures that allow us to model complex relationships between objects in various real-world scenarios. They consist of nodes (or vertices) connected by edges, representing connections or relationships between entities. For more programming related articles, follow me on LinkedIn.