This example shows a canonical (non-ambiguous) representation of a randomly generated unordered rooted tree. Reload to generate a new one. This is an improvement of a previous example.
Unordered rooted trees are trees (with a root) in which sibling order is not defined. Visualizing such trees often involves showing siblings in arbitrary order.
Serializations of unordered trees are often ordered, therefore, they are not necessarily equal to each other even if they represent the same unordered tree. A particular case is that of randomly generated trees.
If such serializations are fed into a tree layout algorithm, it can yield different representations of the same unordered tree, which is undesirable.
We perform a total ordering of the tree, based solely on topological features, which constrains an order-preserving tree layout algorithm to yield a single representation (barring other layout parameters). The total ordering is used to sort the tree before passing it to the layout algorithm. The method could also be applicable to some non-order-preserving layouts.
For an introduction on canonical representation of unordered trees, see Wright et al. 1986 (we still have to verify if our implementation yields the same results).
For an in-depth survey about tree drawing algorithms, see the chapter about tree drawing from the Handbook of Graph Drawing and Visualization (2013).
(function() {
var distance, margin, max_depth, rand_tree, width, zip;
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 {
children: []
};
}
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({
children: []
});
}
}
return {
children: children
};
};
width = 960;
distance = 14;
margin = 40;
max_depth = 10;
d3.select(self.frameElement).style('height', "" + (2 * margin) + "px");
/* python-like zip
*/
zip = function() {
var args, shortest;
args = [].slice.call(arguments);
shortest = args.length === 0 ? [] : args.reduce((function(a, b) {
if (a.length < b.length) {
return a;
} else {
return b;
}
}));
return shortest.map((function(_, i) {
return args.map(function(array) {
return array[i];
});
}));
};
window.main = function() {
/* create the tree
*/
var diagonal, height, link, links, node, nodes, root, rsort, tcmp, tree, vis;
root = rand_tree(1, max_depth, 3);
/* sort the tree
*/
tcmp = function(a, b) {
var ai, bi, ci, _i, _len, _ref, _ref2;
_ref = zip(a.children, b.children);
for (_i = 0, _len = _ref.length; _i < _len; _i++) {
_ref2 = _ref[_i], ai = _ref2[0], bi = _ref2[1];
ci = tcmp(ai, bi);
if (ci !== 0) return ci;
}
return b.children.length - a.children.length;
};
rsort = function(t) {
var c, _i, _len, _ref;
_ref = t.children;
for (_i = 0, _len = _ref.length; _i < _len; _i++) {
c = _ref[_i];
rsort(c);
}
return t.children.sort(tcmp);
};
rsort(root);
/* 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);
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title>Sorting an unordered rooted 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) ->
### 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 {children: []} 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 {children: []}
return {
children: children
}
width = 960
distance = 14
margin = 40
max_depth = 10
d3.select(self.frameElement).style('height', "#{2*margin}px")
### python-like zip ###
zip = () ->
args = [].slice.call(arguments)
shortest = if args.length == 0 then [] else args.reduce(((a,b) ->
if a.length < b.length then a else b
))
return shortest.map(((_,i) ->
args.map((array) -> array[i])
))
window.main = () ->
### create the tree ###
root = rand_tree(1, max_depth, 3)
### sort the tree ###
tcmp = (a,b) ->
for [ai, bi] in zip(a.children, b.children)
ci = tcmp(ai,bi)
if ci isnt 0
return ci
return b.children.length-a.children.length
rsort = (t) ->
for c in t.children
rsort(c)
t.children.sort(tcmp)
rsort(root)
### 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")
.node circle {
stroke: steelblue;
stroke-width: 2px;
}
.node {
font: 10px sans-serif;
}
.link {
fill: none;
stroke: #ccccdd;
stroke-width: 1.5px;
}
.node circle
stroke: steelblue
stroke-width: 2px
.node
font: 10px sans-serif
.link
fill: none
stroke: #ccd
stroke-width: 1.5px