Implementing Graphs Data Structures in Typescript

Implementing data structures and algorithms is one of the best ways to learn and become comfortable with a language. As someone who isn't entirely comfortable with Typescript (Java is my first language), I recently decided to enhance my Typescript by implementing some data structures and algorithms. And what better way to document my knowledge than to share it with you.

In this tutorial, we will learn how to implement the graph data structure in Typescript. It is intended for beginners, but in order to follow along, you must have a basic understanding of Typescript, Arrays, Maps, and their associated functions. This resource can help you get started with Typescript and Javascript if you do not have this knowledge.

If you already know Typescript, Arrays and Maps then it's:

via GIPHY

What is a Graph?

A graph data structure represents connections between entities (a network). For example, if you want to model railway connections between cities in your region, here is how you could say, “There is a railway track from Lagos to Abuja and there is also a railway track from Lagos to Benin City”.

A graph consists of nodes and edges (connections between nodes). When two nodes share an edge, they are considered adjacent. A path between two nodes exists if a sequence of edges connects them.

Applications of Graphs

Graphs are important data structures in computer science. They are used in a variety of intriguing contexts, including:

Facebook makes use of graphs. Users are represented as nodes. If User A is friends with User B, then there is an edge between User A and User B.
In the World Wide Web, a link from web page A to web page B is represented as an edge, while web pages are represented as nodes.
In a GPS system, locations are represented as nodes and the routes between them are represented as edges.

Types of graphs

Directed graphs are like one-way streets. This means that edges in a directed graph begin at a source and end at a destination. An edge between Nodes A and B and Nodes B and A are not the same thing. Directed graphs are also known as digraphs.
Undirected graphs are like two-way streets. This means that any edge between Nodes A and B is also an edge between Nodes B and A.
Weighted Graphs- Each edge in a weighted graph is given a value. In a graph used to represent the network of train stations in a specific area, the distance between two stations can be used as the edge's weight. Weighted graphs can be directed or undirected.
Unweighted Graphs -Each edge in unweighted graphs is not assigned a value. Unweighted graphs can be directed or undirected, just like weighted graphs.
Cyclic Graphs - A graph with cycles is said to be cyclic. A cycle is a closed network. A cyclic graph can be either directed or undirected. Additionally, a cyclic graph can be either weighted or unweighted.
Trees - A directed graph without cycles is referred to as a tree.

A tree data structure begins at a root node. The root node does not have a parent node. Except for the root node, every node in the tree has just one parent. A node that has children, or nodes that are adjacent to it, is referred to as a parent node. Leaves are nodes that do not have any children.

Binary trees are a typical type of tree implementation. Each node in a binary tree is adjacent to no more than two other nodes, the left child and the right child.

A tree data structure is similar to trees in nature but has the root at the top instead of the bottom. In a tree data structure, the branches in a natural tree are equivalent to the parent nodes, and the leaves to the leaf nodes.

The next question is how do we represent graph data structures in the computer now that we are familiar with graphs and their various types.

Representations of Graphs in Computer Memory

Graphs can be stored as either adjacency matrices or adjacency lists in computer memory.

Adjacency Lists: Adjacency lists use an array index to represent each node in the graph. Each array index has a reference to a list of adjacent nodes.

An adjacency list can be used to represent the graph above as follows:

If we were simulating a weighted graph, we would need to implement an adjacency list where each array index points to a linked list of adjacency nodes. The weight of the edge between each node and its parent node would be stored for each node in the linked list.

Adjacency Matrices: An array with dimensions NxN, where N is the number of nodes, is used to represent an adjacency matrix. Each node is referenced by an array index. Point [0, 1] in the adjacency matrix is filled with the boolean value true if there is an edge between Node A referenced by index 0 and Node B referenced by index 1. If there isn't an edge connecting Nodes A and B, the boolean value false is filled in at point [0,1].

The above graph is represented by an adjacency matrix as follows:

If we were modeling a weighted graph with an adjacency matrix, then we would need to use an implementation where each cell of the multidimensional array has a store of the weight of the edge between them. Point [0, 1] in the adjacency matrix, for instance, would have a weight of 3 if Node 1 and Node 2 had an edge with a weight of that value, but it would have a weight of 0 if they didn't.

After learning about the differences between representing graphs as an adjacency list and an adjacency matrix, the next question is when to use each representation.

When to use an Adjacency List versus an Adjacency Matrix

When we need constant access to every node that is directly adjacent to another node, we use an adjacency list. On the other hand, when there are few nodes in the graph and when it is a complete graph—i.e., every node has a direct edge with almost every other node—we use an adjacency matrix.

Typescript Implementation of a Directed Unweighted Graph Using an Adjacency List

We require the use of ES6 classes in order to implement a graph in typescript. To create a class that generates graphs, we must first implement a class that generates nodes because a graph is made up of a collection of nodes. Additionally, a graph has a comparator. A function called the comparator is utilized when comparing two nodes.

As our adjacency list in this implementation, we will employ a map structure. This is because a map is made up of key-value pairs, where each node is a key and its corresponding value is a list of adjacent nodes.

We can carry out the following operations on a graph:

Add a new edge to the graph.
Add a new node to the graph.
Remove an edge from the graph.
Remove a node from the graph.
Traverse the graph using breadth-first search.
Traverse the graph using a depth-first search.

The use of breadth-first search and depth-first search to traverse a graph will not be covered in this article; instead, please read my upcoming articles where I will properly cover these topics.

Add a new node to the graph
- First, we must determine whether the node already exists in the graph.
- If the node already exists in the graph, we return it.
- Otherwise, if the node does not already exist in the graph, we build a new node by calling the Node class constructor and then adding the new node to the collection of nodes.
Add a new edge to the graph To add a new edge to the graph, do the following:
- First, we need data to create our source and destination nodes (an edge is a direct connection between two nodes).
- Next, the destination node must then be added to the list of adjacent nodes on the source node.
Remove a node from the graph To remove a node from a graph:
- We must first locate the node to be deleted from the graph.
- If the node exists in the graph, we must walk through all of the nodes in the graph and then remove the node from everywhere it is located as an adjacent node.
- After disconnecting the node to be deleted from all other nodes, we delete it from the graph's node collection.
Remove a edge from the graph To remove an edge from the graph:
- We must first obtain the source and destination nodes.
- The destination node is then removed from the list of adjacent nodes of the source node.

export class Node<T> {
  data: T;
  adjNodes: Node<T>[];
  comparator: (a: T, b: T) => number;

  constructor(data: T, comparator: (a: T, b: T) => number) {
    this.data = data;
    this.adjNodes = new Array<Node<T>>();
    this.comparator = comparator;
  }
  /**
   * adds a new node as a neighbor
   * @param {Node<T>}node
   */
  addNewNeighbour(node: Node<T>): void {
    this.adjNodes.push(node);
  }

  /**
   * removes a node from the list of neighbors
   * @param {T} data
   * @returns {Node<T>| null}
   */
  removeNeighbour(data: T): Node<T> | null {
    let index = this.adjNodes.findIndex(
      (node) => this.comparator(node.data, data) == 0
    );
    if (index != -1) {
      return this.adjNodes.splice(index, 1)[0];
    }
    return null;
  }
}

export class Graph<T> {
  nodes: Map<T, Node<T>> = new Map<T, Node<T>>();
  comparator: (a: T, b: T) => number;
  root: Node<T>;

  constructor(comparator: (a: T, b: T) => number, data: T) {
    this.comparator = comparator;
    this.root = new Node<T>(data, comparator);
  }

  /**
   * adds a new node to the graph
   * @param {T} data
   * @returns {Node<T>}
   */
  addNewNode(data: T): Node<T> {
    let node = this.nodes.get(data);
    // if the node is already in the graph, then there is no need to build it
    if (node != null) {
      return node;
    }
    // if the node is not already in the graph, then create a node and set the node into the map of nodes
    node = new Node(data, this.comparator);
    this.nodes.set(data, node);
    return node;
  }

  /**
   * remove a node from the graph
   * @param {T} data
   * @returns {Node<T> | null}
   */

  removeNode(data: T) {
    let nodeToRemove = this.nodes.get(data);

    this.nodes.forEach((node) => {
          // if nodeToRemove is not undefined and if node in graph contains nodeToRemove in list of adjacent nodes
          if (nodeToRemove && node.adjNodes.includes(nodeToRemove)){
            // remove nodeToRemove
            node.removeNeighbour(nodeToRemove.data)
          }
        }
    );
    this.nodes.delete(data);
    return nodeToRemove;
  }

  /**
   * add an edge to the graph
   * @param source
   * @param destination
   */
  addEdge(source: T, destination: T): void {
    let sourceNode: Node<T> = this.addNewNode(source);
    let destinationNode: Node<T> = this.addNewNode(destination);

    // add the destination node to the list of adjacent nodes for the destination node.
    sourceNode.addNewNeighbour(destinationNode);
  }

  /**
   * remove an edge from the graph
   * @param source
   * @param destination
   */
  removeEdge(source: T, destination: T): void {
    //get the source node
    let sourceNode: Node<T> | undefined = this.nodes.get(source);
    //get the destination node
    let destinationNode: Node<T> | undefined =
      this.nodes.get(destination);

    //remove the destination from the list of adjacent nodes on the source node
    if (sourceNode && destinationNode) {
      sourceNode.removeNeighbour(destinationNode.data);
    }
  }
}

function comparator(a: number, b: number) {
  if (a < b) return -1;

  if (a > b) return 1;

  return 0;
}

const graph: Graph<number> = new Graph<number>(comparator, 1);
graph.addEdge(1, 2);
graph.addEdge(1, 4);
graph.addEdge(2, 1);
graph.addEdge(2, 3);
graph.addEdge(2, 5);
graph.addEdge(3, 2);
graph.addEdge(3, 6);
graph.addEdge(4, 1);
graph.addEdge(4, 5);
graph.addEdge(4, 7);
graph.addEdge(5, 2);
graph.addEdge(5, 4);
graph.addEdge(5, 6);
graph.addEdge(5, 8);
graph.addEdge(6, 3);
graph.addEdge(6, 5);
graph.addEdge(6, 9);
graph.addEdge(7, 4);
graph.addEdge(7, 8);
graph.addEdge(8, 7);
graph.addEdge(8, 5);
graph.addEdge(8, 9);
graph.addEdge(9, 8);
graph.addEdge(9, 6);

Ehis Edemakhiota's Blog