Data Structures: Graphs II

This is part 2 of my article on Graphs in my data structures series. In part 1 we learned about graph terminology, types of graphs, and some real-life applications of graph data structures. In this part of the series, we are going to look at graph representation, and we're going to build a graph in Javascript code.

 

Graph Representation

Graphs representation deals with how graphs can be written/implemented in code. The two most common ways to represent a graph are through an Adjacency list or an Adjacency matrix

 

Adjacency List

The adjacency list is very straightforward, a list of all vertices each with a list of their edges( adjacent nodes). A list can be any linear or iterable data structure (Arrays, Maps, Linked Lists, Queues). Below are examples of graphs using an adjacency list.

 

Directed Graph

 

Undirected Graph

 

Weighted Graph

 

Pros

• It is very memory efficient when used on sparse graphs (graphs with few edges between the vertices).

• It is easy to understand and implement.

• It is fast at creating and deleting edges and vertices.

Cons

• It is less time-efficient at verifying if vertices are adjacent to each other.

 

Adjacency Matrix

The adjacency matrix is a Square matrix whose rows and columns are equal to the number of vertices in a graph, edges are represented by the intersections between rows and columns. Edges are denoted with the number 1 when present and 0 when not. Weighted edges are denoted by their weight. Below are examples of graphs using an adjacency matrix.

 

Directed Graph

 

Undirected Graph

 

Weighted Graph

In the above images, we can see that the intersections AxA, BxB, CxC, DxD and ExE are all 0; this is because there are no self-loops in these graphs. A self-loop is a vertex in a graph that points to itself.

 

Pros

• It is very time efficient when used with dense or complete graphs (graphs with a lot of edges between vertices are called dense while graphs with all possible edges are called complete).

Cons

• It is slow at creating and deleting edges and vertices.

• It is a lot more complex than the adjacency list.

• It is very memory inefficient when used for sparse graphs (most graphs are sparse)

 

Javascript Implementation

We are going to be building a graph using Adjacency List representation. Our graph can be weighted, directed or undirected. Our graph methods will be:

• AddVertex: Add a vertex to the graph.
• RemoveVertex: Delete a vertex.
• CreateEdge: Add an edge between 2 vertices.
• DeleteEdge: Remove an edge between 2 edges.
• IsPresent: Check if a vertex exists.

Graphs are made of vertices/nodes so let's first create our node constructor before moving on to the graph constructor.

class Node {
  constructor(value) {
    (this.value = value),
    (this.edgeList = {});

  }
  addEdge(node, weight) {
    this.edgeList[node.value] = weight ? weight : 0;
  }

  removeEdge(node) {
    delete this.edgeList[node.value];
  }
}

Explanation

Our nodes will have two properties and methods.

• The value property will store the value of our node.
• The edgeList property stores the edges of our node.
• AddEdge is a method that adds an edge and weight to the edgeList of a node. The value of the node passed to addEdge is used as the key and the weight is the value. if no weight is given we set it to 0.
• DeleteEdge is a method to delete an edge from the edgeList. It uses the value of the node passed to it to access it and delete it.

 

Now let's take a look at our graph constructor and how our various methods work.

class Graph {
  constructor(type) {
    (this.nodes = new Map()), 
    (this.directed = type ? type : false);

  }
  addVertex(value) {
    let node = new Node(value);
    this.nodes.set(value, node);
  }

  removeVertex(value) {
    let vertex = this.nodes.get(value);
    if (vertex) {
      for (const node of this.nodes.values()) {
        node.removeEdge(vertex);
      }
    }
    return vertex;
  }

  createEdge(startNode, endNode, weight) {
    let startVertex = this.nodes.get(startNode);
    let endVertex = this.nodes.get(endNode);

    if (startVertex && endVertex) {
      startVertex.addEdge(endVertex, weight);

      if (!this.directed) {
        endVertex.addEdge(startVertex, weight);
      }
    }else {
      console.log("non-existent vertex passed")
    }
  }

  deleteEdge(startNode, endNode) {
    let startVertex = this.nodes.get(startNode);
    let endVertex = this.nodes.get(endNode);

    startVertex.removeEdge(endVertex);
    endVertex.removeEdge(startVertex)
  }

  getVertex(value){
    return this.nodes.get(value)
  }

  isPresent(value){
    return this.nodes.has(value)
  }
}

Explanation

Our graph will have two properties a Map object to store the vertices/nodes and a boolean to determine the type of graph directed or undirected. if true is passed when the function is called, it is a directed graph; otherwise, it is undirected.

  addVertex(value) {
    let node = new Node(value);
    this.nodes.set(value, node);
  }

• AddVertex is our first method. It simply takes a value and creates a node which it adds to the graph Map object.

 removeVertex(value) {
    let vertex = this.nodes.get(value);
    if (vertex) {
      for (const node of this.nodes.values()) {
        node.removeEdge(vertex);
      }
    }
    this.nodes.delete(value);
    return vertex;
  }

• The removeVertex deletes a vertex from a graph. It takes a value and checks if it exists in the graph, if it does, it loops through the nodes Map object and deletes the node from the edgeList of all nodes, and then deletes it from the nodes map object.

  createEdge(startNode, endNode, weight) {
    let startVertex = this.nodes.get(startNode);
    let endVertex = this.nodes.get(endNode);

    if (startVertex && endVertex) {
      startVertex.addEdge(endVertex, weight);
      if (!this.directed) {
        endVertex.addEdge(startVertex, weight);
      }
    }else {
      console.log("non-existent vertex passed")
    }
  }

• The createEdge method creates an edge in the graph; it takes 3 parameters when called, the start and end vertices, and the weight of the edge. First, it checks that both vertices are present in the node, if they are; it calls addEdge on the start vertex and passes it to the end vertex and the weight. if the graph is undirected it calls addEdge on the end vertex and passes it the start vertex and the weight. if either of the vertices does not exist we let the user know.

  deleteEdge(startNode, endNode) {
    let startVertex = this.nodes.get(startNode);
    let endVertex = this.nodes.get(endNode);

    startVertex.removeEdge(endVertex);
    endVertex.removeEdge(startVertex)
  }

• The deleteEdge method deletes an edge from the graph but not the vertices. It takes two parameters when called, the start and end vertices/nodes and calls the removeEdge method on both.

  getVertex(value){
    return this.nodes.get(value)
  }

• The getVertex method returns a vertex from the nodes map object.

 isPresent(value){
    return this.nodes.has(value)
  }

• The isPresent method simply checks if a node/vertex exists in the nodes Map object and returns a boolean.

 

Conclusion

The code for this article can be found here. Graphs are very complex and useful data structure, if you would to learn more about graphs, check out this video thanks for reading and see you later.