Skip to content

Instantly share code, notes, and snippets.

@nitaku

nitaku/README.md

Last active January 18, 2021 18:26
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
  • Save nitaku/8260510 to your computer and use it in GitHub Desktop.
Save nitaku/8260510 to your computer and use it in GitHub Desktop.
Download ZIP
Canonical representation of unordered rooted trees
Raw
README.md

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).

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 {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")
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>Sorting an unordered rooted 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, 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);
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