Minimum Spanning Tree

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.

forked from bmershon's block: Minimum Spanning Tree

<!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>

https://d3js.org/d3.v4.min.js