Here’s what I’ve learned about the graph data structure. Let’s start.
We will represent the graph as an adjacency list, which is an object (or a hash table) that maps each vertex to an array of its adjacent vertices. This is a simple and efficient way to store the graph structure in JavaScript.
class Graph {
constructor() {
this.adjacencyList = {};
}
}
export default Graph;To add a new vertex to the graph, we just need to create a new property in the object with the vertex name as the key and an empty array as the value. This means that the new vertex has no edges yet.
class Graph {
constructor() {
this.adjacencyList = {};
}
addVertex(value) {
if (!this.adjacencyList[v]) {
this.adjacencyList[v] = [];
return true;
}
return false;
}
}
export default Graph;To add an edge between two vertices, we need to push the names of the vertices to each other’s array in the object. This will create an undirected edge, meaning that the edge can be traversed in both directions.
class Graph {
constructor() {
this.adjacencyList = {};
}
addVertex(v) {
if (!this.adjacencyList[v]) {
this.adjacencyList[v] = [];
return true;
}
return false;
}
addEdge(v1, v2) {
if (this.adjacencyList[v1] && this.adjacencyList[v2]) {
this.adjacencyList[v1].push(v2);
this.adjacencyList[v2].push(v1);
return true;
}
return false;
}
}
export default Graph;If we want to create a directed edge, which can only be traversed in one direction, we only need to push one vertex name to the other’s array.
class Graph {
constructor() {
this.adjacencyList = {};
}
addVertex(v) {
if (!this.adjacencyList[v]) {
this.adjacencyList[v] = [];
return true;
}
return false;
}
addEdge(v1, v2) {
if (this.adjacencyList[v1] && this.adjacencyList[v2]) {
this.adjacencyList[v1].push(v2);
this.adjacencyList[v2].push(v1);
return true;
}
return false;
}
addDirectedEdge(v1, v2) {
if (this.adjacencyList[v1] && this.adjacencyList[v2]) {
this.adjacencyList[v1].push(v2);
return true;
}
return false;
}
}
export default Graph;To remove an edge between two vertices, we need to filter out the names of the vertices from each other’s array in the object. This will delete the edge from both ends.
class Graph {
constructor() {
this.adjacencyList = {};
}
addVertex(v) {
if (!this.adjacencyList[v]) {
this.adjacencyList[v] = [];
return true;
}
return false;
}
addEdge(v1, v2) {
if (this.adjacencyList[v1] && this.adjacencyList[v2]) {
this.adjacencyList[v1].push(v2);
this.adjacencyList[v2].push(v1);
return true;
}
return false;
}
addDirectedEdge(v1, v2) {
if (this.adjacencyList[v1] && this.adjacencyList[v2]) {
this.adjacencyList[v1].push(v2);
return true;
}
return false;
}
removeEdge(v1, v2) {
if (this.adjacencyList[v1] && this.adjacencyList[v2]) {
this.adjacencyList[v1] = this.adjacencyList[v1].filter(v => v !== v2);
this.adjacencyList[v2] = this.adjacencyList[v2].filter(v => v !== v1);
return true;
}
return false;
}
}
export default Graph;The removeEdge() method can also handle the case of deleting a directed edge between two vertices, so we do not need a separate method for that, unlike when we added a directed edge.
Next, we will now need to remove a vertex from the Graph. The ingenuity lies in reusing the removeEdge() method we just implemented above.
class Graph {
constructor() {
this.adjacencyList = {};
}
addVertex(v) {
if (!this.adjacencyList[v]) {
this.adjacencyList[v] = [];
return true;
}
return false;
}
addEdge(v1, v2) {
if (this.adjacencyList[v1] && this.adjacencyList[v2]) {
this.adjacencyList[v1].push(v2);
this.adjacencyList[v2].push(v1);
return true;
}
return false;
}
addDirectedEdge(v1, v2) {
if (this.adjacencyList[v1] && this.adjacencyList[v2]) {
this.adjacencyList[v1].push(v2);
return true;
}
return false;
}
removeEdge(v1, v2) {
if (this.adjacencyList[v1] && this.adjacencyList[v2]) {
this.adjacencyList[v1] = this.adjacencyList[v1].filter(v => v !== v2);
this.adjacencyList[v2] = this.adjacencyList[v2].filter(v => v !== v1);
return true;
}
return false;
}
removeVertex(v) {
if (this.adjacencyList[v]) {
while(this.adjacencyList[v].length) {
let neighbor = this.adjacencyList[v].pop();
this.removeEdge(neighbor, v);
}
delete this.adjacencyList[v];
return this;
}
return undefined;
}
}
export default Graph;To solve the well-known problem of finding Strongly Connected Components, we need a way to reverse a directed graph. This means that all the vertices that had outgoing edges will now have incoming edges instead. This is called a transposed or reversed directed graph.
this.adjacencyList = {
u: [v, w],
v: [],
w: []
}
// Reversed
this.adjacencyList = {
u: [],
v: [u],
w: [u]
}Here’s the transpose() method:
class Graph {
constructor() {
this.adjacencyList = {};
}
addVertex(v) {
if (!this.adjacencyList[v]) {
this.adjacencyList[v] = [];
return true;
}
return false;
}
addEdge(v1, v2) {
if (this.adjacencyList[v1] && this.adjacencyList[v2]) {
this.adjacencyList[v1].push(v2);
this.adjacencyList[v2].push(v1);
return true;
}
return false;
}
addDirectedEdge(v1, v2) {
if (this.adjacencyList[v1] && this.adjacencyList[v2]) {
this.adjacencyList[v1].push(v2);
return true;
}
return false;
}
removeEdge(v1, v2) {
if (this.adjacencyList[v1] && this.adjacencyList[v2]) {
this.adjacencyList[v1] = this.adjacencyList[v1].filter(v => v !== v2);
this.adjacencyList[v2] = this.adjacencyList[v2].filter(v => v !== v1);
return true;
}
return false;
}
removeVertex(v) {
if (this.adjacencyList[v]) {
while(this.adjacencyList[v].length) {
let neighbor = this.adjacencyList[v].pop();
this.removeEdge(neighbor, v);
}
delete this.adjacencyList[v];
return this;
}
return undefined;
}
transpose() {
let reversed = {};
for (let v in this.adjacencyList) {
reversed[v] = [];
}
for (let v in reversed) {
let neighbors = this.adjacencyList[v];
neighbors.forEach((neighbor) => {
reversed[neighbor].push(v);
});
}
return reversed;
}
}
export default Graph;And that concludes our Graph, using an object as an adjacency list to represent a Graph, in JavaScript.