D3 Sankey minimizes intersection

Question

On d3's Sankey Diagram page, Mike Bostock says: “The algorithm may be improved in the future, say, to minimize link crosses.”

I would like to spend some time and do just that, but I'm not sure what will begin. Does anyone have any suggestions or ideas on how to achieve this?

My intuition is that iterative relaxation applied to nodes to minimize distances between lines can also be used to move the same nodes to minimize channel crossings.

I really need to “distribute” nodes vertically even in situations where there is only one node per x-position, so that link intersections are greatly reduced (this does not have to be an academic -level result, practical, better than it is -right-now-the result will be enough)

Here's a JS Fiddle as a starting point - with nodes located on a sub-optimal path that makes edges / links intersect from the start:

function getData() { return { "nodes": [{ "node": 0, "name": "Name0" }, { "node": 1, "name": "Name1" }, { "node": 2, "name": "Action2" }, { "node": 3, "name": "Name3" }, { "node": 4, "name": "Name4" }, { "node": 5, "name": "Action5" }, { "node": 6, "name": "Action6" }, { "node": 7, "name": "Action7" }, { "node": 8, "name": "Action8" }], "links": [{ "source": 0, "target": 6, "value": 25, "id": "name0" }, { "source": 1, "target": 2, "value": 25, "id": "Name1" }, { "source": 2, "target": 5, "value": 25, "id": "Name1" }, { "source": 3, "target": 6, "value": 25, "id": "Name3" }, { "source": 6, "target": 7, "value": 25, "id": "name0" }, { "source": 4, "target": 7, "value": 25, "id": "Name4" }, { "source": 5, "target": 7, "value": 25, "id": "Name1" }, { "source": 6, "target": 7, "value": 25, "id": "Name3", }, { "source": 7, "target": 8, "value": 25, "id": "Name3" }] }; } 

Answer 1

All this in an updated example .

 // load the data var graph_zero = getData(); 

Add intermediate nodes in each lane for the interval.

 var graph = rebuild(graph_zero.nodes, graph_zero.links) 

Create a spacing of the normal path

 sankey .nodes(graph.nodes) .links(graph.links) .layout(32); 

Delete added intermediate nodes

 strip_intermediate(graph.nodes, graph.links) 

And plot as usual. This works for a simple case.

 // From sankey, but keep indices as indices // Populate the sourceLinks and targetLinks for each node. // Also, if the source and target are not objects, assume they are indices. function computeNodeLinks(nodes, links) { nodes.forEach(function(node) { node.sourceLinks = []; node.targetLinks = []; }); links.forEach(function(link) { var source = link.source, target = link.target; nodes[source].sourceLinks.push(link); nodes[target].targetLinks.push(link); }); } // computeNodeBreadths from sankey re-written to use indexes // Iteratively assign the breadth (x-position) for each node. // Nodes are assigned the maximum breadth of incoming neighbors plus one; // nodes with no incoming links are assigned breadth zero, while // nodes with no outgoing links are assigned the maximum breadth. function computeNodeBreadths(nodes,links) { var remainingNodes = nodes.map(function(d) { return d.node }) var nextNodes var x = 0 while (remainingNodes.length) { nextNodes = []; remainingNodes.forEach(function(node) { nodes[node].x = x; nodes[node].sourceLinks.forEach(function(link) { if (nextNodes.indexOf(link.target) < 0) { nextNodes.push(link.target); } }); }); remainingNodes = nextNodes; ++x; } } // Add nodes and links as needed function rebuild(nodes, links) { var temp_nodes = nodes.slice() var temp_links = links.slice() computeNodeLinks(temp_nodes, temp_links) computeNodeBreadths(temp_nodes, temp_links) for (var i = 0; i < temp_links.length; i++) { var source = temp_links[i].source var target = temp_links[i].target var source_x = nodes[source].x var target_x = nodes[target].x var dx = target_x - source_x // Put in intermediate steps for (var j = dx; 1 < j; j--) { var intermediate = nodes.length nodes.push({ node: intermediate, name: "intermediate" }) links.push({ source: intermediate, target: (j == dx ? target : intermediate-1), value: links[i].value }) links[i].target = intermediate } } return { nodes: nodes, links: links } } function strip_intermediate(nodes, links) { for (var i = links.length-1; i >= 0; i--) { var link = links[i] if (link.original_target) { var intermediate = nodes[link.last_leg_source] link.target = nodes[link.original_target] link.ty = intermediate.sourceLinks[0].ty } } for (var i = links.length-1; i >= 0; i--) { var link = links[i] if (link.source.name == "intermediate") { links.splice(i, 1) } } for (var i = nodes.length-1; i >= 0; i--) { if (nodes[i].name == "intermediate") { nodes.splice(i, 1) } } } 

Refresh . To reduce transitions further, Using PQR trees to reduce edge intersections in multicast acyclic graphs can be useful.