Arc Diagrams with Variably Spaced Nodes

README.md

Demonstration of an ArcDiagram layout function with variably spaced nodes.

The alice.json dataset is the first line from Lewis Carroll's Alice in Wonderland, parsed with the Stanford Parser.

alice.json

{
    "nodes": [
        {"value": "ROOT"},
        {"value": "Alice"},
        {"value": "was"},
        {"value": "beginning"},
        {"value": "to"},
        {"value": "get"},
        {"value": "very"},
        {"value": "tired"},
        {"value": "of"},
        {"value": "sitting"},
        {"value": "by"},
        {"value": "her"},
        {"value": "sister"},
        {"value": "on"},
        {"value": "the"},
        {"value": "bank"},
        {"value": ","},
        {"value": "and"},
        {"value": "of"},
        {"value": "having"},
        {"value": "nothing"},
        {"value": "to"},
        {"value": "do"},
        {"value": ":"},
        {"value": "once"},
        {"value": "or"},
        {"value": "twice"},
        {"value": "she"},
        {"value": "had"},
        {"value": "peeped"},
        {"value": "into"},
        {"value": "the"},
        {"value": "book"},
        {"value": "her"},
        {"value": "sister"},
        {"value": "was"},
        {"value": "reading"},
        {"value": ","},
        {"value": "but"},
        {"value": "it"},
        {"value": "had"},
        {"value": "no"},
        {"value": "pictures"},
        {"value": "or"},
        {"value": "conversations"},
        {"value": "in"},
        {"value": "it"},
        {"value": ","},
        {"value": "'"},
        {"value": "and"},
        {"value": "what"},
        {"value": "is"},
        {"value": "the"},
        {"value": "use"},
        {"value": "of"},
        {"value": "a"},
        {"value": "book"},
        {"value": ","},
        {"value": "'"},
        {"value": "thought"},
        {"value": "Alice"},
        {"value": "'"},
        {"value": "without"},
        {"value": "pictures"},
        {"value": "or"},
        {"value": "conversations"},
        {"value": "?"},
        {"value": "'"}
    ],
    "links": [
        {"source": 3, "target": 1, "value": "nsubj"},
        {"source": 3, "target": 2, "value": "aux"},
        {"source": 0, "target": 3, "value": "root"},
        {"source": 7, "target": 4, "value": "aux"},
        {"source": 7, "target": 5, "value": "dep"},
        {"source": 7, "target": 6, "value": "advmod"},
        {"source": 3, "target": 7, "value": "xcomp"},
        {"source": 7, "target": 8, "value": "prep"},
        {"source": 8, "target": 9, "value": "pcomp"},
        {"source": 9, "target": 10, "value": "prep"},
        {"source": 12, "target": 11, "value": "poss"},
        {"source": 10, "target": 12, "value": "pobj"},
        {"source": 12, "target": 13, "value": "prep"},
        {"source": 15, "target": 14, "value": "det"},
        {"source": 13, "target": 15, "value": "pobj"},
        {"source": 12, "target": 17, "value": "cc"},
        {"source": 12, "target": 18, "value": "conj"},
        {"source": 18, "target": 19, "value": "pcomp"},
        {"source": 19, "target": 20, "value": "dobj"},
        {"source": 22, "target": 21, "value": "aux"},
        {"source": 19, "target": 22, "value": "ccomp"},
        {"source": 29, "target": 24, "value": "advmod"},
        {"source": 24, "target": 25, "value": "cc"},
        {"source": 24, "target": 26, "value": "conj"},
        {"source": 29, "target": 27, "value": "nsubj"},
        {"source": 29, "target": 28, "value": "aux"},
        {"source": 22, "target": 29, "value": "dep"},
        {"source": 29, "target": 30, "value": "prep"},
        {"source": 32, "target": 31, "value": "det"},
        {"source": 30, "target": 32, "value": "pobj"},
        {"source": 34, "target": 33, "value": "poss"},
        {"source": 36, "target": 34, "value": "nsubj"},
        {"source": 36, "target": 35, "value": "aux"},
        {"source": 32, "target": 36, "value": "rcmod"},
        {"source": 29, "target": 38, "value": "cc"},
        {"source": 40, "target": 39, "value": "nsubj"},
        {"source": 29, "target": 40, "value": "conj"},
        {"source": 42, "target": 41, "value": "neg"},
        {"source": 40, "target": 42, "value": "dobj"},
        {"source": 42, "target": 43, "value": "cc"},
        {"source": 42, "target": 44, "value": "conj"},
        {"source": 42, "target": 45, "value": "prep"},
        {"source": 45, "target": 46, "value": "pobj"},
        {"source": 50, "target": 49, "value": "cc"},
        {"source": 9, "target": 50, "value": "ccomp"},
        {"source": 50, "target": 51, "value": "cop"},
        {"source": 53, "target": 52, "value": "det"},
        {"source": 50, "target": 53, "value": "nsubj"},
        {"source": 53, "target": 54, "value": "prep"},
        {"source": 56, "target": 55, "value": "det"},
        {"source": 54, "target": 56, "value": "pobj"},
        {"source": 53, "target": 59, "value": "vmod"},
        {"source": 59, "target": 60, "value": "dobj"},
        {"source": 59, "target": 62, "value": "prep"},
        {"source": 62, "target": 63, "value": "pobj"},
        {"source": 63, "target": 64, "value": "cc"},
        {"source": 63, "target": 65, "value": "conj"}
    ]
}

arcDiagram.js

(function() {
  d3.arcDiagram = function() {
    var sortNodes,
      sortLinks = arcDiagramSortLinks,
      linkLevel = arcDiagramLinkLevelCompact,
      nodeWidth = 0,
      separation = 1,
      nodeXOffset = 0,
      levelHeight = arcDiagramLevelHeight,
      nodes = [],
      links = [];

    function arc() {
      var levelIndex = d3.range(nodes.length).map(function() { return []; }),
        nw = typeof nodeWidth === "function" ? nodeWidth : function() { return nodeWidth; },
        sep = typeof separation === "function" ? separation : function() { return separation; },
        nxo = typeof nodeXOffset === "function" ? nodeXOffset : function() { return nodeXOffset; },
        lh = typeof levelHeight === "function" ? levelHeight : function() { return levelHeight; },
        curX = 0,
        nodeIndexMap, idx1, idx2;

      // node calculations
      nodes.forEach(function(n, i) { n.index = i; });
      // if sorting nodes, do it here and create a mapping from old to
      // new positions
      nodeIndexMap = {};
      if (sortNodes) nodes.sort(sortNodes);
      nodes.forEach(function(n, i) {
        nodeIndexMap[n.index] = i; n.index = i;
        // while we're iterating, we can set the x, dx, and y values
        n.x = curX + nxo(n);
        curX += nw(n) + sep(n);
        n.y = 0;
      });

      // link calculations
      // first, reassign source and index, if necessary.
      links.forEach(function(link) {
        link.source = nodeIndexMap[link.source] || link.source;
        link.target = nodeIndexMap[link.target] || link.target;
        // also set distance, which is useful for sorting.
        link.distance = Math.abs(link.source - link.target);
      });
      if (sortLinks) links.sort(sortLinks);

      // now we can find the level of each link
      links.forEach(function(link) {
        link.level = linkLevel(link, levelIndex);
        arcDiagramUpdateLevelIndex(link, levelIndex);
        // and while we're iterating, set the position values
        link.x1 = (nodes[link.source] || {}).x;
        link.x2 = (nodes[link.target] || {}).x;
        link.height = lh(link);
      });
    }

    arc.sortNodes = function(x) {
      if (!arguments.length) return sortNodes;
      sortNodes = x;
      return arc;
    }

    arc.sortLinks = function(x) {
      if (!arguments.length) return sortLinks;
      sortLinks = x;
      return arc;
    }

    arc.linkLevel = function(x) {
      if (!arguments.length) return linkLevel;
      if (x.toLowerCase() == "compact")
        linkLevel = arcDiagramLinkLevelCompact;
      else if (x.toLowerCase() == "distance")
        linkLevel = arcDiagramLinkLevelDistance;
      else
        linkLevel = x;
      return arc;
    }

    arc.nodeWidth = function(x) {
      if (!arguments.length) return nodeWidth;
      nodeWidth = typeof x === "function" ? x : +x;
      return arc;
    }

    arc.separation = function(x) {
      if (!arguments.length) return separation;
      separation = typeof x === "function" ? x : +x;
      return arc;
    }

    arc.nodeXOffset = function(x) {
      if (!arguments.length) return nodeXOffset;
      nodeXOffset = typeof x === "function" ? x : +x;
      return arc;
    }

    arc.levelHeight = function(x) {
      if (!arguments.length) return levelHeight;
      levelHeight = typeof x === "function" ? x : +x;
      return arc;
    }

    arc.nodes = function(x) {
      if (!arguments.length) return nodes;
      nodes = x;
      return arc;
    }

    arc.links = function(x) {
      if (!arguments.length) return links;
      links = x;
      return arc;
    }

    return arc;
  }

  function arcDiagramSortLinks(a, b) { return a.distance - b.distance; }

  function arcDiagramLinkLevelCompact(link, levelIndex) {
    var level = 1, idx1, idx2;

    if (link.source <= link.target) {
      idx1 = link.source; idx2 = link.target;
    } else {
      idx1 = link.target; idx2 = link.source;
    }

    for (var i = idx1; i < idx2; i++) {
      if (levelIndex[i][level]) {
        level += 1;
        i = idx1 - 1;  // restart the for-loop
        continue;
      }
    }
    return level;
  }

  function arcDiagramLinkLevelDistance(link, levelIndex) {
    return link.distance;
  }

  function arcDiagramLevelHeight(link) {
    return link.level;
  }

  function arcDiagramUpdateLevelIndex(link, levelIndex) {
    var idx1, idx2;
    if (link.source <= link.target) {
      idx1 = link.source; idx2 = link.target;
    } else {
      idx1 = link.target; idx2 = link.source;
    }
    d3.range(idx1, idx2).forEach(function(i) { levelIndex[i][link.level] = true; });
  }
})();

index.html

<!DOCTYPE html>
<style>
.axis {
    stroke: #000;
    stroke-width: 1px;
}

.node {
  fill: #000;
}

.label {
  stroke: #000;
  font: 12px sans-serif;
}

.link {
  stroke: #00F;
  stroke-width: 2px;
  fill: none;
}
</style>
<script src="http://d3js.org/d3.v3.min.js" charset="utf-8"></script>
<script src="arcDiagram.js"></script>
<body>
<div style="width: 960; height: 500; border: none; overflow: scroll;">
<svg id="dep1" height=400>
  <defs>
    <marker id="arrowhead" refX="1" refY="2" markerWidth="5" markerHeight="4" orient="auto">
      <path d="M0,0 L1,2 L0,4 L5,2 Z"/>
    </marker>
  </defs>
</svg>
</div>
<script>
var topMargin=50, // in case of overrun (perhaps i should just fix the code)
    upperHeight=300, // where the arcs go
    lowerHeight=50, // where the nodes and labels go
    separation=10, radius=5;

var arcd = d3.arcDiagram()
    .linkLevel("compact")
    .nodeWidth(function(d) { return d.width; })
    .separation(separation)
    .nodeXOffset(function(d) { return d.width/2; });

var svg = d3.select("#dep1")
    .append("svg:g")
    .attr("transform", "translate("+radius*3+","+(upperHeight+topMargin)+")");

d3.json("alice.json", function(error, data) {
    arcd.nodes(data.nodes).links(data.links);

    // do this first so the layout function can get the width
    var nodes = svg.selectAll(".node")
        .data(arcd.nodes())
      .enter().append("svg:g")
        .attr("class", "node")
    nodes.append("svg:circle")
        .attr("r", 5);
    nodes.append("svg:text")
        .attr("class", "label")
        .attr("text-anchor", "middle")
        .attr("dy", "2em")
        .text(function(d) { return d.value; })
      .each(function(d) { d.width = this.getBBox().width; });

    // now we can call the layout function
    arcd();
    // and resize the svg
    d3.select("#dep1").attr("width", d3.max(data.nodes, function(d) { return d.x + d.width + separation; }));

    var xscale = d3.scale.linear();  // we're calculating our own widths, so just do 1-to-1

    var yscale = d3.scale.linear()
        .domain([0, d3.max(arcd.links().map(function(l) { return l.height; }))+1])
        .range([0, upperHeight]);

    // with the scales, we can reposition the nodes
    nodes.attr("transform", function(d, i) {
            return "translate(" + xscale(d.x) + "," + (radius*2) + ")";
        });

    var arc = pathgen()
        .xscale(xscale)
        .yscale(yscale);

    var links = svg.selectAll(".link")
        .data(arcd.links())
      .enter().append("svg:path")
        .attr("class", "link")
        .style("marker-end", "url(#arrowhead)")
        .attr("d", arc.ortho);
});

// tiny path generator for an orthogonal path
function pathgen() {
    var gen = {},
        x = function(x) { return x; },
        y = function(y) { return y; };

    gen.ortho = function(d) {
        var x1 = x(d.x1),
            x2 = x(d.x2),
            height = y(d.height),
            dir = x1 < x2 ? 1 : -1;
        return [
            "M", x1, 0,
            "v", -(height-10),
            "q", 0, -10, dir*10, -10,
            "H", x2 - (dir*10),
            "q", (dir*10), 0, (dir*10), +10,
            "V", -2
        ].join(" ");
    };

    gen.xscale = function(a) {
      if (!arguments.length) return x;
      x = a;
      return gen;
    }

    gen.yscale = function(a) {
      if (!arguments.length) return y;
      y = a;
      return gen;
    }

    return gen;
}

</script>
</body>

thumbnail.png