diff options
Diffstat (limited to 'visualize/static/d3.layout.js')
-rw-r--r-- | visualize/static/d3.layout.js | 1881 |
1 files changed, 0 insertions, 1881 deletions
diff --git a/visualize/static/d3.layout.js b/visualize/static/d3.layout.js deleted file mode 100644 index d93fbe5..0000000 --- a/visualize/static/d3.layout.js +++ /dev/null @@ -1,1881 +0,0 @@ -(function(){d3.layout = {}; -// Implements hierarchical edge bundling using Holten's algorithm. For each -// input link, a path is computed that travels through the tree, up the parent -// hierarchy to the least common ancestor, and then back down to the destination -// node. Each path is simply an array of nodes. -d3.layout.bundle = function() { - return function(links) { - var paths = [], - i = -1, - n = links.length; - while (++i < n) paths.push(d3_layout_bundlePath(links[i])); - return paths; - }; -}; - -function d3_layout_bundlePath(link) { - var start = link.source, - end = link.target, - lca = d3_layout_bundleLeastCommonAncestor(start, end), - points = [start]; - while (start !== lca) { - start = start.parent; - points.push(start); - } - var k = points.length; - while (end !== lca) { - points.splice(k, 0, end); - end = end.parent; - } - return points; -} - -function d3_layout_bundleAncestors(node) { - var ancestors = [], - parent = node.parent; - while (parent != null) { - ancestors.push(node); - node = parent; - parent = parent.parent; - } - ancestors.push(node); - return ancestors; -} - -function d3_layout_bundleLeastCommonAncestor(a, b) { - if (a === b) return a; - var aNodes = d3_layout_bundleAncestors(a), - bNodes = d3_layout_bundleAncestors(b), - aNode = aNodes.pop(), - bNode = bNodes.pop(), - sharedNode = null; - while (aNode === bNode) { - sharedNode = aNode; - aNode = aNodes.pop(); - bNode = bNodes.pop(); - } - return sharedNode; -} -d3.layout.chord = function() { - var chord = {}, - chords, - groups, - matrix, - n, - padding = 0, - sortGroups, - sortSubgroups, - sortChords; - - function relayout() { - var subgroups = {}, - groupSums = [], - groupIndex = d3.range(n), - subgroupIndex = [], - k, - x, - x0, - i, - j; - - chords = []; - groups = []; - - // Compute the sum. - k = 0, i = -1; while (++i < n) { - x = 0, j = -1; while (++j < n) { - x += matrix[i][j]; - } - groupSums.push(x); - subgroupIndex.push(d3.range(n)); - k += x; - } - - // Sort groups… - if (sortGroups) { - groupIndex.sort(function(a, b) { - return sortGroups(groupSums[a], groupSums[b]); - }); - } - - // Sort subgroups… - if (sortSubgroups) { - subgroupIndex.forEach(function(d, i) { - d.sort(function(a, b) { - return sortSubgroups(matrix[i][a], matrix[i][b]); - }); - }); - } - - // Convert the sum to scaling factor for [0, 2pi]. - // TODO Allow start and end angle to be specified. - // TODO Allow padding to be specified as percentage? - k = (2 * Math.PI - padding * n) / k; - - // Compute the start and end angle for each group and subgroup. - // Note: Opera has a bug reordering object literal properties! - x = 0, i = -1; while (++i < n) { - x0 = x, j = -1; while (++j < n) { - var di = groupIndex[i], - dj = subgroupIndex[di][j], - v = matrix[di][dj], - a0 = x, - a1 = x += v * k; - subgroups[di + "-" + dj] = { - index: di, - subindex: dj, - startAngle: a0, - endAngle: a1, - value: v - }; - } - groups.push({ - index: di, - startAngle: x0, - endAngle: x, - value: (x - x0) / k - }); - x += padding; - } - - // Generate chords for each (non-empty) subgroup-subgroup link. - i = -1; while (++i < n) { - j = i - 1; while (++j < n) { - var source = subgroups[i + "-" + j], - target = subgroups[j + "-" + i]; - if (source.value || target.value) { - chords.push(source.value < target.value - ? {source: target, target: source} - : {source: source, target: target}); - } - } - } - - if (sortChords) resort(); - } - - function resort() { - chords.sort(function(a, b) { - return sortChords( - (a.source.value + a.target.value) / 2, - (b.source.value + b.target.value) / 2); - }); - } - - chord.matrix = function(x) { - if (!arguments.length) return matrix; - n = (matrix = x) && matrix.length; - chords = groups = null; - return chord; - }; - - chord.padding = function(x) { - if (!arguments.length) return padding; - padding = x; - chords = groups = null; - return chord; - }; - - chord.sortGroups = function(x) { - if (!arguments.length) return sortGroups; - sortGroups = x; - chords = groups = null; - return chord; - }; - - chord.sortSubgroups = function(x) { - if (!arguments.length) return sortSubgroups; - sortSubgroups = x; - chords = null; - return chord; - }; - - chord.sortChords = function(x) { - if (!arguments.length) return sortChords; - sortChords = x; - if (chords) resort(); - return chord; - }; - - chord.chords = function() { - if (!chords) relayout(); - return chords; - }; - - chord.groups = function() { - if (!groups) relayout(); - return groups; - }; - - return chord; -}; -// A rudimentary force layout using Gauss-Seidel. -d3.layout.force = function() { - var force = {}, - event = d3.dispatch("tick"), - size = [1, 1], - drag, - alpha, - friction = .9, - linkDistance = d3_layout_forceLinkDistance, - linkStrength = d3_layout_forceLinkStrength, - charge = -30, - gravity = .1, - theta = .8, - interval, - nodes = [], - links = [], - distances, - strengths, - charges; - - function repulse(node) { - return function(quad, x1, y1, x2, y2) { - if (quad.point !== node) { - var dx = quad.cx - node.x, - dy = quad.cy - node.y, - dn = 1 / Math.sqrt(dx * dx + dy * dy); - - /* Barnes-Hut criterion. */ - if ((x2 - x1) * dn < theta) { - var k = quad.charge * dn * dn; - node.px -= dx * k; - node.py -= dy * k; - return true; - } - - if (quad.point && isFinite(dn)) { - var k = quad.pointCharge * dn * dn; - node.px -= dx * k; - node.py -= dy * k; - } - } - return !quad.charge; - }; - } - - function tick() { - var n = nodes.length, - m = links.length, - q, - i, // current index - o, // current object - s, // current source - t, // current target - l, // current distance - k, // current force - x, // x-distance - y; // y-distance - - // gauss-seidel relaxation for links - for (i = 0; i < m; ++i) { - o = links[i]; - s = o.source; - t = o.target; - x = t.x - s.x; - y = t.y - s.y; - if (l = (x * x + y * y)) { - l = alpha * strengths[i] * ((l = Math.sqrt(l)) - distances[i]) / l; - x *= l; - y *= l; - t.x -= x * (k = s.weight / (t.weight + s.weight)); - t.y -= y * k; - s.x += x * (k = 1 - k); - s.y += y * k; - } - } - - // apply gravity forces - if (k = alpha * gravity) { - x = size[0] / 2; - y = size[1] / 2; - i = -1; if (k) while (++i < n) { - o = nodes[i]; - o.x += (x - o.x) * k; - o.y += (y - o.y) * k; - } - } - - // compute quadtree center of mass and apply charge forces - if (charge) { - d3_layout_forceAccumulate(q = d3.geom.quadtree(nodes), alpha, charges); - i = -1; while (++i < n) { - if (!(o = nodes[i]).fixed) { - q.visit(repulse(o)); - } - } - } - - // position verlet integration - i = -1; while (++i < n) { - o = nodes[i]; - if (o.fixed) { - o.x = o.px; - o.y = o.py; - } else { - o.x -= (o.px - (o.px = o.x)) * friction; - o.y -= (o.py - (o.py = o.y)) * friction; - } - } - - event.tick({type: "tick", alpha: alpha}); - - // simulated annealing, basically - return (alpha *= .99) < .005; - } - - force.nodes = function(x) { - if (!arguments.length) return nodes; - nodes = x; - return force; - }; - - force.links = function(x) { - if (!arguments.length) return links; - links = x; - return force; - }; - - force.size = function(x) { - if (!arguments.length) return size; - size = x; - return force; - }; - - force.linkDistance = function(x) { - if (!arguments.length) return linkDistance; - linkDistance = d3.functor(x); - return force; - }; - - // For backwards-compatibility. - force.distance = force.linkDistance; - - force.linkStrength = function(x) { - if (!arguments.length) return linkStrength; - linkStrength = d3.functor(x); - return force; - }; - - force.friction = function(x) { - if (!arguments.length) return friction; - friction = x; - return force; - }; - - force.charge = function(x) { - if (!arguments.length) return charge; - charge = typeof x === "function" ? x : +x; - return force; - }; - - force.gravity = function(x) { - if (!arguments.length) return gravity; - gravity = x; - return force; - }; - - force.theta = function(x) { - if (!arguments.length) return theta; - theta = x; - return force; - }; - - force.start = function() { - var i, - j, - n = nodes.length, - m = links.length, - w = size[0], - h = size[1], - neighbors, - o; - - for (i = 0; i < n; ++i) { - (o = nodes[i]).index = i; - o.weight = 0; - } - - distances = []; - strengths = []; - for (i = 0; i < m; ++i) { - o = links[i]; - if (typeof o.source == "number") o.source = nodes[o.source]; - if (typeof o.target == "number") o.target = nodes[o.target]; - distances[i] = linkDistance.call(this, o, i); - strengths[i] = linkStrength.call(this, o, i); - ++o.source.weight; - ++o.target.weight; - } - - for (i = 0; i < n; ++i) { - o = nodes[i]; - if (isNaN(o.x)) o.x = position("x", w); - if (isNaN(o.y)) o.y = position("y", h); - if (isNaN(o.px)) o.px = o.x; - if (isNaN(o.py)) o.py = o.y; - } - - charges = []; - if (typeof charge === "function") { - for (i = 0; i < n; ++i) { - charges[i] = +charge.call(this, nodes[i], i); - } - } else { - for (i = 0; i < n; ++i) { - charges[i] = charge; - } - } - - // initialize node position based on first neighbor - function position(dimension, size) { - var neighbors = neighbor(i), - j = -1, - m = neighbors.length, - x; - while (++j < m) if (!isNaN(x = neighbors[j][dimension])) return x; - return Math.random() * size; - } - - // initialize neighbors lazily - function neighbor() { - if (!neighbors) { - neighbors = []; - for (j = 0; j < n; ++j) { - neighbors[j] = []; - } - for (j = 0; j < m; ++j) { - var o = links[j]; - neighbors[o.source.index].push(o.target); - neighbors[o.target.index].push(o.source); - } - } - return neighbors[i]; - } - - return force.resume(); - }; - - force.resume = function() { - alpha = .1; - d3.timer(tick); - return force; - }; - - force.stop = function() { - alpha = 0; - return force; - }; - - // use `node.call(force.drag)` to make nodes draggable - force.drag = function() { - if (!drag) drag = d3.behavior.drag() - .origin(Object) - .on("dragstart", dragstart) - .on("drag", d3_layout_forceDrag) - .on("dragend", d3_layout_forceDragEnd); - - this.on("mouseover.force", d3_layout_forceDragOver) - .on("mouseout.force", d3_layout_forceDragOut) - .call(drag); - }; - - function dragstart(d) { - d3_layout_forceDragOver(d3_layout_forceDragNode = d); - d3_layout_forceDragForce = force; - } - - return d3.rebind(force, event, "on"); -}; - -var d3_layout_forceDragForce, - d3_layout_forceDragNode; - -function d3_layout_forceDragOver(d) { - d.fixed |= 2; -} - -function d3_layout_forceDragOut(d) { - if (d !== d3_layout_forceDragNode) d.fixed &= 1; -} - -function d3_layout_forceDragEnd() { - d3_layout_forceDrag(); - d3_layout_forceDragNode.fixed &= 1; - d3_layout_forceDragForce = d3_layout_forceDragNode = null; -} - -function d3_layout_forceDrag() { - d3_layout_forceDragNode.px = d3.event.x; - d3_layout_forceDragNode.py = d3.event.y; - d3_layout_forceDragForce.resume(); // restart annealing -} - -function d3_layout_forceAccumulate(quad, alpha, charges) { - var cx = 0, - cy = 0; - quad.charge = 0; - if (!quad.leaf) { - var nodes = quad.nodes, - n = nodes.length, - i = -1, - c; - while (++i < n) { - c = nodes[i]; - if (c == null) continue; - d3_layout_forceAccumulate(c, alpha, charges); - quad.charge += c.charge; - cx += c.charge * c.cx; - cy += c.charge * c.cy; - } - } - if (quad.point) { - // jitter internal nodes that are coincident - if (!quad.leaf) { - quad.point.x += Math.random() - .5; - quad.point.y += Math.random() - .5; - } - var k = alpha * charges[quad.point.index]; - quad.charge += quad.pointCharge = k; - cx += k * quad.point.x; - cy += k * quad.point.y; - } - quad.cx = cx / quad.charge; - quad.cy = cy / quad.charge; -} - -function d3_layout_forceLinkDistance(link) { - return 20; -} - -function d3_layout_forceLinkStrength(link) { - return 1; -} -d3.layout.partition = function() { - var hierarchy = d3.layout.hierarchy(), - size = [1, 1]; // width, height - - function position(node, x, dx, dy) { - var children = node.children; - node.x = x; - node.y = node.depth * dy; - node.dx = dx; - node.dy = dy; - if (children && (n = children.length)) { - var i = -1, - n, - c, - d; - dx = node.value ? dx / node.value : 0; - while (++i < n) { - position(c = children[i], x, d = c.value * dx, dy); - x += d; - } - } - } - - function depth(node) { - var children = node.children, - d = 0; - if (children && (n = children.length)) { - var i = -1, - n; - while (++i < n) d = Math.max(d, depth(children[i])); - } - return 1 + d; - } - - function partition(d, i) { - var nodes = hierarchy.call(this, d, i); - position(nodes[0], 0, size[0], size[1] / depth(nodes[0])); - return nodes; - } - - partition.size = function(x) { - if (!arguments.length) return size; - size = x; - return partition; - }; - - return d3_layout_hierarchyRebind(partition, hierarchy); -}; -d3.layout.pie = function() { - var value = Number, - sort = d3_layout_pieSortByValue, - startAngle = 0, - endAngle = 2 * Math.PI; - - function pie(data, i) { - - // Compute the numeric values for each data element. - var values = data.map(function(d, i) { return +value.call(pie, d, i); }); - - // Compute the start angle. - var a = +(typeof startAngle === "function" - ? startAngle.apply(this, arguments) - : startAngle); - - // Compute the angular scale factor: from value to radians. - var k = ((typeof endAngle === "function" - ? endAngle.apply(this, arguments) - : endAngle) - startAngle) - / d3.sum(values); - - // Optionally sort the data. - var index = d3.range(data.length); - if (sort != null) index.sort(sort === d3_layout_pieSortByValue - ? function(i, j) { return values[j] - values[i]; } - : function(i, j) { return sort(data[i], data[j]); }); - - // Compute the arcs! - // They are stored in the original data's order. - var arcs = []; - index.forEach(function(i) { - arcs[i] = { - data: data[i], - value: d = values[i], - startAngle: a, - endAngle: a += d * k - }; - }); - return arcs; - } - - /** - * Specifies the value function *x*, which returns a nonnegative numeric value - * for each datum. The default value function is `Number`. The value function - * is passed two arguments: the current datum and the current index. - */ - pie.value = function(x) { - if (!arguments.length) return value; - value = x; - return pie; - }; - - /** - * Specifies a sort comparison operator *x*. The comparator is passed two data - * elements from the data array, a and b; it returns a negative value if a is - * less than b, a positive value if a is greater than b, and zero if a equals - * b. - */ - pie.sort = function(x) { - if (!arguments.length) return sort; - sort = x; - return pie; - }; - - /** - * Specifies the overall start angle of the pie chart. Defaults to 0. The - * start angle can be specified either as a constant or as a function; in the - * case of a function, it is evaluated once per array (as opposed to per - * element). - */ - pie.startAngle = function(x) { - if (!arguments.length) return startAngle; - startAngle = x; - return pie; - }; - - /** - * Specifies the overall end angle of the pie chart. Defaults to 2π. The - * end angle can be specified either as a constant or as a function; in the - * case of a function, it is evaluated once per array (as opposed to per - * element). - */ - pie.endAngle = function(x) { - if (!arguments.length) return endAngle; - endAngle = x; - return pie; - }; - - return pie; -}; - -var d3_layout_pieSortByValue = {}; -// data is two-dimensional array of x,y; we populate y0 -d3.layout.stack = function() { - var values = Object, - order = d3_layout_stackOrders["default"], - offset = d3_layout_stackOffsets["zero"], - out = d3_layout_stackOut, - x = d3_layout_stackX, - y = d3_layout_stackY; - - function stack(data, index) { - - // Convert series to canonical two-dimensional representation. - var series = data.map(function(d, i) { - return values.call(stack, d, i); - }); - - // Convert each series to canonical [[x,y]] representation. - var points = series.map(function(d, i) { - return d.map(function(v, i) { - return [x.call(stack, v, i), y.call(stack, v, i)]; - }); - }); - - // Compute the order of series, and permute them. - var orders = order.call(stack, points, index); - series = d3.permute(series, orders); - points = d3.permute(points, orders); - - // Compute the baseline… - var offsets = offset.call(stack, points, index); - - // And propagate it to other series. - var n = series.length, - m = series[0].length, - i, - j, - o; - for (j = 0; j < m; ++j) { - out.call(stack, series[0][j], o = offsets[j], points[0][j][1]); - for (i = 1; i < n; ++i) { - out.call(stack, series[i][j], o += points[i - 1][j][1], points[i][j][1]); - } - } - - return data; - } - - stack.values = function(x) { - if (!arguments.length) return values; - values = x; - return stack; - }; - - stack.order = function(x) { - if (!arguments.length) return order; - order = typeof x === "function" ? x : d3_layout_stackOrders[x]; - return stack; - }; - - stack.offset = function(x) { - if (!arguments.length) return offset; - offset = typeof x === "function" ? x : d3_layout_stackOffsets[x]; - return stack; - }; - - stack.x = function(z) { - if (!arguments.length) return x; - x = z; - return stack; - }; - - stack.y = function(z) { - if (!arguments.length) return y; - y = z; - return stack; - }; - - stack.out = function(z) { - if (!arguments.length) return out; - out = z; - return stack; - }; - - return stack; -} - -function d3_layout_stackX(d) { - return d.x; -} - -function d3_layout_stackY(d) { - return d.y; -} - -function d3_layout_stackOut(d, y0, y) { - d.y0 = y0; - d.y = y; -} - -var d3_layout_stackOrders = { - - "inside-out": function(data) { - var n = data.length, - i, - j, - max = data.map(d3_layout_stackMaxIndex), - sums = data.map(d3_layout_stackReduceSum), - index = d3.range(n).sort(function(a, b) { return max[a] - max[b]; }), - top = 0, - bottom = 0, - tops = [], - bottoms = []; - for (i = 0; i < n; ++i) { - j = index[i]; - if (top < bottom) { - top += sums[j]; - tops.push(j); - } else { - bottom += sums[j]; - bottoms.push(j); - } - } - return bottoms.reverse().concat(tops); - }, - - "reverse": function(data) { - return d3.range(data.length).reverse(); - }, - - "default": function(data) { - return d3.range(data.length); - } - -}; - -var d3_layout_stackOffsets = { - - "silhouette": function(data) { - var n = data.length, - m = data[0].length, - sums = [], - max = 0, - i, - j, - o, - y0 = []; - for (j = 0; j < m; ++j) { - for (i = 0, o = 0; i < n; i++) o += data[i][j][1]; - if (o > max) max = o; - sums.push(o); - } - for (j = 0; j < m; ++j) { - y0[j] = (max - sums[j]) / 2; - } - return y0; - }, - - "wiggle": function(data) { - var n = data.length, - x = data[0], - m = x.length, - max = 0, - i, - j, - k, - s1, - s2, - s3, - dx, - o, - o0, - y0 = []; - y0[0] = o = o0 = 0; - for (j = 1; j < m; ++j) { - for (i = 0, s1 = 0; i < n; ++i) s1 += data[i][j][1]; - for (i = 0, s2 = 0, dx = x[j][0] - x[j - 1][0]; i < n; ++i) { - for (k = 0, s3 = (data[i][j][1] - data[i][j - 1][1]) / (2 * dx); k < i; ++k) { - s3 += (data[k][j][1] - data[k][j - 1][1]) / dx; - } - s2 += s3 * data[i][j][1]; - } - y0[j] = o -= s1 ? s2 / s1 * dx : 0; - if (o < o0) o0 = o; - } - for (j = 0; j < m; ++j) y0[j] -= o0; - return y0; - }, - - "expand": function(data) { - var n = data.length, - m = data[0].length, - k = 1 / n, - i, - j, - o, - y0 = []; - for (j = 0; j < m; ++j) { - for (i = 0, o = 0; i < n; i++) o += data[i][j][1]; - if (o) for (i = 0; i < n; i++) data[i][j][1] /= o; - else for (i = 0; i < n; i++) data[i][j][1] = k; - } - for (j = 0; j < m; ++j) y0[j] = 0; - return y0; - }, - - "zero": function(data) { - var j = -1, - m = data[0].length, - y0 = []; - while (++j < m) y0[j] = 0; - return y0; - } - -}; - -function d3_layout_stackMaxIndex(array) { - var i = 1, - j = 0, - v = array[0][1], - k, - n = array.length; - for (; i < n; ++i) { - if ((k = array[i][1]) > v) { - j = i; - v = k; - } - } - return j; -} - -function d3_layout_stackReduceSum(d) { - return d.reduce(d3_layout_stackSum, 0); -} - -function d3_layout_stackSum(p, d) { - return p + d[1]; -} -d3.layout.histogram = function() { - var frequency = true, - valuer = Number, - ranger = d3_layout_histogramRange, - binner = d3_layout_histogramBinSturges; - - function histogram(data, i) { - var bins = [], - values = data.map(valuer, this), - range = ranger.call(this, values, i), - thresholds = binner.call(this, range, values, i), - bin, - i = -1, - n = values.length, - m = thresholds.length - 1, - k = frequency ? 1 : 1 / n, - x; - - // Initialize the bins. - while (++i < m) { - bin = bins[i] = []; - bin.dx = thresholds[i + 1] - (bin.x = thresholds[i]); - bin.y = 0; - } - - // Fill the bins, ignoring values outside the range. - i = -1; while(++i < n) { - x = values[i]; - if ((x >= range[0]) && (x <= range[1])) { - bin = bins[d3.bisect(thresholds, x, 1, m) - 1]; - bin.y += k; - bin.push(data[i]); - } - } - - return bins; - } - - // Specifies how to extract a value from the associated data. The default - // value function is `Number`, which is equivalent to the identity function. - histogram.value = function(x) { - if (!arguments.length) return valuer; - valuer = x; - return histogram; - }; - - // Specifies the range of the histogram. Values outside the specified range - // will be ignored. The argument `x` may be specified either as a two-element - // array representing the minimum and maximum value of the range, or as a - // function that returns the range given the array of values and the current - // index `i`. The default range is the extent (minimum and maximum) of the - // values. - histogram.range = function(x) { - if (!arguments.length) return ranger; - ranger = d3.functor(x); - return histogram; - }; - - // Specifies how to bin values in the histogram. The argument `x` may be - // specified as a number, in which case the range of values will be split - // uniformly into the given number of bins. Or, `x` may be an array of - // threshold values, defining the bins; the specified array must contain the - // rightmost (upper) value, thus specifying n + 1 values for n bins. Or, `x` - // may be a function which is evaluated, being passed the range, the array of - // values, and the current index `i`, returning an array of thresholds. The - // default bin function will divide the values into uniform bins using - // Sturges' formula. - histogram.bins = function(x) { - if (!arguments.length) return binner; - binner = typeof x === "number" - ? function(range) { return d3_layout_histogramBinFixed(range, x); } - : d3.functor(x); - return histogram; - }; - - // Specifies whether the histogram's `y` value is a count (frequency) or a - // probability (density). The default value is true. - histogram.frequency = function(x) { - if (!arguments.length) return frequency; - frequency = !!x; - return histogram; - }; - - return histogram; -}; - -function d3_layout_histogramBinSturges(range, values) { - return d3_layout_histogramBinFixed(range, Math.ceil(Math.log(values.length) / Math.LN2 + 1)); -} - -function d3_layout_histogramBinFixed(range, n) { - var x = -1, - b = +range[0], - m = (range[1] - b) / n, - f = []; - while (++x <= n) f[x] = m * x + b; - return f; -} - -function d3_layout_histogramRange(values) { - return [d3.min(values), d3.max(values)]; -} -d3.layout.hierarchy = function() { - var sort = d3_layout_hierarchySort, - children = d3_layout_hierarchyChildren, - value = d3_layout_hierarchyValue; - - // Recursively compute the node depth and value. - // Also converts the data representation into a standard hierarchy structure. - function recurse(data, depth, nodes) { - var childs = children.call(hierarchy, data, depth), - node = d3_layout_hierarchyInline ? data : {data: data}; - node.depth = depth; - nodes.push(node); - if (childs && (n = childs.length)) { - var i = -1, - n, - c = node.children = [], - v = 0, - j = depth + 1; - while (++i < n) { - d = recurse(childs[i], j, nodes); - d.parent = node; - c.push(d); - v += d.value; - } - if (sort) c.sort(sort); - if (value) node.value = v; - } else if (value) { - node.value = +value.call(hierarchy, data, depth) || 0; - } - return node; - } - - // Recursively re-evaluates the node value. - function revalue(node, depth) { - var children = node.children, - v = 0; - if (children && (n = children.length)) { - var i = -1, - n, - j = depth + 1; - while (++i < n) v += revalue(children[i], j); - } else if (value) { - v = +value.call(hierarchy, d3_layout_hierarchyInline ? node : node.data, depth) || 0; - } - if (value) node.value = v; - return v; - } - - function hierarchy(d) { - var nodes = []; - recurse(d, 0, nodes); - return nodes; - } - - hierarchy.sort = function(x) { - if (!arguments.length) return sort; - sort = x; - return hierarchy; - }; - - hierarchy.children = function(x) { - if (!arguments.length) return children; - children = x; - return hierarchy; - }; - - hierarchy.value = function(x) { - if (!arguments.length) return value; - value = x; - return hierarchy; - }; - - // Re-evaluates the `value` property for the specified hierarchy. - hierarchy.revalue = function(root) { - revalue(root, 0); - return root; - }; - - return hierarchy; -}; - -// A method assignment helper for hierarchy subclasses. -function d3_layout_hierarchyRebind(object, hierarchy) { - d3.rebind(object, hierarchy, "sort", "children", "value"); - - // Add an alias for links, for convenience. - object.links = d3_layout_hierarchyLinks; - - // If the new API is used, enabling inlining. - object.nodes = function(d) { - d3_layout_hierarchyInline = true; - return (object.nodes = object)(d); - }; - - return object; -} - -function d3_layout_hierarchyChildren(d) { - return d.children; -} - -function d3_layout_hierarchyValue(d) { - return d.value; -} - -function d3_layout_hierarchySort(a, b) { - return b.value - a.value; -} - -// Returns an array source+target objects for the specified nodes. -function d3_layout_hierarchyLinks(nodes) { - return d3.merge(nodes.map(function(parent) { - return (parent.children || []).map(function(child) { - return {source: parent, target: child}; - }); - })); -} - -// For backwards-compatibility, don't enable inlining by default. -var d3_layout_hierarchyInline = false; -d3.layout.pack = function() { - var hierarchy = d3.layout.hierarchy().sort(d3_layout_packSort), - size = [1, 1]; - - function pack(d, i) { - var nodes = hierarchy.call(this, d, i), - root = nodes[0]; - - // Recursively compute the layout. - root.x = 0; - root.y = 0; - d3_layout_packTree(root); - - // Scale the layout to fit the requested size. - var w = size[0], - h = size[1], - k = 1 / Math.max(2 * root.r / w, 2 * root.r / h); - d3_layout_packTransform(root, w / 2, h / 2, k); - - return nodes; - } - - pack.size = function(x) { - if (!arguments.length) return size; - size = x; - return pack; - }; - - return d3_layout_hierarchyRebind(pack, hierarchy); -}; - -function d3_layout_packSort(a, b) { - return a.value - b.value; -} - -function d3_layout_packInsert(a, b) { - var c = a._pack_next; - a._pack_next = b; - b._pack_prev = a; - b._pack_next = c; - c._pack_prev = b; -} - -function d3_layout_packSplice(a, b) { - a._pack_next = b; - b._pack_prev = a; -} - -function d3_layout_packIntersects(a, b) { - var dx = b.x - a.x, - dy = b.y - a.y, - dr = a.r + b.r; - return dr * dr - dx * dx - dy * dy > .001; // within epsilon -} - -function d3_layout_packCircle(nodes) { - var xMin = Infinity, - xMax = -Infinity, - yMin = Infinity, - yMax = -Infinity, - n = nodes.length, - a, b, c, j, k; - - function bound(node) { - xMin = Math.min(node.x - node.r, xMin); - xMax = Math.max(node.x + node.r, xMax); - yMin = Math.min(node.y - node.r, yMin); - yMax = Math.max(node.y + node.r, yMax); - } - - // Create node links. - nodes.forEach(d3_layout_packLink); - - // Create first node. - a = nodes[0]; - a.x = -a.r; - a.y = 0; - bound(a); - - // Create second node. - if (n > 1) { - b = nodes[1]; - b.x = b.r; - b.y = 0; - bound(b); - - // Create third node and build chain. - if (n > 2) { - c = nodes[2]; - d3_layout_packPlace(a, b, c); - bound(c); - d3_layout_packInsert(a, c); - a._pack_prev = c; - d3_layout_packInsert(c, b); - b = a._pack_next; - - // Now iterate through the rest. - for (var i = 3; i < n; i++) { - d3_layout_packPlace(a, b, c = nodes[i]); - - // Search for the closest intersection. - var isect = 0, s1 = 1, s2 = 1; - for (j = b._pack_next; j !== b; j = j._pack_next, s1++) { - if (d3_layout_packIntersects(j, c)) { - isect = 1; - break; - } - } - if (isect == 1) { - for (k = a._pack_prev; k !== j._pack_prev; k = k._pack_prev, s2++) { - if (d3_layout_packIntersects(k, c)) { - break; - } - } - } - - // Update node chain. - if (isect) { - if (s1 < s2 || (s1 == s2 && b.r < a.r)) d3_layout_packSplice(a, b = j); - else d3_layout_packSplice(a = k, b); - i--; - } else { - d3_layout_packInsert(a, c); - b = c; - bound(c); - } - } - } - } - - // Re-center the circles and return the encompassing radius. - var cx = (xMin + xMax) / 2, - cy = (yMin + yMax) / 2, - cr = 0; - for (var i = 0; i < n; i++) { - var node = nodes[i]; - node.x -= cx; - node.y -= cy; - cr = Math.max(cr, node.r + Math.sqrt(node.x * node.x + node.y * node.y)); - } - - // Remove node links. - nodes.forEach(d3_layout_packUnlink); - - return cr; -} - -function d3_layout_packLink(node) { - node._pack_next = node._pack_prev = node; -} - -function d3_layout_packUnlink(node) { - delete node._pack_next; - delete node._pack_prev; -} - -function d3_layout_packTree(node) { - var children = node.children; - if (children && children.length) { - children.forEach(d3_layout_packTree); - node.r = d3_layout_packCircle(children); - } else { - node.r = Math.sqrt(node.value); - } -} - -function d3_layout_packTransform(node, x, y, k) { - var children = node.children; - node.x = (x += k * node.x); - node.y = (y += k * node.y); - node.r *= k; - if (children) { - var i = -1, n = children.length; - while (++i < n) d3_layout_packTransform(children[i], x, y, k); - } -} - -function d3_layout_packPlace(a, b, c) { - var db = a.r + c.r, - dx = b.x - a.x, - dy = b.y - a.y; - if (db && (dx || dy)) { - var da = b.r + c.r, - dc = Math.sqrt(dx * dx + dy * dy), - cos = Math.max(-1, Math.min(1, (db * db + dc * dc - da * da) / (2 * db * dc))), - theta = Math.acos(cos), - x = cos * (db /= dc), - y = Math.sin(theta) * db; - c.x = a.x + x * dx + y * dy; - c.y = a.y + x * dy - y * dx; - } else { - c.x = a.x + db; - c.y = a.y; - } -} -// Implements a hierarchical layout using the cluster (or dendogram) algorithm. -d3.layout.cluster = function() { - var hierarchy = d3.layout.hierarchy().sort(null).value(null), - separation = d3_layout_treeSeparation, - size = [1, 1]; // width, height - - function cluster(d, i) { - var nodes = hierarchy.call(this, d, i), - root = nodes[0], - previousNode, - x = 0, - kx, - ky; - - // First walk, computing the initial x & y values. - d3_layout_treeVisitAfter(root, function(node) { - var children = node.children; - if (children && children.length) { - node.x = d3_layout_clusterX(children); - node.y = d3_layout_clusterY(children); - } else { - node.x = previousNode ? x += separation(node, previousNode) : 0; - node.y = 0; - previousNode = node; - } - }); - - // Compute the left-most, right-most, and depth-most nodes for extents. - var left = d3_layout_clusterLeft(root), - right = d3_layout_clusterRight(root), - x0 = left.x - separation(left, right) / 2, - x1 = right.x + separation(right, left) / 2; - - // Second walk, normalizing x & y to the desired size. - d3_layout_treeVisitAfter(root, function(node) { - node.x = (node.x - x0) / (x1 - x0) * size[0]; - node.y = (1 - (root.y ? node.y / root.y : 1)) * size[1]; - }); - - return nodes; - } - - cluster.separation = function(x) { - if (!arguments.length) return separation; - separation = x; - return cluster; - }; - - cluster.size = function(x) { - if (!arguments.length) return size; - size = x; - return cluster; - }; - - return d3_layout_hierarchyRebind(cluster, hierarchy); -}; - -function d3_layout_clusterY(children) { - return 1 + d3.max(children, function(child) { - return child.y; - }); -} - -function d3_layout_clusterX(children) { - return children.reduce(function(x, child) { - return x + child.x; - }, 0) / children.length; -} - -function d3_layout_clusterLeft(node) { - var children = node.children; - return children && children.length ? d3_layout_clusterLeft(children[0]) : node; -} - -function d3_layout_clusterRight(node) { - var children = node.children, n; - return children && (n = children.length) ? d3_layout_clusterRight(children[n - 1]) : node; -} -// Node-link tree diagram using the Reingold-Tilford "tidy" algorithm -d3.layout.tree = function() { - var hierarchy = d3.layout.hierarchy().sort(null).value(null), - separation = d3_layout_treeSeparation, - size = [1, 1]; // width, height - - function tree(d, i) { - var nodes = hierarchy.call(this, d, i), - root = nodes[0]; - - function firstWalk(node, previousSibling) { - var children = node.children, - layout = node._tree; - if (children && (n = children.length)) { - var n, - firstChild = children[0], - previousChild, - ancestor = firstChild, - child, - i = -1; - while (++i < n) { - child = children[i]; - firstWalk(child, previousChild); - ancestor = apportion(child, previousChild, ancestor); - previousChild = child; - } - d3_layout_treeShift(node); - var midpoint = .5 * (firstChild._tree.prelim + child._tree.prelim); - if (previousSibling) { - layout.prelim = previousSibling._tree.prelim + separation(node, previousSibling); - layout.mod = layout.prelim - midpoint; - } else { - layout.prelim = midpoint; - } - } else { - if (previousSibling) { - layout.prelim = previousSibling._tree.prelim + separation(node, previousSibling); - } - } - } - - function secondWalk(node, x) { - node.x = node._tree.prelim + x; - var children = node.children; - if (children && (n = children.length)) { - var i = -1, - n; - x += node._tree.mod; - while (++i < n) { - secondWalk(children[i], x); - } - } - } - - function apportion(node, previousSibling, ancestor) { - if (previousSibling) { - var vip = node, - vop = node, - vim = previousSibling, - vom = node.parent.children[0], - sip = vip._tree.mod, - sop = vop._tree.mod, - sim = vim._tree.mod, - som = vom._tree.mod, - shift; - while (vim = d3_layout_treeRight(vim), vip = d3_layout_treeLeft(vip), vim && vip) { - vom = d3_layout_treeLeft(vom); - vop = d3_layout_treeRight(vop); - vop._tree.ancestor = node; - shift = vim._tree.prelim + sim - vip._tree.prelim - sip + separation(vim, vip); - if (shift > 0) { - d3_layout_treeMove(d3_layout_treeAncestor(vim, node, ancestor), node, shift); - sip += shift; - sop += shift; - } - sim += vim._tree.mod; - sip += vip._tree.mod; - som += vom._tree.mod; - sop += vop._tree.mod; - } - if (vim && !d3_layout_treeRight(vop)) { - vop._tree.thread = vim; - vop._tree.mod += sim - sop; - } - if (vip && !d3_layout_treeLeft(vom)) { - vom._tree.thread = vip; - vom._tree.mod += sip - som; - ancestor = node; - } - } - return ancestor; - } - - // Initialize temporary layout variables. - d3_layout_treeVisitAfter(root, function(node, previousSibling) { - node._tree = { - ancestor: node, - prelim: 0, - mod: 0, - change: 0, - shift: 0, - number: previousSibling ? previousSibling._tree.number + 1 : 0 - }; - }); - - // Compute the layout using Buchheim et al.'s algorithm. - firstWalk(root); - secondWalk(root, -root._tree.prelim); - - // Compute the left-most, right-most, and depth-most nodes for extents. - var left = d3_layout_treeSearch(root, d3_layout_treeLeftmost), - right = d3_layout_treeSearch(root, d3_layout_treeRightmost), - deep = d3_layout_treeSearch(root, d3_layout_treeDeepest), - x0 = left.x - separation(left, right) / 2, - x1 = right.x + separation(right, left) / 2, - y1 = deep.depth || 1; - - // Clear temporary layout variables; transform x and y. - d3_layout_treeVisitAfter(root, function(node) { - node.x = (node.x - x0) / (x1 - x0) * size[0]; - node.y = node.depth / y1 * size[1]; - delete node._tree; - }); - - return nodes; - } - - tree.separation = function(x) { - if (!arguments.length) return separation; - separation = x; - return tree; - }; - - tree.size = function(x) { - if (!arguments.length) return size; - size = x; - return tree; - }; - - return d3_layout_hierarchyRebind(tree, hierarchy); -}; - -function d3_layout_treeSeparation(a, b) { - return a.parent == b.parent ? 1 : 2; -} - -// function d3_layout_treeSeparationRadial(a, b) { -// return (a.parent == b.parent ? 1 : 2) / a.depth; -// } - -function d3_layout_treeLeft(node) { - var children = node.children; - return children && children.length ? children[0] : node._tree.thread; -} - -function d3_layout_treeRight(node) { - var children = node.children, - n; - return children && (n = children.length) ? children[n - 1] : node._tree.thread; -} - -function d3_layout_treeSearch(node, compare) { - var children = node.children; - if (children && (n = children.length)) { - var child, - n, - i = -1; - while (++i < n) { - if (compare(child = d3_layout_treeSearch(children[i], compare), node) > 0) { - node = child; - } - } - } - return node; -} - -function d3_layout_treeRightmost(a, b) { - return a.x - b.x; -} - -function d3_layout_treeLeftmost(a, b) { - return b.x - a.x; -} - -function d3_layout_treeDeepest(a, b) { - return a.depth - b.depth; -} - -function d3_layout_treeVisitAfter(node, callback) { - function visit(node, previousSibling) { - var children = node.children; - if (children && (n = children.length)) { - var child, - previousChild = null, - i = -1, - n; - while (++i < n) { - child = children[i]; - visit(child, previousChild); - previousChild = child; - } - } - callback(node, previousSibling); - } - visit(node, null); -} - -function d3_layout_treeShift(node) { - var shift = 0, - change = 0, - children = node.children, - i = children.length, - child; - while (--i >= 0) { - child = children[i]._tree; - child.prelim += shift; - child.mod += shift; - shift += child.shift + (change += child.change); - } -} - -function d3_layout_treeMove(ancestor, node, shift) { - ancestor = ancestor._tree; - node = node._tree; - var change = shift / (node.number - ancestor.number); - ancestor.change += change; - node.change -= change; - node.shift += shift; - node.prelim += shift; - node.mod += shift; -} - -function d3_layout_treeAncestor(vim, node, ancestor) { - return vim._tree.ancestor.parent == node.parent - ? vim._tree.ancestor - : ancestor; -} -// Squarified Treemaps by Mark Bruls, Kees Huizing, and Jarke J. van Wijk -// Modified to support a target aspect ratio by Jeff Heer -d3.layout.treemap = function() { - var hierarchy = d3.layout.hierarchy(), - round = Math.round, - size = [1, 1], // width, height - padding = null, - pad = d3_layout_treemapPadNull, - sticky = false, - stickies, - ratio = 0.5 * (1 + Math.sqrt(5)); // golden ratio - - // Compute the area for each child based on value & scale. - function scale(children, k) { - var i = -1, - n = children.length, - child, - area; - while (++i < n) { - area = (child = children[i]).value * (k < 0 ? 0 : k); - child.area = isNaN(area) || area <= 0 ? 0 : area; - } - } - - // Recursively arranges the specified node's children into squarified rows. - function squarify(node) { - var children = node.children; - if (children && children.length) { - var rect = pad(node), - row = [], - remaining = children.slice(), // copy-on-write - child, - best = Infinity, // the best row score so far - score, // the current row score - u = Math.min(rect.dx, rect.dy), // initial orientation - n; - scale(remaining, rect.dx * rect.dy / node.value); - row.area = 0; - while ((n = remaining.length) > 0) { - row.push(child = remaining[n - 1]); - row.area += child.area; - if ((score = worst(row, u)) <= best) { // continue with this orientation - remaining.pop(); - best = score; - } else { // abort, and try a different orientation - row.area -= row.pop().area; - position(row, u, rect, false); - u = Math.min(rect.dx, rect.dy); - row.length = row.area = 0; - best = Infinity; - } - } - if (row.length) { - position(row, u, rect, true); - row.length = row.area = 0; - } - children.forEach(squarify); - } - } - - // Recursively resizes the specified node's children into existing rows. - // Preserves the existing layout! - function stickify(node) { - var children = node.children; - if (children && children.length) { - var rect = pad(node), - remaining = children.slice(), // copy-on-write - child, - row = []; - scale(remaining, rect.dx * rect.dy / node.value); - row.area = 0; - while (child = remaining.pop()) { - row.push(child); - row.area += child.area; - if (child.z != null) { - position(row, child.z ? rect.dx : rect.dy, rect, !remaining.length); - row.length = row.area = 0; - } - } - children.forEach(stickify); - } - } - - // Computes the score for the specified row, as the worst aspect ratio. - function worst(row, u) { - var s = row.area, - r, - rmax = 0, - rmin = Infinity, - i = -1, - n = row.length; - while (++i < n) { - if (!(r = row[i].area)) continue; - if (r < rmin) rmin = r; - if (r > rmax) rmax = r; - } - s *= s; - u *= u; - return s - ? Math.max((u * rmax * ratio) / s, s / (u * rmin * ratio)) - : Infinity; - } - - // Positions the specified row of nodes. Modifies `rect`. - function position(row, u, rect, flush) { - var i = -1, - n = row.length, - x = rect.x, - y = rect.y, - v = u ? round(row.area / u) : 0, - o; - if (u == rect.dx) { // horizontal subdivision - if (flush || v > rect.dy) v = v ? rect.dy : 0; // over+underflow - while (++i < n) { - o = row[i]; - o.x = x; - o.y = y; - o.dy = v; - x += o.dx = v ? round(o.area / v) : 0; - } - o.z = true; - o.dx += rect.x + rect.dx - x; // rounding error - rect.y += v; - rect.dy -= v; - } else { // vertical subdivision - if (flush || v > rect.dx) v = v ? rect.dx : 0; // over+underflow - while (++i < n) { - o = row[i]; - o.x = x; - o.y = y; - o.dx = v; - y += o.dy = v ? round(o.area / v) : 0; - } - o.z = false; - o.dy += rect.y + rect.dy - y; // rounding error - rect.x += v; - rect.dx -= v; - } - } - - function treemap(d) { - var nodes = stickies || hierarchy(d), - root = nodes[0]; - root.x = 0; - root.y = 0; - root.dx = size[0]; - root.dy = size[1]; - if (stickies) hierarchy.revalue(root); - scale([root], root.dx * root.dy / root.value); - (stickies ? stickify : squarify)(root); - if (sticky) stickies = nodes; - return nodes; - } - - treemap.size = function(x) { - if (!arguments.length) return size; - size = x; - return treemap; - }; - - treemap.padding = function(x) { - if (!arguments.length) return padding; - - function padFunction(node) { - var p = x.call(treemap, node, node.depth); - return p == null - ? d3_layout_treemapPadNull(node) - : d3_layout_treemapPad(node, typeof p === "number" ? [p, p, p, p] : p); - } - - function padConstant(node) { - return d3_layout_treemapPad(node, x); - } - - var type; - pad = (padding = x) == null ? d3_layout_treemapPadNull - : (type = typeof x) === "function" ? padFunction - : type === "number" ? (x = [x, x, x, x], padConstant) - : padConstant; - return treemap; - }; - - treemap.round = function(x) { - if (!arguments.length) return round != Number; - round = x ? Math.round : Number; - return treemap; - }; - - treemap.sticky = function(x) { - if (!arguments.length) return sticky; - sticky = x; - stickies = null; - return treemap; - }; - - treemap.ratio = function(x) { - if (!arguments.length) return ratio; - ratio = x; - return treemap; - }; - - return d3_layout_hierarchyRebind(treemap, hierarchy); -}; - -function d3_layout_treemapPadNull(node) { - return {x: node.x, y: node.y, dx: node.dx, dy: node.dy}; -} - -function d3_layout_treemapPad(node, padding) { - var x = node.x + padding[3], - y = node.y + padding[0], - dx = node.dx - padding[1] - padding[3], - dy = node.dy - padding[0] - padding[2]; - if (dx < 0) { x += dx / 2; dx = 0; } - if (dy < 0) { y += dy / 2; dy = 0; } - return {x: x, y: y, dx: dx, dy: dy}; -} -})(); |