nitaku/README.md

## README.md

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

  
## 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")


## index.css
.node circle {
  stroke: steelblue;
  stroke-width: 2px;
}

.node {
  font: 10px sans-serif;
}

.link {
  fill: none;
  stroke: #ccccdd;
  stroke-width: 1.5px;
}

## 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>

## 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);

## index.sass
.node circle
    stroke: steelblue
    stroke-width: 2px

.node
    font: 10px sans-serif

.link
    fill: none
    stroke: #ccd
    stroke-width: 1.5px


## thumbnail.png

      
    Raw
  

              thumbnail.png
	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;
	}
	<!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>
	(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);
	.node circle
	stroke: steelblue
	stroke-width: 2px

	.node
	font: 10px sans-serif

	.link
	fill: none
	stroke: #ccd
	stroke-width: 1.5px