(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.on = function(type, listener) {

    event.on(type, 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;