Nicholas Kyriakides Nicholas Kyriakides - 2 months ago 34
Javascript Question

Drawing multiple, bezier-connected edges in a force-directed graph in D3

I'm trying to draw a force-directed graph with multiple edges per node where the edges appear distinct from each other, irregardless of the distance between the target and the source node.

tl;dr

Current graph:




  • I've got a force directed graph

  • Each node can have multiple edges pointing to another node

  • To illustrate multiple edges emanating from a node, I use Arcs instead of Lines to separate each one (by giving an incremented
    linknum
    and using it to calculate the arcs radius)



The problem:



If the distance between 2 connected nodes becomes too big, the arcs merge into each other - since an arc cannot "expand" more than the radius of the imaginary circle that overlaps the 2.

Therefore the edges which should look distinct from each other, merge into 1 big arc.

Possible solutions:



I could fix the Arc radius to correspond to a valid/suitable link distance so this never happens but unfortunately the nodes are draggable/anchored by the user (I omitted the user drag/anchor code from my code sample below for brevity)

I think it would make more sense to use bezier curves instead of arcs which don't have an expansion limit. However, I'm not sure how would I go about and calculate their control points for this case

The code



Dragging the slider would redraw the chart with an increasing link/edge distance. Values above 75 create the arc/link/edge merge I'm talking about.



function draw(linkDistance) {

var links = [{
source: "Microsoft",
target: "Amazon",
type: "licensing"
}, {
source: "Microsoft",
target: "Amazon",
type: "suit"
}, {
source: "Microsoft",
target: "Amazon",
type: "resolved"
}];

//sort links by source, then target
links.sort(function(a, b) {
if (a.source > b.source) {
return 1;
}
else if (a.source < b.source) {
return -1;
}
else {
if (a.target > b.target) {
return 1;
}
if (a.target < b.target) {
return -1;
}
else {
return 0;
}
}
});

//any links with duplicate source and target get an incremented 'linknum'
for (var i = 0; i < links.length; i++) {
if (i != 0 &&
links[i].source == links[i - 1].source &&
links[i].target == links[i - 1].target) {
links[i].linknum = links[i - 1].linknum + 1;
}
else {
links[i].linknum = 1;
};
};

var nodes = {};

// Compute the distinct nodes from the links.
links.forEach(function(link) {
link.source = nodes[link.source] || (nodes[link.source] = {
name: link.source
});
link.target = nodes[link.target] || (nodes[link.target] = {
name: link.target
});
});

var w = 300,
h = 200;

var force = d3.layout.force()
.nodes(d3.values(nodes))
.links(links)
.size([w, h])
.linkDistance(linkDistance)
.charge(-300)
.on("tick", tick)
.start();

var svg = d3.select("#chart").append("svg:svg")
.attr("width", w)
.attr("height", h);

// Per-type markers, as they don't inherit styles.
svg.append("svg:defs").selectAll("marker")
.data(["suit", "licensing", "resolved"])
.enter().append("svg:marker")
.attr("id", String)
.attr("viewBox", "0 -5 10 10")
.attr("refX", 15)
.attr("refY", -1.5)
.attr("markerWidth", 6)
.attr("markerHeight", 6)
.attr("orient", "auto")
.append("svg:path")
.attr("d", "M0,-5L10,0L0,5");

var path = svg.append("svg:g").selectAll("path")
.data(force.links())
.enter().append("svg:path")
.attr("class", function(d) {
return "link " + d.type;
})
.attr("marker-end", function(d) {
return "url(#" + d.type + ")";
});

var circle = svg.append("svg:g").selectAll("circle")
.data(force.nodes())
.enter().append("svg:circle")
.attr("r", 6)
.call(force.drag);

var text = svg.append("svg:g").selectAll("g")
.data(force.nodes())
.enter().append("svg:g");

text.append("svg:text")
.attr("x", 8)
.attr("y", ".31em")
.text(function(d) {
return d.name;
});

// Use elliptical arc path segments to doubly-encode directionality.
function tick() {
path.attr("d", function(d) {
var dx = d.target.x - d.source.x,
dy = d.target.y - d.source.y,
dr = 75 / d.linknum; //linknum is defined above
return "M" + d.source.x + "," + d.source.y + "A" + dr + "," + dr + " 0 0,1 " + d.target.x + "," + d.target.y;
});

circle.attr("transform", function(d) {
return "translate(" + d.x + "," + d.y + ")";
});

text.attr("transform", function(d) {
return "translate(" + d.x + "," + d.y + ")";
});
}
}



window.onload = function() {
document.getElementById("range").addEventListener("input", function(e) {
var value = this.value;

document.getElementById("chart").innerHTML = "";
document.getElementById("label").innerHTML = value;
draw(value);
})

draw(70);
}

path.link {
fill: none;
stroke: #666;
stroke-width: 1.5px;
}

marker#licensing {
fill: green;
}

path.link.licensing {
stroke: green;
}

path.link.resolved {
stroke-dasharray: 0,2 1;
}

circle {
fill: #ccc;
stroke: #333;
stroke-width: 1.5px;
}

<script src="https://cdnjs.cloudflare.com/ajax/libs/d3/3.4.9/d3.min.js"></script>
<input type="range" id="range" step="2" value="70" min="50" max="150">
<span id="label"></span>
<div id="chart"></div>




Answer

Do you mean something like this ? -->

path.attr("d", function(d) {
      var dx = d.target.x - d.source.x,
        dy = d.target.y - d.source.y;
        var qx = dy /  1 * d.linknum, //linknum is defined above
        qy = -dx / 1 * d.linknum;
        var qx1 = (d.source.x + (dx / 2)) + qx,
        qy1 = (d.source.y + (dy / 2)) + qy;
      return "M"+d.source.x+" "+d.source.y+" C" + d.source.x + " " + d.source.y + " " + qx1 + " " + qy1 + " " + d.target.x + " " + d.target.y;
    });

That would turn them from arcs (A in the path syntax) to beziers (C in the path syntax). The control point is just stuck out at right angles from the centre of the line between the two nodes, with the 'stick-out' distance scaled to the linknum variable.

http://jsfiddle.net/a5ua66zy/2/

Ps. The '1' in the qx/qy variables can be increased to tighten the curves together

ps2. If you don't want the arcs to be as wobbly when dragged about (i.e. dependent on the distance between nodes), you can do this:

var ds = Math.sqrt ((dx * dx) + (dy * dy));
var qx = (dy / ds) * 20 * d.linknum, //linknum is defined above
    qy = -(dx / ds) * 20 * d.linknum;

// 20 is the separation between adjacent curves