GraphMatrix 🌐
Description:
A GraphMatrix represents a directed graph using an adjacency matrix where each node is connected via edges. The matrix represents the relationships between nodes, with 1 indicating an edge between two nodes and 0 meaning no edge.
Pros & Cons:
Using this data structure has several benefits:
Fast Edge Lookups: You can check if an edge exists between two nodes in constant time O(1).
Simple Representation: The graph structure is straightforward to implement and visualize as a matrix.
It also has some drawbacks:
Memory Usage: The adjacency matrix requires space proportional to the square of the number of nodes, O(n²), which is inefficient for sparse graphs.
Handling Sparse Graphs: For large, sparse graphs, a different structure like adjacency lists might be more efficient.
1. Adding Nodes:
The add function inserts a new node into the graph and updates the adjacency matrix to include this new node with no initial edges.
0
1
2
3
4
5
6
7
8
9
10
11
12
13
add(node: T) {
this.nodes.push(node);
this.matrix = this.matrixCreationHelper(this.nodes.length);
}
private matrixCreationHelper(length: number): number[][] {
const newMatrix = new Array(length);
for (let x = 0; x < length; x++) {
newMatrix[x] = new Array(length).fill(0);
}
return newMatrix;
}
2. Adding Edges:
The addEdge function creates a directed edge from one node to another. The adjacency matrix is updated with a 1 to indicate this edge.
0
1
2
3
4
5
6
addEdge(from: T, to: T) {
const indexFrom = this.nodes.indexOf(from);
const indexTo = this.nodes.indexOf(to);
this.matrix[indexTo][indexFrom] = 1;
}
3. Removing Edges:
The removeEdge function removes an edge between two nodes by setting the corresponding value in the matrix to 0.
0
1
2
3
4
5
6
removeEdge(from: T, to: T) {
const indexFrom = this.nodes.indexOf(from);
const indexTo = this.nodes.indexOf(to);
this.matrix[indexTo][indexFrom] = 0;
}
4. Showing All Edges:
The showEdges function displays the current state of the adjacency matrix, showing all connections between nodes.
0
1
2
3
4
5
6
7
8
9
10
11
showEdges() {
console.log(` ${this.nodes.join(' ')}`);
for (let y = 0; y < this.matrix.length; y++) {
let row = `${this.nodes[y]} `;
for (let x = 0; x < this.matrix.length; x++) {
row += `${this.matrix[x][y]} `;
}
console.log(`${row}`);
}
}
4. Removing Nodes:
The remove function removes a node from the graph and adjusts the adjacency matrix by removing the row and column corresponding to the node.
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
remove(nodeToRemove: T) {
const indexOfNodeToRemove = this.nodes.indexOf(nodeToRemove);
this.nodes = this.nodes.filter(node => node !== nodeToRemove);
this.matrix = this.matrixDeletionHelper(indexOfNodeToRemove, this.nodes.length);
}
private matrixDeletionHelper(index: number, length: number): number[][] {
let newMatrix = this.matrix.filter((_, i) => i !== index);
for (let x = 0; x < length; x++) {
newMatrix[x] = (newMatrix[x] as number[]).filter((_, i) => i !== index);
}
return newMatrix;
}
5. Checking for an Edge:
The checkEdge function checks if there is a directed edge between two nodes. It returns true if the edge exists, false otherwise.
0
1
2
3
4
5
6
checkEdge(from: T, to: T): boolean {
const indexFrom = this.nodes.indexOf(from);
const indexTo = this.nodes.indexOf(to);
return this.matrix[indexTo][indexFrom] === 1;
}
6. Removing All Edges from a Node:
The removeAllEdges function removes all outgoing edges from a specified node, setting the corresponding column in the adjacency matrix to 0.
0
1
2
3
4
5
6
7
removeAllEdges(from: T) {
const indexFrom = this.nodes.indexOf(from);
for (let i = 0; i < this.nodes.length; i++) {
this.matrix[i][indexFrom] = 0;
}
}
Testing the Implementation
Let's see how this graph matrix works with some example operations:
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
const matrix = new GraphMatrix<string>();
matrix.add("A");
matrix.add("B");
matrix.add("C");
matrix.add("D");
matrix.add("E");
matrix.add("F");
matrix.addEdge("A", "B");
matrix.addEdge("A", "C");
matrix.addEdge("B", "D");
matrix.addEdge("C", "D");
matrix.addEdge("D", "C");
matrix.addEdge("D", "E");
matrix.addEdge("E", "F");
matrix.showEdges();
matrix.removeAllEdges("A");
matrix.showEdges();
matrix.addEdge("A", "B");
matrix.addEdge("A", "C");
matrix.showEdges();
matrix.removeEdge("A", "B");
matrix.showEdges();
matrix.remove("D");
matrix.showEdges();
Console Output Example
This is an example of what you should see in the console:
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
** Adds nodes: A,B,C,D,E,F.
** Add edge A --> B.
** Add edge A --> C.
** Add edge B --> D.
** Add edge C --> D.
** Add edge D --> C.
** Add edge D --> E.
** Add edge E --> F.
** Show all added edges matrix.
A B C D E F
A 0 1 1 0 0 0
B 0 0 0 1 0 0
C 0 0 0 1 0 0
D 0 0 1 0 1 0
E 0 0 0 0 0 1
F 0 0 0 0 0 0
** Remove all edges of A and show the edges matrix.
A B C D E F
A 0 0 0 0 0 0
B 0 0 0 1 0 0
C 0 0 0 1 0 0
D 0 0 1 0 1 0
E 0 0 0 0 0 1
F 0 0 0 0 0 0
** Add edge A --> B.
** Add edge A --> C.
A B C D E F
A 0 1 1 0 0 0
B 0 0 0 1 0 0
C 0 0 0 1 0 0
D 0 0 1 0 1 0
E 0 0 0 0 0 1
F 0 0 0 0 0 0
** remove edge A --> B.
A B C D E F
A 0 0 1 0 0 0
B 0 0 0 1 0 0
C 0 0 0 1 0 0
D 0 0 1 0 1 0
E 0 0 0 0 0 1
F 0 0 0 0 0 0
** Remove node D.
A B C E F
A 0 0 1 0 0
B 0 0 0 0 0
C 0 0 0 0 0
E 0 0 0 0 1
F 0 0 0 0 0
Complete GraphMatrix Implementation
Here’s the complete implementation for the GraphMatrix class:
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
export class GraphMatrix<T> {
nodes: T[] = [];
matrix: number[][] = [];
add(node: T) {
this.nodes.push(node);
this.matrix = this.matrixCreationHelper(this.nodes.length);
}
private matrixCreationHelper(length: number): number[][] {
const newMatrix = new Array(length).fill(null).map(() => new Array(length).fill(0));
return newMatrix;
}
remove(nodeToRemove: T) {
const indexOfNodeToRemove = this.nodes.indexOf(nodeToRemove);
this.nodes = this.nodes.filter(node => node !== nodeToRemove);
this.matrix = this.matrixDeletionHelper(indexOfNodeToRemove, this.nodes.length);
}
private matrixDeletionHelper(index: number, length: number): number[][] {
let newMatrix = this.matrix.filter((_, i) => i !== index);
for (let x = 0; x < length; x++) {
newMatrix[x] = (newMatrix[x] as number[]).filter((_, i) => i !== index);
}
return newMatrix;
}
addEdge(from: T, to: T) {
const indexFrom = this.nodes.indexOf(from);
const indexTo = this.nodes.indexOf(to);
this.matrix[indexTo][indexFrom] = 1;
}
checkEdge(from: T, to: T) {
const indexFrom = this.nodes.indexOf(from);
const indexTo = this.nodes.indexOf(to);
return this.matrix[indexTo][indexFrom] === 1;
}
removeAllEdges(from: T) {
const indexFrom = this.nodes.indexOf(from);
for (let i = 0; i < this.nodes.length; i++) {
this.matrix[i][indexFrom] = 0;
}
}
removeEdge(from: T, to: T) {
const indexFrom = this.nodes.indexOf(from);
const indexTo = this.nodes.indexOf(to);
this.matrix[indexTo][indexFrom] = 0;
}
showEdges() {
console.log(` ${this.nodes.join(' ')}`);
for (let y = 0; y < this.matrix.length; y++) {
let row = `${this.nodes[y]} `;
for (let x = 0; x < this.matrix.length; x++) {
row += `${this.matrix[x][y]} `;
}
console.log(`${row}`);
}
}
}