Hept Tree

.block

license: mit

README.md

This visualization shows a hept tree that is a particular kind of tree having nodes with exactly 7 children. The hept tree is constructed starting from a random number converted to (→) base 7.

The experiment tries to explain how it is possible to create a Gosper Map, that is a particular kind of Treemap used in our Linked Data Maps approach. Each level of the tree, corresponds to an iteration of the Gosper Space Filling Curve that generates islands. Each island corresponds to a tile: at the first iteration is an hexagon, at the second one is the composition of 7 hexagons, at the thid one the composition of 49 hexagons and so on. Hence, the number hexagons composing an island at the ith iteration is equal to 7^i.

In the diagram, each iteration is reported directly above its corresponding level in the tree. The first iteration is the rightmost corresponding to the leaves of the hept tree.

So, this diagram allows to understand how a GosperMap composed by N hexagons can be constructed in term of islands/tiles. For instance, a GosperMap:

• where N = 6 (base10) → 6 (base7), will have 6 tile of order zero;
• where N = 13 (base10) → 16 (base7), will have 1 tile of order one (= 7 tiles of order zero) and 6 tile of order zero;
• where N = 58 (base10) → 112 (base7), will have 1 tile of order two (= 49 tiles of order zero), one tile of order 1 (= 7 tiles of order zero) and 2 tile of order zero.

Blue, white and lightblue hexagons respectevely represent a full, empty and partially full island.

forked from fabiovalse's block: Hept Tree

forked from anonymous's block: Hept Tree

forked from anonymous's block: Hept Tree

forked from anonymous's block: Hept Tree

index.coffee

width = 960
height = 500

distance = 16
max_depth = 10
radius = 8

svg = d3.select 'svg'
  .attr
    width: width
    height: height
    
vis = svg.append 'g'
  .attr
    transform: "translate(50, 100)"

get_children = () ->
  return [{name: '', type: '', children: []}, {name: '', type: '', children: []}, {name: '', type: '', children: []}, {name: '', type: '', children: []}, {name: '', type: '', children: []}, {name: '', type: '', children: []}, {name: '', type: '', children: []}]
    
# Given a base10 number, returns the base7 conversion
base10_to_base7 = (n) ->
  base7 = []
  
  while n > 0
    base7.unshift(n%7)
    n = Math.floor(n/7)
  
  return base7

# Given a base7 number, returns the corresponding HEPT TREE structure
make_tree = (node, base10_n, base7_n) ->
  
  for child,i in node.children
    # FULL
    if i < parseInt(base7_n[0])
      child.type = 'full'
    # PARTIALLY FULL
    else if i is parseInt(base7_n[0]) and base7_n.length > 1 and !((base7_n.reduce (t, s) -> t + s) is base7_n[0])
      child.type = if base10_n%Math.pow(7,base7_n.length) is 0 or base7_n.length is 1 then 'full' else 'partially full'
      
      if !(Math.pow(7,base7_n.length) is 0)
        child.children = get_children()
        make_tree(child, base10_n/7, base7_n.slice(1))
    # EMPTY
    else
      child.type = 'empty'
  
  return node

### Tree construction ###
n = Math.floor(Math.random()*1000)
base7_n = base10_to_base7 n

tree = {
  name: 'root',
  type: (if (base7_n.reduce (t, s) -> t + s) is 1 then 'full' else 'partially full'),
  children: get_children()
}

data = make_tree tree, n, (if (base7_n.reduce (t, s) -> t + s) is 1 then base7_n.slice(1) else base7_n)

# Write the random number conversion
svg.append 'text'
  .html "#{n} → #{base7_n.join('')}"
  .attr
    class: 'number'
    x: 40
    y: 40

#
svg.selectAll '.order'
  .data(i for i in [0..base7_n.length])
 .enter().append 'text'
  .text (d,i) -> "#{base7_n.length-i}"
  .attr
    class: 'order'
    x: (d,i) -> 45+96*i
    y: 75

### Tree visualization ###
tree = d3.layout.tree()
  .size [0, 0]
        
nodes = tree.nodes data
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)

# 
diagonal = d3.svg.diagonal()
  .projection((d) -> [d.y, d.x])

link = vis.selectAll 'path.link'
  .data links
.enter().append('path')
  .attr
    class: 'link'
    d: diagonal

node = vis.selectAll 'g.node'
  .data nodes
.enter().append('g')
  .attr
    class: 'node'
    transform: (d) -> "translate(#{d.y},#{d.x})"

# HEXAGONS
hex_generate_svg_path = (scale) ->
  a = scale/2
  r = a / Math.sin(Math.PI/3)
  "M#{r} 0 L#{r/2} #{a} L#{-r/2} #{a} L#{-r} 0 L#{-r/2} #{-a} L#{r/2} #{-a} Z"
  
node.append 'path'
  .attr
    class: 'hex'
    d: (d) -> hex_generate_svg_path 12
    fill: (d) -> if d.type is 'full' then 'steelblue' else if d.type is 'empty' then 'white' else 'lightsteelblue'
  .append 'title'
    .text (d) -> d.type

index.css

html, body {
  margin: 0;
  padding: 0;
}

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

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

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

.number {
  fill: #333;
  font-family: sans-serif;
  font-size: 25px;
}

.hex {
  stroke: steelblue;
  stroke-width: 2px;
}

.order {
  fill: #333;
  font-family: sans-serif;
}

index.html

<!doctype html>
<html lang="en">
<head>
  <meta charset="utf-8">
  <title>Hept Tree</title>
  <meta name="description" content="Hept Tree">
  <script src="http://d3js.org/d3.v3.min.js"></script>
  <link rel="stylesheet" href="index.css">
</head>
<body>
  <svg></svg>
  <script src="index.js"></script>
</body>
</html>

index.js

// Generated by CoffeeScript 1.10.0
(function() {
  var base10_to_base7, base7_n, data, diagonal, distance, get_children, height, hex_generate_svg_path, i, link, links, make_tree, max_depth, n, node, nodes, radius, svg, tree, vis, width;

  width = 960;

  height = 500;

  distance = 16;

  max_depth = 10;

  radius = 8;

  svg = d3.select('svg').attr({
    width: width,
    height: height
  });

  vis = svg.append('g').attr({
    transform: "translate(50, 100)"
  });

  get_children = function() {
    return [
      {
        name: '',
        type: '',
        children: []
      }, {
        name: '',
        type: '',
        children: []
      }, {
        name: '',
        type: '',
        children: []
      }, {
        name: '',
        type: '',
        children: []
      }, {
        name: '',
        type: '',
        children: []
      }, {
        name: '',
        type: '',
        children: []
      }, {
        name: '',
        type: '',
        children: []
      }
    ];
  };

  base10_to_base7 = function(n) {
    var base7;
    base7 = [];
    while (n > 0) {
      base7.unshift(n % 7);
      n = Math.floor(n / 7);
    }
    return base7;
  };

  make_tree = function(node, base10_n, base7_n) {
    var child, i, j, len, ref;
    ref = node.children;
    for (i = j = 0, len = ref.length; j < len; i = ++j) {
      child = ref[i];
      if (i < parseInt(base7_n[0])) {
        child.type = 'full';
      } else if (i === parseInt(base7_n[0]) && base7_n.length > 1 && !((base7_n.reduce(function(t, s) {
        return t + s;
      })) === base7_n[0])) {
        child.type = base10_n % Math.pow(7, base7_n.length) === 0 || base7_n.length === 1 ? 'full' : 'partially full';
        if (!(Math.pow(7, base7_n.length) === 0)) {
          child.children = get_children();
          make_tree(child, base10_n / 7, base7_n.slice(1));
        }
      } else {
        child.type = 'empty';
      }
    }
    return node;
  };


  /* Tree construction */

  n = Math.floor(Math.random() * 1000);

  base7_n = base10_to_base7(n);

  tree = {
    name: 'root',
    type: ((base7_n.reduce(function(t, s) {
      return t + s;
    })) === 1 ? 'full' : 'partially full'),
    children: get_children()
  };

  data = make_tree(tree, n, ((base7_n.reduce(function(t, s) {
    return t + s;
  })) === 1 ? base7_n.slice(1) : base7_n));

  svg.append('text').html(n + " → " + (base7_n.join(''))).attr({
    "class": 'number',
    x: 40,
    y: 40
  });

  svg.selectAll('.order').data((function() {
    var j, ref, results;
    results = [];
    for (i = j = 0, ref = base7_n.length; 0 <= ref ? j <= ref : j >= ref; i = 0 <= ref ? ++j : --j) {
      results.push(i);
    }
    return results;
  })()).enter().append('text').text(function(d, i) {
    return "" + (base7_n.length - i);
  }).attr({
    "class": 'order',
    x: function(d, i) {
      return 45 + 96 * i;
    },
    y: 75
  });


  /* Tree visualization */

  tree = d3.layout.tree().size([0, 0]);

  nodes = tree.nodes(data);

  links = tree.links(nodes);

  height = 0;

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

  diagonal = d3.svg.diagonal().projection(function(d) {
    return [d.y, d.x];
  });

  link = vis.selectAll('path.link').data(links).enter().append('path').attr({
    "class": 'link',
    d: diagonal
  });

  node = vis.selectAll('g.node').data(nodes).enter().append('g').attr({
    "class": 'node',
    transform: function(d) {
      return "translate(" + d.y + "," + d.x + ")";
    }
  });

  hex_generate_svg_path = function(scale) {
    var a, r;
    a = scale / 2;
    r = a / Math.sin(Math.PI / 3);
    return "M" + r + " 0 L" + (r / 2) + " " + a + " L" + (-r / 2) + " " + a + " L" + (r/2) + " 0 L" + (-r / 2) + " " + (-a) + " L" + (r / 2) + " " + (-a) + " Z";
  };

  node.append('path').attr({
    "class": 'hex',
    d: function(d) {
      return hex_generate_svg_path(101);
    },
    fill: function(d) {
      if (d.type === 'full') {
        return 'steelblue';
      } else if (d.type === 'empty') {
        return 'white';
      } else {
        return 'lightsteelblue';
      }
    }
  }).append('title').text(function(d) {
    return d.type;
  });

}).call(this);