https://thomasahle.com/blog/tree.js

1// Can get some visual ideas from here
2// https://observablehq.com/@mbostock/tree-of-life
3//
4function link(curve) {
5  var radius = null,
6     angle = null;
7  function link(d) {
8     context = d3.path();
9     curve(context, radius(d.source), angle(d.source), radius(d.target), angle(d.target));
10     return context;
11  }
12  link.radius = function(f) {
13     radius = f;
14     return link;
15  };
16  link.angle = function(f) {
17     angle = f;
18     return link;
19  };
20  return link;
21}
22
23function curveArc(context, r0, a0, r1, a1) {
24  var p0 = d3.pointRadial(a0+Math.PI/2, r0),
25      p1 = d3.pointRadial(a0+Math.PI/2, (r0 + r1) / 2),
26      p2 = d3.pointRadial(a1+Math.PI/2, (r0 + r1) / 2),
27      p3 = d3.pointRadial(a1+Math.PI/2, r1);
28
29  context.moveTo(p0[0], p0[1]);
30  context.lineTo(p1[0], p1[1]);
31  context.arc(0, 0, (r0+r1)/2, a0, a1, a1<a0);
32  context.lineTo(p3[0], p3[1]);
33
34  // context.moveTo(p0[0], p0[1]);
35  // context.arc(0, 0, r0, a0-Math.PI/2, a1-Math.PI/2, a1<a0);
36  // context.lineTo(p3[0], p3[1]);
37}
38
39function linkRadial2() {
40   return link(curveArc);
41}
42
43class RadialTree {
44   constructor(radius) {
45      this.radius = radius;
46      this.tree = d3.tree().size([2*Math.PI, this.radius]);
47      this.duration = 1000;
48      this.dispatch = d3.dispatch('change');
49   }
50   reset(init_degree, p, t, d) {
51      this.p = p;
52      this.t = t;
53      this.d = d;
54      this.root = d3.hierarchy({
55         name: '',
56         value: 0,
57         id: 0,
58         alive: true
59      });
60      this.id_counter = 1;
61      this.root.x0 = 0;
62      this.root.y0 = 0;
63      for (let i = 0; i < init_degree; i++) {
64         this.insert(this.root, {name: '', value: 0, alive: true});
65      }
66      this.total_size = 1;
67   }
68   insert(par, data) {
69      data.id = this.id_counter++;
70      const newNode = d3.hierarchy(data);
71      newNode.x0 = par.x0;
72      newNode.y0 = par.y0;
73      newNode.depth = par.depth + 1;
74      newNode.parent = par;
75      // Walk up the tree, updating the heights of ancestors as needed.
76      // Could perhaps be done also with newNode.decendants().each.
77      for(let height = 1, anc = par; anc != null; height++, anc=anc.parent) {
78         anc.height = Math.max(anc.height, height);
79      }
80      if (!par.children)
81         par.children = [];
82      par.children.push(newNode);
83   }
84   step() {
85      const level = this.root.height;
86      const level_size = Math.ceil(Math.pow(this.d, level)/this.total_size);
87      this.total_size *= level_size;
88      this.root.each(node => {
89         if (node.depth == level && node.data.alive) {
90            for (let i = 0; i < level_size; i++) {
91               const val = node.data.value + (Math.random() < this.p ? 1 : 0);
92               // The proven bound uses (rat**2 * sig**2 * k)**1/3. Probably
93               // something can be done that uses `level` instead of k, but it
94               // would likely cost some loglog factor to make sure it survives
95               // forever.
96               //
97               // const rat = this.t == 0 || this.t == 1 ? 0
98               //             : Math.log(this.t/this.p * (1-this.p)/(1-this.t));
99               // const sig = Math.pow(rat**2 * this.t*(1-this.t)*level, 1/3);
100               //
101               // Maybe the reason 1/3 is good is that I would actually prefer the
102               // process to die at some point, before the browswer gets overloaded.
103               const sig = Math.pow(this.t*(1-this.t)*level, 1/3);
104               this.insert(node, {
105                  name: val+'/'+level,
106                  value: val,
107                  alive: this.t >= this.p ? val >= this.t*level-sig : val <= this.t*level+sig,
108                  id: this.id_counter++
109               });
110            }
111         }
112      });
113   }
114   isAlive() {
115      const level = this.root.height;
116      let res = false;
117      this.root.each(node => {
118         if (node.depth == level && node.data.alive)
119            res = true;
120      });
121      return res;
122   }
123   mount(svg) {
124      this.svg = svg
125         .classed('radial_tree', true);
126      const r = this.radius;
127      const p = 15;
128      svg.attr('width', 2*r)
129         .attr('height', 2*r)
130         .attr('viewBox', [-r-p, -r-p, 2*r+2*p, 2*r+2*p]);
131      this.g = svg.append("g")
132   }
133   update() {
134      this.tree(this.root);
135      this.dispatch.call('change');
136      const links = this.root.links();
137      const nodes = this.root.descendants();
138
139      // Compute the new tree layout.
140      //const size = size_radial();
141      const transition = this.svg.transition()
142         .duration(this.duration)
143      // Animate resize of svg element to fit new data
144         //.attr("viewBox", [-margin.left, - margin.top, size.width, size.height])
145      // Some sort of hack to make the window realize it needs to resize?
146         .tween("resize", window.ResizeObserver ? null : () => () => this.svg.dispatch("toggle"));
147
148      // Update the links. They take the id of their target.
149      const link = this.g.selectAll("path")
150         .data(links, d => d.target.data.id);
151
152      // Helper function for beizer paths
153      // const diagonal = d3.linkVertical().x(d => d.x).y(d => d.y);
154      const diagonal = linkRadial2().angle(d => d.x).radius(d => d.y);
155
156      // Enter any new links at the parent's previous position.
157      const linkEnter = link.enter().append("path");
158
159      // Transition links to their new position.
160      // Note: each link is an object that defines source and target properties
161      link.merge(linkEnter)
162         // We hide root links, since they don't really exist
163         .attr('visibility', d => d.source.depth == 0 ? 'hidden' : 'visible')
164         .transition(transition)
165         // We need to storre the old positions before they get updated at the end
166         // of the function. It turns out attrTween is too late.
167         .attr('d', li => {
168            li.source.x00 = li.source.x0;
169            li.source.y00 = li.source.y0;
170            // If there is no x0 (the newly entered items)i
171            // we make it pop out of the parent.
172            li.target.x00 = li.target.x0 || li.source.x0;
173            li.target.y00 = li.target.y0 || li.source.y0;
174         })
175         .attrTween("d", d => t => diagonal(
176               {source: {x: (1-t)*d.source.x00 + t*d.source.x,
177                         y: (1-t)*d.source.y00 + t*d.source.y},
178                target: {x: (1-t)*d.target.x00 + t*d.target.x,
179                         y: (1-t)*d.target.y00 + t*d.target.y}})
180         );
181
182      // We do the nodes after the links to have them on top
183      const nodeUpdate = this.g.selectAll('g.node')
184         .data(nodes, d => d.data.id);
185
186      const nodeEnter = nodeUpdate.enter().append("g").classed('node', true)
187         .attr('transform', d => `translate(
188               ${d.parent ? d.parent.y0 * Math.cos(d.parent.x0) : 0},
189               ${d.parent ? d.parent.y0 * Math.sin(d.parent.x0) : 0})`);
190
191      // Make shadows
192      nodeEnter.append('circle')
193         .clone()
194         .classed('shadow', true)
195         .lower();
196
197      nodeUpdate.merge(nodeEnter)
198         .classed("inner", d => d.height > 0)
199         .classed("alive", d => d.data.alive)
200         .transition(transition)
201         .attr('transform', d => `translate(
202               ${d.y * Math.cos(d.x)},
203               ${d.y * Math.sin(d.x)})`);
204
205      // We just use those for reset.
206      // But actually, the new structure doesn't require resets...
207      link.exit().remove();
208      nodeUpdate.exit().remove();
209
210      // Stash the old positions for transition.
211      this.root.each(d => {
212         d.x0 = d.x;
213         d.y0 = d.y;
214      });
215   }
216}
217