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

x = 0, i = -1; while (++i < n) {

x0 = x, j = -1; while (++j < n) {

var di = groupIndex[i],

dj = subgroupIndex[i][j],

v = matrix[di][dj];

subgroups[di + "-" + dj] = {

index: di,

subindex: dj,

startAngle: x,

endAngle: x += v * k,

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.target.value, b.target.value);

});

}

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.dispatch({type: "tick", alpha: alpha});

// simulated annealing, basically

return (alpha *= .99) < .005;

}

force.on = function(type, listener) {

event[type].add(listener);

return force;

};

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

.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 force;

};

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.dx;

d3_layout_forceDragNode.py += d3.event.dy;

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

var i = -1,

n = children.length,

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

var i = -1,

n = children.length;

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 = null,

startAngle = 0,

endAngle = 2 * Math.PI;

function pie(data, i) {

// Compute the start angle.

var a = +(typeof startAngle === "function"

? startAngle.apply(this, arguments)

: startAngle);

// Compute the angular range (end - start).

var k = (typeof endAngle === "function"

? endAngle.apply(this, arguments)

: endAngle) - startAngle;

// Optionally sort the data.

var index = d3.range(data.length);

if (sort != null) index.sort(function(i, j) {

return sort(data[i], data[j]);

});

// Compute the numeric values for each data element.

var values = data.map(value);

// Convert k into a scale factor from value to angle, using the sum.

k /= values.reduce(function(p, d) { return p + d; }, 0);

// Compute the arcs!

var arcs = index.map(function(i) {

return {

data: data[i],

value: d = values[i],

startAngle: a,

endAngle: a += d * k

};

});

// Return the arcs in the original data's order.

return data.map(function(d, i) {

return arcs[index[i]];

});

}

/**

* 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;

};

// 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) {