Skip to content

Instantly share code, notes, and snippets.

@nitaku

nitaku/README.md

Last active December 31, 2015 00:59
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/7910706 to your computer and use it in GitHub Desktop.
Save nitaku/7910706 to your computer and use it in GitHub Desktop.
Download ZIP
Random tree
Raw
README.md

This example generates and visualizes a random tree. It uses a recursive algorithm similar to the simplest one I found in a survey about random trees used in genetic programming (Luke 2001). Hit reload to generate a different tree.

The generated tree has a maximum depth of 10, and for each node branches with a probability of 0.5 yielding at most 6 children.

Leaf nodes (depicted in gray) are placed after internal nodes (in white). The blue label shows an internal node's prefix, i.e. the path from the root node to it.

The implementation is based on this example by Mike Bostock, and customizes d3.js's tree layout to fit my taste.

Raw
index.coffee
rand_tree = (d, MAX_D, MAX_N, P, index) ->
### return a tree with maximum depth MAX_D that branches with probability P at most N times for each internal node ###
return {index: Infinity} if d is 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, P, 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.5, 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</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, P, index) {
/* return a tree with maximum depth MAX_D that branches with probability P at most N times for each internal node
*/
var child_i, children, i, n;
if (d === MAX_D) {
return {
index: Infinity
};
}
/* 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, P, 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.5, 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