| height: 960 | |
| border: no | |
| license: MIT |
Kruskal's Algorithm may be used to find the minimum spanning tree of a given graph. Kruskal's algorithm relies on a disjoint-set data structure.
Click and hold to see the minimum spanning tree for original graph.
Thicker red lines have a higher weight associated with them than thinner black lines. The minimum spanning tree avoids including higher cost edges.
| // https://en.wikipedia.org/wiki/Disjoint-set_data_structure | |
| (function(window) { | |
| function DisjointSet() { | |
| this.index_ = {}; | |
| } | |
| function Node(id) { | |
| this.id_ = id; | |
| this.parent_ = this; | |
| this.rank_ = 0; | |
| } | |
| DisjointSet.prototype.makeSet = function(id) { | |
| if (!this.index_[id]) { | |
| let created = new Node(id); | |
| this.index_[id] = created; | |
| } | |
| } | |
| // Returns the id of the representative element of this set that (id) | |
| // belongs to. | |
| DisjointSet.prototype.find = function(id) { | |
| if (this.index_[id] === undefined) { | |
| return undefined; | |
| } | |
| let current = this.index_[id].parent_; | |
| while (current !== current.parent_) { | |
| current = current.parent_; | |
| } | |
| return current.id_; | |
| } | |
| DisjointSet.prototype.union = function(x, y) { | |
| let xRoot = this.index_[this.find(x)]; | |
| let yRoot = this.index_[this.find(y)]; | |
| if (xRoot === undefined || yRoot === undefined || xRoot === yRoot) { | |
| // x and y already belong to the same set. | |
| return; | |
| } | |
| if (xRoot.rank < yRoot.rank) { // Move x into the set y is a member of. | |
| xRoot.parent_ = yRoot; | |
| } else if (yRoot.rank_ < xRoot.rank_) { // Move y into the set x is a member of. | |
| yRoot.parent_ = xRoot; | |
| } else { // Arbitrarily choose to move y into the set x is a member of. | |
| yRoot.parent_ = xRoot; | |
| xRoot.rank_++; | |
| } | |
| } | |
| // Returns the current number of disjoint sets. | |
| DisjointSet.prototype.size = function() { | |
| let uniqueIndices = {}; | |
| Object.keys(this.index_).forEach((id) => { | |
| let representative = this.find(id); | |
| uniqueIndices[id] = true; | |
| }); | |
| return Object.keys(uniqueIndices).length; | |
| } | |
| window.DisjointSet = DisjointSet; | |
| })(window); |
| <!DOCTYPE html> | |
| <meta charset="utf-8"> | |
| <title>Connected Network Reduction</title> | |
| <style> | |
| svg { | |
| cursor: pointer; | |
| pointer-events: all; | |
| } | |
| .nodes circle { | |
| stroke: none; | |
| } | |
| </style> | |
| <svg width="960" height="960"></svg> | |
| <script src="https://d3js.org/d3.v4.min.js"></script> | |
| <script src="disjoint-set.js"></script> | |
| <script src="kruskal-mst.js"></script> | |
| <script> | |
| var svg = d3.select("svg"), | |
| width = +svg.attr("width"), | |
| height = +svg.attr("height"); | |
| var simulation = d3.forceSimulation() | |
| .force("link", d3.forceLink().id(function(d) { return d.id; }).strength(0.005)) | |
| .force("charge", d3.forceManyBody().strength(-200)) | |
| .force("center", d3.forceCenter(width / 2, height / 2)); | |
| var maxWeight = -Infinity; | |
| // Asynchronously load the graph, encoded as a CSV file (without a header). | |
| d3.text("network.csv", function(error, adjacency) { | |
| if (error) throw error; | |
| var graph = {}; | |
| graph.nodes = []; | |
| graph.links = []; | |
| function makeNode(id) { | |
| return {"id": id}; | |
| } | |
| function makeLink(sourceId, targetId, weight) { | |
| return {"source": sourceId, "target": targetId, "weight": weight}; | |
| } | |
| total = 0 | |
| d3.csvParseRows(adjacency, (row, sourceId) => { | |
| graph.nodes.push(makeNode(sourceId)); | |
| row.forEach((weight, targetId) => { | |
| if (targetId > sourceId && weight !== "-") { | |
| total += +weight; | |
| maxWeight = Math.max(maxWeight, +weight); | |
| graph.links.push(makeLink(sourceId, targetId, +weight)); | |
| } | |
| }); | |
| }); | |
| let minimumSpanningTree = mst(graph); | |
| let includedEdgeMap = {}; | |
| // Create a Hash Map with unique identifiers for the edges/links included | |
| // in the minimum spanning tree. | |
| minimumSpanningTree.links.forEach((link) => { | |
| includedEdgeMap[linkId(link)] = true; | |
| }); | |
| // Flag edges for rendering with a boolean indicating whether they are | |
| // part of the minimum spanning tree for the graph. | |
| graph.links.forEach((link) => { | |
| link.mst = (includedEdgeMap[linkId(link)] !== undefined); | |
| }); | |
| function linkId(link) { | |
| return link.source + "-" + link.target; | |
| } | |
| function linkColor(link) { | |
| return d3.interpolateRgb("black", "red")(link.weight / maxWeight); | |
| } | |
| function linkWidth(link) { | |
| return d3.scaleLinear() | |
| .domain([0, maxWeight]) | |
| .range([0.5, 3])(link.weight) + "px"; | |
| } | |
| var link = svg.append("g") | |
| .attr("class", "links") | |
| .selectAll("line") | |
| .data(graph.links) | |
| .enter().append("line") | |
| .attr("stroke", (d) => linkColor(d)) | |
| .attr("stroke-width", (d) => linkWidth(d)) | |
| .style("stroke-opacity", 0.3); | |
| var node = svg.append("g") | |
| .attr("class", "nodes") | |
| .selectAll("circle") | |
| .data(graph.nodes) | |
| .enter().append("circle") | |
| .attr("r", 2.5); | |
| node.append("title") | |
| .text(function(d) { return "node: " + d.id; }); | |
| link.append("title") | |
| .text(function(d) { | |
| return [d.source, "-", d.target, "(weight: " + d.weight + ")"].join(" "); | |
| }); | |
| // Kick off the simulation. | |
| simulation | |
| .nodes(graph.nodes) | |
| .on("tick", ticked); | |
| simulation.force("link") | |
| .links(graph.links); | |
| // Update positions, which will quickly stabilize as the simulation cools. | |
| function ticked() { | |
| link | |
| .attr("x1", function(d) { return d.source.x; }) | |
| .attr("y1", function(d) { return d.source.y; }) | |
| .attr("x2", function(d) { return d.target.x; }) | |
| .attr("y2", function(d) { return d.target.y; }); | |
| node | |
| .attr("cx", function(d) { return d.x; }) | |
| .attr("cy", function(d) { return d.y; }); | |
| } | |
| // Show the MST. | |
| svg.on("mousedown", () => { | |
| link.each(function (d) { | |
| d3.select(this).style("stroke-opacity", (d.mst) ? 0.3 : 0); | |
| }); | |
| }); | |
| // Show the entire graph. | |
| svg.on("mouseup", () => { | |
| link.each(function (d) { | |
| d3.select(this).style("stroke-opacity", 0.3); | |
| }); | |
| }); | |
| }); | |
| </script> |
| // See https://en.wikipedia.org/wiki/Kruskal%27s_algorithm\ | |
| // Depends on DisjointSet. | |
| (function(window) { | |
| window.mst = function(graph) { | |
| let vertices = graph.nodes, | |
| edges = graph.links.slice(0), | |
| selectedEdges = [], | |
| forest = new DisjointSet(); | |
| // Each vertex begins "disconnected" and isolated from all the others. | |
| vertices.forEach((vertex) => { | |
| forest.makeSet(vertex.id); | |
| }); | |
| // Sort edges in descending order of weight. We will pop edges beginning | |
| // from the end of the array. | |
| edges.sort((a, b) => { | |
| return -(a.weight - b.weight); | |
| }); | |
| while(edges.length && forest.size() > 1) { | |
| let edge = edges.pop(); | |
| if (forest.find(edge.source) !== forest.find(edge.target)) { | |
| forest.union(edge.source, edge.target); | |
| selectedEdges.push(edge); | |
| } | |
| } | |
| return { | |
| nodes: vertices, | |
| links: selectedEdges | |
| } | |
| } | |
| })(window); |
| - | - | - | 428 | 668 | 495 | 377 | 678 | - | 167 | - | - | 870 | - | 869 | 624 | 300 | 609 | 131 | - | 251 | - | - | - | 856 | 221 | 514 | - | 591 | 762 | 182 | 56 | - | 884 | 412 | 273 | 636 | - | - | 774 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| - | - | 262 | - | - | 508 | 472 | 799 | - | 956 | 578 | 363 | 940 | 143 | - | 162 | 122 | 910 | - | 729 | 802 | 941 | 922 | 573 | 531 | 539 | 667 | 607 | - | 920 | - | - | 315 | 649 | 937 | - | 185 | 102 | 636 | 289 | |
| - | 262 | - | - | 926 | - | 958 | 158 | 647 | 47 | 621 | 264 | 81 | - | 402 | 813 | 649 | 386 | 252 | 391 | 264 | 637 | 349 | - | - | - | 108 | - | 727 | 225 | 578 | 699 | - | 898 | 294 | - | 575 | 168 | 432 | 833 | |
| 428 | - | - | - | 366 | - | - | 635 | - | 32 | 962 | 468 | 893 | 854 | 718 | 427 | 448 | 916 | 258 | - | 760 | 909 | 529 | 311 | 404 | - | - | 588 | 680 | 875 | - | 615 | - | 409 | 758 | 221 | - | - | 76 | 257 | |
| 668 | - | 926 | 366 | - | - | - | 250 | 268 | - | 503 | 944 | - | 677 | - | 727 | 793 | 457 | 981 | 191 | - | - | - | 351 | 969 | 925 | 987 | 328 | 282 | 589 | - | 873 | 477 | - | - | 19 | 450 | - | - | - | |
| 495 | 508 | - | - | - | - | - | 765 | 711 | 819 | 305 | 302 | 926 | - | - | 582 | - | 861 | - | 683 | 293 | - | - | 66 | - | 27 | - | - | 290 | - | 786 | - | 554 | 817 | 33 | - | 54 | 506 | 386 | 381 | |
| 377 | 472 | 958 | - | - | - | - | - | - | 120 | 42 | - | 134 | 219 | 457 | 639 | 538 | 374 | - | - | - | 966 | - | - | - | - | - | 449 | 120 | 797 | 358 | 232 | 550 | - | 305 | 997 | 662 | 744 | 686 | 239 | |
| 678 | 799 | 158 | 635 | 250 | 765 | - | - | - | 35 | - | 106 | 385 | 652 | 160 | - | 890 | 812 | 605 | 953 | - | - | - | 79 | - | 712 | 613 | 312 | 452 | - | 978 | 900 | - | 901 | - | - | 225 | 533 | 770 | 722 | |
| - | - | 647 | - | 268 | 711 | - | - | - | 283 | - | 172 | - | 663 | 236 | 36 | 403 | 286 | 986 | - | - | 810 | 761 | 574 | 53 | 793 | - | - | 777 | 330 | 936 | 883 | 286 | - | 174 | - | - | - | 828 | 711 | |
| 167 | 956 | 47 | 32 | - | 819 | 120 | 35 | 283 | - | 50 | - | 565 | 36 | 767 | 684 | 344 | 489 | 565 | - | - | 103 | 810 | 463 | 733 | 665 | 494 | 644 | 863 | 25 | 385 | - | 342 | 470 | - | - | - | 730 | 582 | 468 | |
| - | 578 | 621 | 962 | 503 | 305 | 42 | - | - | 50 | - | 155 | 519 | - | - | 256 | 990 | 801 | 154 | 53 | 474 | 650 | 402 | - | - | - | 966 | - | - | 406 | 989 | 772 | 932 | 7 | - | 823 | 391 | - | - | 933 | |
| - | 363 | 264 | 468 | 944 | 302 | - | 106 | 172 | - | 155 | - | - | - | 380 | 438 | - | 41 | 266 | - | - | 104 | 867 | 609 | - | 270 | 861 | - | - | 165 | - | 675 | 250 | 686 | 995 | 366 | 191 | - | 433 | - | |
| 870 | 940 | 81 | 893 | - | 926 | 134 | 385 | - | 565 | 519 | - | - | 313 | 851 | - | - | - | 248 | 220 | - | 826 | 359 | 829 | - | 234 | 198 | 145 | 409 | 68 | 359 | - | 814 | 218 | 186 | - | - | 929 | 203 | - | |
| - | 143 | - | 854 | 677 | - | 219 | 652 | 663 | 36 | - | - | 313 | - | 132 | - | 433 | 598 | - | - | 168 | 870 | - | - | - | 128 | 437 | - | 383 | 364 | 966 | 227 | - | - | 807 | 993 | - | - | 526 | 17 | |
| 869 | - | 402 | 718 | - | - | 457 | 160 | 236 | 767 | - | 380 | 851 | 132 | - | - | 596 | 903 | 613 | 730 | - | 261 | - | 142 | 379 | 885 | 89 | - | 848 | 258 | 112 | - | 900 | - | - | 818 | 639 | 268 | 600 | - | |
| 624 | 162 | 813 | 427 | 727 | 582 | 639 | - | 36 | 684 | 256 | 438 | - | - | - | - | 539 | 379 | 664 | 561 | 542 | - | 999 | 585 | - | - | 321 | 398 | - | - | 950 | 68 | 193 | - | 697 | - | 390 | 588 | 848 | - | |
| 300 | 122 | 649 | 448 | 793 | - | 538 | 890 | 403 | 344 | 990 | - | - | 433 | 596 | 539 | - | - | 73 | - | 318 | - | - | 500 | - | 968 | - | 291 | - | - | 765 | 196 | 504 | 757 | - | 542 | - | 395 | 227 | 148 | |
| 609 | 910 | 386 | 916 | 457 | 861 | 374 | 812 | 286 | 489 | 801 | 41 | - | 598 | 903 | 379 | - | - | - | 946 | 136 | 399 | - | 941 | 707 | 156 | 757 | 258 | 251 | - | 807 | - | - | - | 461 | 501 | - | - | 616 | - | |
| 131 | - | 252 | 258 | 981 | - | - | 605 | 986 | 565 | 154 | 266 | 248 | - | 613 | 664 | 73 | - | - | 686 | - | - | 575 | 627 | 817 | 282 | - | 698 | 398 | 222 | - | 649 | - | - | - | - | - | 654 | - | - | |
| - | 729 | 391 | - | 191 | 683 | - | 953 | - | - | 53 | - | 220 | - | 730 | 561 | - | 946 | 686 | - | - | 389 | 729 | 553 | 304 | 703 | 455 | 857 | 260 | - | 991 | 182 | 351 | 477 | 867 | - | - | 889 | 217 | 853 | |
| 251 | 802 | 264 | 760 | - | 293 | - | - | - | - | 474 | - | - | 168 | - | 542 | 318 | 136 | - | - | - | - | 392 | - | - | - | 267 | 407 | 27 | 651 | 80 | 927 | - | 974 | 977 | - | - | 457 | 117 | - | |
| - | 941 | 637 | 909 | - | - | 966 | - | 810 | 103 | 650 | 104 | 826 | 870 | 261 | - | - | 399 | - | 389 | - | - | - | 202 | - | - | - | - | 867 | 140 | 403 | 962 | 785 | - | 511 | - | 1 | - | 707 | - | |
| - | 922 | 349 | 529 | - | - | - | - | 761 | 810 | 402 | 867 | 359 | - | - | 999 | - | - | 575 | 729 | 392 | - | - | 388 | 939 | - | 959 | - | 83 | 463 | 361 | - | - | 512 | 931 | - | 224 | 690 | 369 | - | |
| - | 573 | - | 311 | 351 | 66 | - | 79 | 574 | 463 | - | 609 | 829 | - | 142 | 585 | 500 | 941 | 627 | 553 | - | 202 | 388 | - | 164 | 829 | - | 620 | 523 | 639 | 936 | - | - | 490 | - | 695 | - | 505 | 109 | - | |
| 856 | 531 | - | 404 | 969 | - | - | - | 53 | 733 | - | - | - | - | 379 | - | - | 707 | 817 | 304 | - | - | 939 | 164 | - | - | 616 | 716 | 728 | - | 889 | 349 | - | 963 | 150 | 447 | - | 292 | 586 | 264 | |
| 221 | 539 | - | - | 925 | 27 | - | 712 | 793 | 665 | - | 270 | 234 | 128 | 885 | - | 968 | 156 | 282 | 703 | - | - | - | 829 | - | - | - | 822 | - | - | - | 736 | 576 | - | 697 | 946 | 443 | - | 205 | 194 | |
| 514 | 667 | 108 | - | 987 | - | - | 613 | - | 494 | 966 | 861 | 198 | 437 | 89 | 321 | - | 757 | - | 455 | 267 | - | 959 | - | 616 | - | - | - | 349 | 156 | 339 | - | 102 | 790 | 359 | - | 439 | 938 | 809 | 260 | |
| - | 607 | - | 588 | 328 | - | 449 | 312 | - | 644 | - | - | 145 | - | - | 398 | 291 | 258 | 698 | 857 | 407 | - | - | 620 | 716 | 822 | - | - | 293 | 486 | 943 | - | 779 | - | 6 | 880 | 116 | 775 | - | 947 | |
| 591 | - | 727 | 680 | 282 | 290 | 120 | 452 | 777 | 863 | - | - | 409 | 383 | 848 | - | - | 251 | 398 | 260 | 27 | 867 | 83 | 523 | 728 | - | 349 | 293 | - | 212 | 684 | 505 | 341 | 384 | 9 | 992 | 507 | 48 | - | - | |
| 762 | 920 | 225 | 875 | 589 | - | 797 | - | 330 | 25 | 406 | 165 | 68 | 364 | 258 | - | - | - | 222 | - | 651 | 140 | 463 | 639 | - | - | 156 | 486 | 212 | - | - | 349 | 723 | - | - | 186 | - | 36 | 240 | 752 | |
| 182 | - | 578 | - | - | 786 | 358 | 978 | 936 | 385 | 989 | - | 359 | 966 | 112 | 950 | 765 | 807 | - | 991 | 80 | 403 | 361 | 936 | 889 | - | 339 | 943 | 684 | - | - | 965 | 302 | 676 | 725 | - | 327 | 134 | - | 147 | |
| 56 | - | 699 | 615 | 873 | - | 232 | 900 | 883 | - | 772 | 675 | - | 227 | - | 68 | 196 | - | 649 | 182 | 927 | 962 | - | - | 349 | 736 | - | - | 505 | 349 | 965 | - | 474 | 178 | 833 | - | - | 555 | 853 | - | |
| - | 315 | - | - | 477 | 554 | 550 | - | 286 | 342 | 932 | 250 | 814 | - | 900 | 193 | 504 | - | - | 351 | - | 785 | - | - | - | 576 | 102 | 779 | 341 | 723 | 302 | 474 | - | 689 | - | - | - | 451 | - | - | |
| 884 | 649 | 898 | 409 | - | 817 | - | 901 | - | 470 | 7 | 686 | 218 | - | - | - | 757 | - | - | 477 | 974 | - | 512 | 490 | 963 | - | 790 | - | 384 | - | 676 | 178 | 689 | - | 245 | 596 | 445 | - | - | 343 | |
| 412 | 937 | 294 | 758 | - | 33 | 305 | - | 174 | - | - | 995 | 186 | 807 | - | 697 | - | 461 | - | 867 | 977 | 511 | 931 | - | 150 | 697 | 359 | 6 | 9 | - | 725 | 833 | - | 245 | - | 949 | - | 270 | - | 112 | |
| 273 | - | - | 221 | 19 | - | 997 | - | - | - | 823 | 366 | - | 993 | 818 | - | 542 | 501 | - | - | - | - | - | 695 | 447 | 946 | - | 880 | 992 | 186 | - | - | - | 596 | 949 | - | 91 | - | 768 | 273 | |
| 636 | 185 | 575 | - | 450 | 54 | 662 | 225 | - | - | 391 | 191 | - | - | 639 | 390 | - | - | - | - | - | 1 | 224 | - | - | 443 | 439 | 116 | 507 | - | 327 | - | - | 445 | - | 91 | - | 248 | - | 344 | |
| - | 102 | 168 | - | - | 506 | 744 | 533 | - | 730 | - | - | 929 | - | 268 | 588 | 395 | - | 654 | 889 | 457 | - | 690 | 505 | 292 | - | 938 | 775 | 48 | 36 | 134 | 555 | 451 | - | 270 | - | 248 | - | 371 | 680 | |
| - | 636 | 432 | 76 | - | 386 | 686 | 770 | 828 | 582 | - | 433 | 203 | 526 | 600 | 848 | 227 | 616 | - | 217 | 117 | 707 | 369 | 109 | 586 | 205 | 809 | - | - | 240 | - | 853 | - | - | - | 768 | - | 371 | - | 540 | |
| 774 | 289 | 833 | 257 | - | 381 | 239 | 722 | 711 | 468 | 933 | - | - | 17 | - | - | 148 | - | - | 853 | - | - | - | - | 264 | 194 | 260 | 947 | - | 752 | 147 | - | - | 343 | 112 | 273 | 344 | 680 | 540 | - |
Hello! Can you help me implement this algorithm on my data set (not csv but json)?