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.
(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);
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title>Random tree</title>
<link type="text/css" href="index.css" rel="stylesheet"/>
<script src="//d3js.org/d3.v3.min.js"></script>
<script src="index.js"></script>
</head>
<body onload="main()"></body>
</html>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")
.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;
}
.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