lorenzopub · April 21, 2018 14:46
diff --git a/.block b/.block
 height: 960
 border: no
 license: MIT
diff --git a/README.md b/README.md
diff --git a/disjoint-set.js b/disjoint-set.js
 // 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);
diff --git a/index.html b/index.html
 <!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>
diff --git a/kruskal-mst.js b/kruskal-mst.js
 // 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);
diff --git a/network.csv b/network.csv
	// 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	-