Skip to content

Instantly share code, notes, and snippets.

@nitaku

nitaku/README.md

Last active January 2, 2016 03:29
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/8244446 to your computer and use it in GitHub Desktop.
Save nitaku/8244446 to your computer and use it in GitHub Desktop.
Download ZIP
Random tree (unordered)
Raw
README.md

Another example of random rooted trees (see also random tree and random tree II). Reload the page to generate a new tree.

This time, the tree is unordered, i.e. it doesn't have any natural ordering, except for the partial one implied by the hierarchy. Therefore, sibling nodes can be placed in arbitrary order in the visualization. This leads to possibly have many different visualizations for the same unordered rooted tree (only its topology is relevant), that is undesirable.

In order to reduce the degrees of freedom of the visualization, the tree is sorted by subtree height: Taller subtrees are drawn before shorter ones. This partial ordering does not solve the problem completely, leaving unmanaged many cases of ambiguity (e.g. two sibling subtrees with the same height). See this more advanced example for an unambiguous solution to this problem.

Raw
index.coffee
rand_tree = (d, MAX_D, MAX_N) ->
### 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 {height: 0} 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
children = []
for i in [0...n]
if p >= Math.random()
children.push rand_tree(d+1, MAX_D, MAX_N)
else
children.push {height: 0}
children.sort((a,b) -> b.height - a.height)
return {
height: d3.max(children, (d) -> d.height) + 1,
children: children
}
width = 960
distance = 14
margin = 40
max_depth = 10
d3.select(self.frameElement).style('height', "#{2*margin}px")
window.main = () ->
### create the tree ###
root = rand_tree(1, max_depth, 3)
### 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)
### 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 'steelblue')
### 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: steelblue;
stroke-width: 2px;
}
.node {
font: 10px sans-serif;
}
.link {
fill: none;
stroke: #ccccdd;
stroke-width: 1.5px;
}
Raw
index.html
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title>Random tree (unlabeled)</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) {
/* 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 children, i, n, p;
if (d === MAX_D) {
return {
height: 0
};
}
p = (MAX_D - d) / MAX_D;
/* if the tree branches, at least one branch is made
*/
n = Math.floor(Math.random() * MAX_N) + 1;
children = [];
for (i = 0; 0 <= n ? i < n : i > n; 0 <= n ? i++ : i--) {
if (p >= Math.random()) {
children.push(rand_tree(d + 1, MAX_D, MAX_N));
} else {
children.push({
height: 0
});
}
}
children.sort(function(a, b) {
return b.height - a.height;
});
return {
height: d3.max(children, function(d) {
return d.height;
}) + 1,
children: children
};
};
width = 960;
distance = 14;
margin = 40;
max_depth = 10;
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, 3);
/* 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);
});
/* 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 'steelblue';
}
});
/* 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: steelblue
stroke-width: 2px
.node
font: 10px sans-serif
.link
fill: none
stroke: #ccd
stroke-width: 1.5px
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment