Implementing Graphs with NodeJS and Javascript

Graphs: Working with Complex Data Relationships

Graphs are an essential data structure that allows us to represent complex relationships between elements, such as social networks, navigation systems and route optimization. Here we will cover the basics with implementation and a few concepts of graphs in NodeJS/JavaScript.

Hands-on

First The Theory

Here you will remember about trees because the graph is a collection of nodes (or vertices) and edges, the edges are the ones that connect these nodes. Graphs can be directed or undirected and can include edges with weights (or other type of information), and when we have that, usually means that the edge has a cost or distance between nodes, and the cost should be considered when navigating through the graph... yes it kind of get a little bit more complex but let's try to simplify this here.

Now The Practice

So, let's dive in the code, the following is a basic graph structure, I mean, what a basic graph should have? It should have its nodes, and it's size:

class Graph {
  constructor() {
    this.numberOfNodes = 0
    this.adjacentList = {}
  }
}

Sooo that's it, graph is done, let's all go to sleep...I'm kidding, lets add some functions to insert and show the graph connections:

class Graph {
  constructor() {
    this.numberOfNodes = 0
    this.adjacentList = {}
  }
  add(node) {
    this.adjacentList[node] = []
    this.numberOfNodes++
  }
  addEdge(node1, node2) {
    this.adjacentList[node1].push(node2)
    this.adjacentList[node2].push(node1)
  }
  showConnections() {
    const all = Object.keys(this.adjacentList)
    for (let node of all) {
      let nodeConnections = this.adjacentList[node]
      let connections = ''
      let vertex
      for (vertex of nodeConnections) {
        connections += vertex + ' '
      }
      console.log(`${node} --> ${connections}`)
    }
  }
}

Let me explain each section:

add(node) {
    this.adjacentList[node] = [];
    this.numberOfNodes++;
}

On the above code the goal is to add items (or nodes) into the graph, but bear in mind that the variable where we are inserting data it's named as adjacentList but it's an object, I know that's a little confunsing now, but the intention here is to keep the names easy for you to identify in other places. So we are adding an object, and when we do adjacentList[node] = [] we are creating a object key inside the adjacentList object, and this key has an empty ([]) value, meaning that it has empty relations/connections.

 addEdge(node1, node2) {
    this.adjacentList[node1].push(node2);
    this.adjacentList[node2].push(node1);
}

When we add an Edge we basically are adding a connection between two nodes like a connection between X and Y. That's why we add both ways on the code, we need to add a connection from X to Y and another connection grom Y to X.

We do that because of the type of the graph we are creating is not a directional graph (thats a matter for another post) but keep in mind that we are basically creating a connection that comes and goes from 2 points (like a street). We can also note that in this basic template we are not adding any "weight" to the edges, if we wanna to do that (like in a graph that represents a street and the lenght of the street for instance) we could add the weight doing something like this:

addEdge(node1, node2, weight = 0) {
    this.addVertex(node1);
    this.addVertex(node2);
    this.vertices[node1].push({ node: node2, weight });
    this.vertices[node2].push({ node: node1, weight });
}

Of course this is a basic example, but I think you are starting to get the idea. Let's run some tests on the graph:

const myGraph = new Graph()
myGraph.add(0)
myGraph.add(1)
myGraph.add(2)
myGraph.add(3)
myGraph.addEdge(0, 2)
myGraph.addEdge(1, 2)
myGraph.addEdge(1, 3)
myGraph.addEdge(2, 3)
myGraph.showConnections()

If you did it right and tried to run the node file you should get something like this:

> node graph.js
0 --> 2
1 --> 2 3
2 --> 0 1 3
3 --> 1 2

To basically the showConnections function is saying that:

• 0 has a connection with 2.
• 1 has a connection with 2 and 3.
• 2 has a connection with 0, 1 and 3.
• 3 has a connection with 1 and 2.

Does this information triggers something in your brain?

Where You Can Use/See it

We don't have a lot of options here, you will see this kind of structure in cases like:

Social Midia

Graphs are the best way of representing social midia relationships, so each user can be represented as a node and the relationships as edges, that way you can easily represent first, 2nd, 3rd levels of relations, etc.

GPS and Navigation in General

GPS systems are great friends of graphs, you can easily represent streets as edges and houses, buildings, restaurants as nodes, you can put a weight on street that usually have lot of traffic or has lot of stop lights, and so on... Then you can make use of algorithms to find the shortest path from point A to point B.

And of course you can see this kind of structure in other places as well, you can for instance have an e-commerce platform where you use graphs that each node is a product and the weight is the percentage of how much a product can be related to another in a purchase and based on the weight you can use the graph to show customers related products as suggestions for purchases, and so on...

Tips and Tricks

• Choose the graph representation (list, matrix, etc.) based on the type of operations you need the most, such as searching or inserting nodes.
• For large graphs, consider the use of specialized data structures that optimize memory usage and processing time, today we have specific databases for graphs, specific libs, etc.
• Implement and test fundamental graph algorithms, such as depth first search (DFS) and breadth first search (BFS), to ensure that your graph structure works effectively under various conditions. (We will do this in a later post, if you scroll up where I mention my initial post about the 15 most used structures and algorithms you'll see that we are going to address this in a future post).

My Final Thoughts

The idea here is to have a base of how graphs work, probably you will never need to create a graph structure in your daily life, or maintain it. Even if you work at companies like Meta, Instagram, Twitter (X), you will need to understand the structure, and perhaps create features or solve bugs that are close to these structures, but it's difficult to think that you will be working with the core of the graph or the algorithms all the time, once you created a graph with the necessary functions, you will only change if the need for your product changes for some reason such as a sudden increase in users, adding new features such as weight or priority queues, etc.

And You?!

Have you ever created/used something similar in your personal or company projects? Share your comments here with your questions, what you have already done, experiences, challenges, tips, etc!! Let's explore these concepts together, and if you see any bugs, errors, improvements, leave a comment as well!