Skip to content

Instantly share code, notes, and snippets.

@nitaku

nitaku/README.md

Last active December 31, 2015 05:09
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save nitaku/7938492 to your computer and use it in GitHub Desktop.
Save nitaku/7938492 to your computer and use it in GitHub Desktop.
Download ZIP
Random tree II
Raw
README.md

Another take on randomly generated trees. In random tree I, a node had a fixed probability of branching off. This time, the probability decreases linearly with the depth, starting at 1 for the root node and ending at 0 when the maximum depth is reached.

Raw
index.coffee
rand_tree = (d, MAX_D, MAX_N, index) ->
### return a tree with maximum depth MAX_D that branches with probability p at most N times for each internal node. p starts from 1 and decreases linearly with d, reaching zero at MAX_D ###
### this still seems to be necessary to avoid infinte recursion (floating point precision?) ###
return {index: Infinity} if d is MAX_D
p = (MAX_D-d)/MAX_D
### if the tree branches, at least one branch is made ###
n = Math.floor(Math.random()*MAX_N)+1
child_i = 0
children = []
for i in [0...n]
if p >= Math.random()
child_i += 1
children.push rand_tree(d+1, MAX_D, MAX_N, child_i)
else
children.push {index: Infinity}
children.sort((a,b) -> a.index - b.index)
return {
index: index,
children: children
}
width = 960
distance = 14
margin = 40
max_depth = 8
d3.select(self.frameElement).style('height', "#{2*margin}px")
window.main = () ->
### create the tree ###
root = rand_tree(1, max_depth, 4, 0)
root.index = ''
### initialize the layout ###
tree = d3.layout.tree()
.size([0, 0])
nodes = tree.nodes(root)
links = tree.links(nodes)
height = 0
### force the layout to display nodes in fixed rows and columns ###
nodes.forEach (n) ->
if n.parent? and n.parent.children[0] isnt n
height += distance
n.x = height
n.y = n.depth * (width / max_depth)
### define a method for computing an internal node's prefix ###
nodes.filter((d) -> d.children).forEach (n, i) ->
n.prefix = () -> (if n.parent? then n.parent.prefix() else '') + n.index
### draw the vis ###
diagonal = d3.svg.diagonal()
.projection((d) -> [d.y, d.x])
vis = d3.select('body').append('svg')
.attr('width', width)
.attr('height', height+2*margin)
.append('g')
.attr('transform', "translate(#{margin},#{margin})")
link = vis.selectAll('path.link')
.data(links)
.enter().append('path')
.attr('class', 'link')
.attr('d', diagonal)
node = vis.selectAll('g.node')
.data(nodes)
.enter().append('g')
.attr('class', 'node')
.attr('transform', (d) -> "translate(#{d.y},#{d.x})")
node.append('circle')
.attr('r', 4)
.attr('fill', (d) -> if d.children then 'white' else 'gray')
node.filter((d) -> d.children).append('text')
.attr('dx', (d) -> if d.children then -8 else 8)
.attr('dy', 3)
.attr('text-anchor', (d) -> if d.children then 'end' else 'start')
.text((d) -> d.prefix())
### adapt bl.ocks.org frame to the tree ###
d3.select(self.frameElement).transition().duration(500).style('height', "#{height+2*margin}px")
Raw
index.css
.node circle {
stroke: gray;
stroke-width: 2px;
}
.node {
font: 10px sans-serif;
}
.link {
fill: none;
stroke: #cccccc;
stroke-width: 1.5px;
}
.node text {
fill: steelblue;
font-style: italic;
}
Raw
index.html
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title>Random tree II</title>
<link type="text/css" href="index.css" rel="stylesheet"/>
<script src="http://d3js.org/d3.v3.min.js"></script>
<script src="index.js"></script>
</head>
<body onload="main()"></body>
</html>
Raw
index.js
(function() {
var distance, margin, max_depth, rand_tree, width;
rand_tree = function(d, MAX_D, MAX_N, index) {
/* return a tree with maximum depth MAX_D that branches with probability p at most N times for each internal node. p starts from 1 and decreases linearly with d, reaching zero at MAX_D
*/
/* this still seems to be necessary to avoid infinte recursion (floating point precision?)
*/
var child_i, children, i, n, p;
if (d === MAX_D) {
return {
index: Infinity
};
}
p = (MAX_D - d) / MAX_D;
/* if the tree branches, at least one branch is made
*/
n = Math.floor(Math.random() * MAX_N) + 1;
child_i = 0;
children = [];
for (i = 0; 0 <= n ? i < n : i > n; 0 <= n ? i++ : i--) {
if (p >= Math.random()) {
child_i += 1;
children.push(rand_tree(d + 1, MAX_D, MAX_N, child_i));
} else {
children.push({
index: Infinity
});
}
}
children.sort(function(a, b) {
return a.index - b.index;
});
return {
index: index,
children: children
};
};
width = 960;
distance = 14;
margin = 40;
max_depth = 8;
d3.select(self.frameElement).style('height', "" + (2 * margin) + "px");
window.main = function() {
/* create the tree
*/
var diagonal, height, link, links, node, nodes, root, tree, vis;
root = rand_tree(1, max_depth, 4, 0);
root.index = '';
/* initialize the layout
*/
tree = d3.layout.tree().size([0, 0]);
nodes = tree.nodes(root);
links = tree.links(nodes);
height = 0;
/* force the layout to display nodes in fixed rows and columns
*/
nodes.forEach(function(n) {
if ((n.parent != null) && n.parent.children[0] !== n) height += distance;
n.x = height;
return n.y = n.depth * (width / max_depth);
});
/* define a method for computing an internal node's prefix
*/
nodes.filter(function(d) {
return d.children;
}).forEach(function(n, i) {
return n.prefix = function() {
return (n.parent != null ? n.parent.prefix() : '') + n.index;
};
});
/* draw the vis
*/
diagonal = d3.svg.diagonal().projection(function(d) {
return [d.y, d.x];
});
vis = d3.select('body').append('svg').attr('width', width).attr('height', height + 2 * margin).append('g').attr('transform', "translate(" + margin + "," + margin + ")");
link = vis.selectAll('path.link').data(links).enter().append('path').attr('class', 'link').attr('d', diagonal);
node = vis.selectAll('g.node').data(nodes).enter().append('g').attr('class', 'node').attr('transform', function(d) {
return "translate(" + d.y + "," + d.x + ")";
});
node.append('circle').attr('r', 4).attr('fill', function(d) {
if (d.children) {
return 'white';
} else {
return 'gray';
}
});
node.filter(function(d) {
return d.children;
}).append('text').attr('dx', function(d) {
if (d.children) {
return -8;
} else {
return 8;
}
}).attr('dy', 3).attr('text-anchor', function(d) {
if (d.children) {
return 'end';
} else {
return 'start';
}
}).text(function(d) {
return d.prefix();
});
/* adapt bl.ocks.org frame to the tree
*/
return d3.select(self.frameElement).transition().duration(500).style('height', "" + (height + 2 * margin) + "px");
};
}).call(this);
Raw
index.sass
.node circle
stroke: gray
stroke-width: 2px
.node
font: 10px sans-serif
.link
fill: none
stroke: #ccc
stroke-width: 1.5px
.node text
fill: steelblue
font-style: italic
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment