2023-02-23 15:35:45 +01:00
|
|
|
import { KeyPriorityQueue } from '../Data-Structures/Heap/KeyPriorityQueue'
|
2020-07-10 01:38:14 +05:30
|
|
|
class GraphWeightedUndirectedAdjacencyList {
|
|
|
|
|
// Weighted Undirected Graph class
|
2023-10-03 23:08:19 +02:00
|
|
|
constructor() {
|
2020-07-10 01:38:14 +05:30
|
|
|
this.connections = {}
|
|
|
|
|
}
|
|
|
|
|
|
2023-10-03 23:08:19 +02:00
|
|
|
addNode(node) {
|
2020-07-10 01:38:14 +05:30
|
|
|
// Function to add a node to the graph (connection represented by set)
|
|
|
|
|
this.connections[node] = {}
|
|
|
|
|
}
|
|
|
|
|
|
2023-10-03 23:08:19 +02:00
|
|
|
addEdge(node1, node2, weight) {
|
2020-07-10 01:38:14 +05:30
|
|
|
// Function to add an edge (adds the node too if they are not present in the graph)
|
2023-10-03 23:08:19 +02:00
|
|
|
if (!(node1 in this.connections)) {
|
|
|
|
|
this.addNode(node1)
|
|
|
|
|
}
|
|
|
|
|
if (!(node2 in this.connections)) {
|
|
|
|
|
this.addNode(node2)
|
|
|
|
|
}
|
2020-07-10 01:38:14 +05:30
|
|
|
this.connections[node1][node2] = weight
|
|
|
|
|
this.connections[node2][node1] = weight
|
|
|
|
|
}
|
|
|
|
|
|
2023-10-03 23:08:19 +02:00
|
|
|
PrimMST(start) {
|
2020-08-01 09:11:19 +05:30
|
|
|
// Prim's Algorithm to generate a Minimum Spanning Tree (MST) of a graph
|
2020-07-10 01:38:14 +05:30
|
|
|
// Details: https://en.wikipedia.org/wiki/Prim%27s_algorithm
|
|
|
|
|
const distance = {}
|
|
|
|
|
const parent = {}
|
2023-02-23 15:35:45 +01:00
|
|
|
const priorityQueue = new KeyPriorityQueue()
|
2020-07-10 01:38:14 +05:30
|
|
|
// Initialization
|
|
|
|
|
for (const node in this.connections) {
|
2023-10-03 23:08:19 +02:00
|
|
|
distance[node] = node === start.toString() ? 0 : Infinity
|
2020-07-10 01:38:14 +05:30
|
|
|
parent[node] = null
|
|
|
|
|
priorityQueue.push(node, distance[node])
|
|
|
|
|
}
|
|
|
|
|
// Updating 'distance' object
|
|
|
|
|
while (!priorityQueue.isEmpty()) {
|
|
|
|
|
const node = priorityQueue.pop()
|
2023-10-03 23:08:19 +02:00
|
|
|
Object.keys(this.connections[node]).forEach((neighbour) => {
|
|
|
|
|
if (
|
|
|
|
|
priorityQueue.contains(neighbour) &&
|
|
|
|
|
distance[node] + this.connections[node][neighbour] <
|
|
|
|
|
distance[neighbour]
|
|
|
|
|
) {
|
|
|
|
|
distance[neighbour] =
|
|
|
|
|
distance[node] + this.connections[node][neighbour]
|
2020-07-10 01:38:14 +05:30
|
|
|
parent[neighbour] = node
|
|
|
|
|
priorityQueue.update(neighbour, distance[neighbour])
|
|
|
|
|
}
|
|
|
|
|
})
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
// MST Generation from the 'parent' object
|
|
|
|
|
const graph = new GraphWeightedUndirectedAdjacencyList()
|
2023-10-03 23:08:19 +02:00
|
|
|
Object.keys(parent).forEach((node) => {
|
2020-07-10 01:38:14 +05:30
|
|
|
if (node && parent[node]) {
|
|
|
|
|
graph.addEdge(node, parent[node], this.connections[node][parent[node]])
|
|
|
|
|
}
|
|
|
|
|
})
|
|
|
|
|
return graph
|
|
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
|
2021-10-10 17:55:08 +02:00
|
|
|
export { GraphWeightedUndirectedAdjacencyList }
|
