Skip to content

Instantly share code, notes, and snippets.

@bgschiller

bgschiller/README.md

Last active July 12, 2017 15:32
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save bgschiller/213ee4e6e9bfb4688faebaa1fd28a3e4 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save bgschiller/213ee4e6e9bfb4688faebaa1fd28a3e4 to your computer and use it in GitHub Desktop.
Download ZIP
Rectilinear Steiner Trees
Raw
README.md
Raw
index.html
<!DOCTYPE html>
<meta charset="utf-8">
<title>Rectilinear Steiner Trees</title>
<style>
body {
font: 13px sans-serif;
position: relative;
width: 960px;
height: 500px;
}
form {
position: absolute;
bottom: 10px;
left: 10px;
}
rect {
fill: none;
pointer-events: all;
}
circle,
.line {
fill: none;
stroke: steelblue;
stroke-width: 1.5px;
}
circle {
fill: #fff;
fill-opacity: .2;
cursor: move;
}
.selected {
fill: #ff7f0e;
stroke: #ff7f0e;
}
</style>
<form>
<label for="layout">Layout:</label>
<select id="layout"></select><br>
</form>
<script src="//d3js.org/d3.v3.min.js"></script>
<script src="//cdnjs.cloudflare.com/ajax/libs/underscore.js/1.8.3/underscore-min.js"></script>
<script>
// dependencies: kruskal.js, and union-find (transitive)
// union-find
function UnionFind(count) {
this.roots = new Array(count);
this.ranks = new Array(count);
for(var i=0; i<count; ++i) {
this.roots[i] = i;
this.ranks[i] = 0;
}
}
var proto = UnionFind.prototype
Object.defineProperty(proto, "length", {
"get": function() {
return this.roots.length
}
})
proto.makeSet = function() {
var n = this.roots.length;
this.roots.push(n);
this.ranks.push(0);
return n;
}
proto.find = function(x) {
var x0 = x
var roots = this.roots;
while(roots[x] !== x) {
x = roots[x]
}
while(roots[x0] !== x) {
var y = roots[x0]
roots[x0] = x
x0 = y
}
return x;
}
proto.link = function(x, y) {
var xr = this.find(x)
, yr = this.find(y);
if(xr === yr) {
return;
}
var ranks = this.ranks
, roots = this.roots
, xd = ranks[xr]
, yd = ranks[yr];
if(xd < yd) {
roots[xr] = yr;
} else if(yd < xd) {
roots[yr] = xr;
} else {
roots[yr] = xr;
++ranks[xr];
}
}
// kruskal.js
var Kruskal;
var MakeSet = UnionFind;
(function() {
"use strict";
// vertices hold data that will be used in the distance 'metric' function
// edges holds position in vertices list
//
Kruskal = {
kruskal: function( vertices, edges, metric )
{
var set = {};
var finalEdge = [];
var forest = new MakeSet( vertices.length );
var edgeDist = [];
for (var ind in edges)
{
var u = edges[ind][0];
var v = edges[ind][1];
var e = { edge: edges[ind], weight: metric( vertices[u], vertices[v] ) };
edgeDist.push(e);
}
edgeDist.sort( function(a, b) { return a.weight- b.weight; } );
for (var i=0; i<edgeDist.length; i++)
{
var u = edgeDist[i].edge[0];
var v = edgeDist[i].edge[1];
if ( forest.find(u) != forest.find(v) )
{
finalEdge.push( [ u, v ] );
forest.link( u, v );
}
}
return finalEdge;
}
}
if (typeof module !== 'undefined')
module.exports = Kruskal;
})();
</script>
<script>
// computeRSMT translated from github.com/Keydrain/Steiner-Tree-Visualization
function manhattanDist(a, b){
var dx = Math.abs(a[0] - b[0]),
dy = Math.abs(a[1] - b[1]);
return dx + dy;
}
function completeEdges(pts){
var ptsLen = pts.length, edges = [];
for (var i = 0; i < pts.length; i++){
for (var j = 0; j < i; j++){
edges.push([i, j]);
}
}
return edges;
}
function minSpanningTree(pts){
return Kruskal.kruskal(pts, completeEdges(pts), manhattanDist);
}
function lineBetween(a, b){
return [
[a, [a[0], b[1]]],
[[a[0], b[1]], b],
];
}
function edgesToLines(pts, edges){
var lines = [];
edges.forEach(function(e){
lines.push.apply(lines, lineBetween(pts[e[0]], pts[e[1]]));
});
return lines;
}
function minSpanningTreeLines(pts){
return edgesToLines(pts, minSpanningTree(pts));
}
function mstCost(lines){
return lines.reduce(
function(acc, curr){
return acc + manhattanDist.apply(this, curr);
}, 0);
}
function deltaMST(pts, testPt){
var currentMST = minSpanningTreeLines(pts),
togetherMST = minSpanningTreeLines(
[].concat.call([], pts, [testPt])
);
return mstCost(togetherMST) - mstCost(currentMST);
}
function hananPts(pts){
var hPts = [];
hPts.push.apply(hPts, pts);
pts.forEach(function(p1, ix){
pts.forEach(function(p2, jx){
if (ix !== jx){
hPts.push([
p1[0], p2[1]
]);
hPts.push([
p2[0], p1[1]
]);
}
});
});
return _.uniq(hPts, JSON.stringify);
}
function degreeByPtIx(edges){
return _.chain(edges)
.flatten('shallow')
.countBy(_.identity)
.value();
}
function steinerCandidatesWithCosts(pts){
var hPts = hananPts(pts),
newHpts = _.difference(
hPts.map(JSON.stringify),
pts.map(JSON.stringify)
).map(JSON.parse),
edges = minSpanningTreeLines(pts),
currCost = mstCost(edges);
// Include only those hanan points that
// cause a decrease in total mst cost
// Those are out steiner candidates.
return hPts
.map(function(hPt){
return {
pt: hPt,
deltaCost: currCost - mstCost(minSpanningTreeLines([].concat.call([], pts, [hPt]))),
};
})
.filter(function(hPt){
return hPt.deltaCost > 0;
});
}
function rectilinearSteinerPoints(pts){
var
candidateSet = [null],
steinerPts = [],
maxPt, mstEdges, degsByIx;
while (candidateSet.length > 0){
candidateSet = steinerCandidatesWithCosts([].concat.call([], pts, steinerPts));
if (candidateSet.length){
maxPt = _.max(candidateSet, 'deltaCost');
steinerPts.push(maxPt.pt);
}
// Keep only those steiner points whose degree in a current mst is
// more than 2.
mstEdges = minSpanningTree([].concat.call([], pts, steinerPts));
degsByIx = degreeByPtIx(mstEdges);
var steinerIxsToKeep = _.reject(
_.range(steinerPts.length),
(ptIx) => { degsByIx[ptIx + pts.length] <= 2; }
);
steinerPts = steinerIxsToKeep.map((ix) => steinerPts[ix]);
}
return steinerPts;
}
function rectilinearSteinerMinimumTree(pts){
var steinerPts = rectilinearSteinerPoints(pts);
return minSpanningTreeLines([].concat.call(
[], pts, steinerPts))
}
</script>
<script>
var pathLayout = rectilinearSteinerMinimumTree;
var width = 960,
height = 500;
var points = d3.range(1, 8).map(function(i) {
return [i * width / 8, 50 + Math.random() * (height - 100)];
});
var dragged = null,
selected = points[0];
var line = d3.svg.line();
var svg = d3.select("body").append("svg")
.attr("width", width)
.attr("height", height)
.attr("tabindex", 1);
svg.append("rect")
.attr("width", width)
.attr("height", height)
.on("mousedown", mousedown);
svg.append("g")
.attr("class", "paths")
.call(redraw);
d3.select(window)
.on("mousemove", mousemove)
.on("mouseup", mouseup)
.on("keydown", keydown);
d3.select("#layout")
.on("change", changeLayout)
.selectAll("option")
.data([
"Rectilinear Steiner",
"Minimum Spanning",
])
.enter().append("option")
.attr("value", _.identity)
.text(_.identity);
svg.node().focus();
function redraw() {
var path = svg.select("g.paths")
.selectAll('path')
.data(pathLayout(points));
path.enter()
.append('path')
.attr("class", "line")
path.attr("d", line);
path.exit().remove();
var circle = svg.selectAll("circle")
.data(points, function(d) { return d; });
circle.enter().append("circle")
.attr("r", 1e-6)
.on("mousedown", function(d) { selected = dragged = d; redraw(); })
.transition()
.duration(750)
.ease("elastic")
.attr("r", 6.5);
circle
.classed("selected", function(d) { return d === selected; })
.attr("cx", function(d) { return d[0]; })
.attr("cy", function(d) { return d[1]; });
circle.exit().remove();
if (d3.event) {
d3.event.preventDefault();
d3.event.stopPropagation();
}
}
function changeLayout() {
pathLayout = this.value === 'Minimum Spanning' ?
minSpanningTreeLines :
rectilinearSteinerMinimumTree;
redraw();
}
function mousedown() {
points.push(selected = dragged = d3.mouse(svg.node()));
redraw();
}
function mousemove() {
if (!dragged) return;
var m = d3.mouse(svg.node());
dragged[0] = Math.max(0, Math.min(width, m[0]));
dragged[1] = Math.max(0, Math.min(height, m[1]));
redraw();
}
function mouseup() {
if (!dragged) return;
mousemove();
dragged = null;
}
function keydown() {
if (!selected) return;
switch (d3.event.keyCode) {
case 8: // backspace
case 46: { // delete
var i = points.indexOf(selected);
points.splice(i, 1);
selected = points.length ? points[i > 0 ? i - 1 : 0] : null;
redraw();
break;
}
}
}
</script>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment