<_

Data Structures: Adjacency Graph in TypeScript

Understanding Adjacency Graphs with TypeScript

Ever wondered how to represent a graph in programming? Well, it's not as hard as it seems! We'll dive into the world of graph theory using TypeScript, focusing on the adjacency list representation.

What is an Adjacency Graph?

An adjacency graph is a way to represent a graph in which we store all the vertices and their corresponding connected vertices. It's like having a network of friends, where for each person, you have a list of all their friends.

Introduction: The Lay of the Land

Adjacency graphs are like the intricate road maps of data, offering a bird's-eye view of how different elements connect and interact. In TypeScript, wielding this powerful tool effectively can be akin to mastering the art of cartography in the realm of data.

What's an Adjacency Graph?

At its core, an adjacency graph is a way to represent connections between nodes. Imagine a spiderweb where each strand represents a relationship - that's your graph, with each node a crucial intersection in this web of data.

Setting the Scene: Understanding the Basics

Before we dive into the nuts and bolts, let's get a lay of the land.

Nodes and Edges: The Building Blocks

  • Nodes: These are the data points or entities. In a social network, for instance, each person would be a node.
  • Edges: The lines that connect nodes, representing relationships or connections.

Directed vs. Undirected Graphs: Picking Your Path

  • Directed Graphs: Here, edges have a direction, like a one-way street.
  • Undirected Graphs: Edges are two-way streets, with no inherent direction.

Weighted Graphs: Adding Some Gravity

In some graphs, edges have weights, like paths with different difficulties or lengths. It adds another layer of complexity, like choosing between a highway or a scenic route.


Representing the Adjacency Graph - Adjacency List

Today, we will be creating an adjacency list. To conceptualize how this will look, take a look at this code snippet representation:


const AdjacencyList = {
	A: ["B"],
	B: ["A", "C"],
	C: ["B"],
}

Here you can see the points A, B, and C. A. has the "B" vertex, B. has "A" and "C" (creating an edge), and C. has "B".

Crafting the Map: Implementing an Adjacency Graph in TypeScript

Let's get our hands dirty and start building our map.

Defining the Class


export class AdjacencyGraph {
	adjacentList: { [keyof: string]: Set }

	constructor() {
		this.adjacentList = {}
	}
}

Adding Vertices


    addVertex(vertex: string) {
		if (!this.adjacentList[vertex]) this.adjacentList[vertex] = new Set()
	}

Here, we will add vertices to our graph..

Connecting the Dots: Adding Edges


addEdge(vertex1: string, vertex2: string) {
		if (!this.adjacentList[vertex1]) {
			this.addVertex(vertex1)
		}
		if (!this.adjacentList[vertex2]) {
			this.addVertex(vertex2)
		}
		this.adjacentList[vertex1].add(vertex2)
		this.adjacentList[vertex2].add(vertex1)
	}

With addEdge, we're drawing lines between our flags, establishing connections.

Removing the Dots: Removing Edges


removeEdge(vertex1: string, vertex2: string) {
	this.adjacentList[vertex1].delete(vertex2)
	this.adjacentList[vertex2].delete(vertex1)
}

With removeEdge, we're removing lines between our flags, deleting connections.

Removing the Dots: Removing Vertices


removeVertex(vertex: string) {
		if (!this.adjacentList[vertex]) return

		for (const adjacentVertex of this.adjacentList[vertex]) {
			this.removeEdge(vertex, adjacentVertex)
		}

		delete this.adjacentList[vertex]
	}

Has Edge: do things connect?

A very simple boolean response. Add two vertices to the method, and a boolean tells you true or false.


    
    hasEdge(vertex1: string, vertex2: string) {
		return (
			this.adjacentList[vertex1].has(vertex2) &&
			this.adjacentList[vertex2].has(vertex1)
		)
	}

	display() {
		for (const vertex in this.adjacentList) {
			console.log(vertex, " -> ", [...this.adjacentList[vertex]])
		}
	}

Display()

As you'd expect. A console log of your graph.



	display() {
		for (const vertex in this.adjacentList) {
			console.log(vertex, " -> ", [...this.adjacentList[vertex]])
		}
	}

The final class

Let's explore the TypeScript code for an adjacency graph:

export class AdjacencyGraph {
    adjacentList: { [keyof: string]: Set<string> }

    constructor() {
        this.adjacentList = {}
    }

    addVertex(vertex: string) {
        if (!this.adjacentList[vertex]) this.adjacentList[vertex] = new Set()
    }

    addEdge(vertex1: string, vertex2: string) {
        if (!this.adjacentList[vertex1]) {
            this.addVertex(vertex1)
        }
        if (!this.adjacentList[vertex2]) {
            this.addVertex(vertex2)
        }
        this.adjacentList[vertex1].add(vertex2)
        this.adjacentList[vertex2].add(vertex1)
    }

    removeEdge(vertex1: string, vertex2: string) {
        this.adjacentList[vertex1].delete(vertex2)
        this.adjacentList[vertex2].delete(vertex1)
    }

    removeVertex(vertex: string) {
        if (!this.adjacentList[vertex]) return

        for (const adjacentVertex of this.adjacentList[vertex]) {
            this.removeEdge(vertex, adjacentVertex)
        }

        delete this.adjacentList[vertex]
    }

    hasEdge(vertex1: string, vertex2: string) {
        return (
            this.adjacentList[vertex1].has(vertex2) &&
            this.adjacentList[vertex2].has(vertex1)
        )
    }

    display() {
        for (const vertex in this.adjacentList) {
            console.log(vertex, " -> ", [...this.adjacentList[vertex]])
        }
    }
}

Breaking Down the Code

Here's what each part of our code does:

  • Constructor: Initializes the adjacency list.
  • addVertex: Adds a new vertex to the graph.
  • addEdge: Connects two vertices with an edge.
  • removeEdge: Removes the connection between two vertices.
  • removeVertex: Removes a vertex and all its connected edges.
  • hasEdge: Checks if an edge exists between two vertices.
  • display: Logs the graph to the console.

Charting New Territories: Practical Applications

Adjacency graphs are not just theoretical constructs. They have real-world applications that can revolutionize how we handle data.

Social Networks: Mapping Relationships

In social networking platforms, adjacency graphs can model friendships, helping suggest new connections or content.

Transportation Networks: Plotting Routes

Whether it's for GPS systems or logistics, adjacency graphs can optimize routes, saving time and fuel.

Internet Routing: Guiding Data Packets

In the vast expanse of the internet, adjacency graphs help in efficient data packet routing, ensuring information reaches its destination swiftly.


Conclusion

And that's it! With this simple class, you can create and manage a graph in TypeScript. Remember, graphs are all about connections, much like social networks or road maps. So next time you're thinking about data structures, give graphs a go!