D3 Sankey minimize link crossing

Question

On his d3 Sankey Diagram page, Mike Bostock says "The algorithm could be improved in the future, say to minimize link crossing".

I would like to invest some time and do just that, but I'm not sure were to begin. Does anyone have any propositions or ideas as to how to achieve this?

My intuition is that the iterative relaxation applied on nodes to minimize link distances could also be used to reposition the same nodes to minimize link crossing.

I really need to 'spread out' the nodes vertically even in situations where there is only one node per x-position, in such a way that link crossings are strongly reduced (it doesn't need to be an academic-level result, a practical, better-than-it-is-right-now-result will suffice)

Here is a JS Fiddle as a starting point - with nodes positioned in a suboptimal way that makes edges/links cross from the very beginning:

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"
        }]
    };
}

Crushing

I believe this is a variation of edge crossing minimization for bipartite graphs. This question may provide you with some ideas: #20108145. The nodes in adjacent layers make up a bipartite graph and you can solve the edge crossing problem from layer to layer. There is some added complexity in the Sankey though since connections can "pass over" a layer (like in Mike Bostock's example). – Middling

Answer 1

All this is in a updated sample.

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

Add intermediate nodes at every band for spacing

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

Generate the spacing the normal way

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

Remove the added intermediate nodes

strip_intermediate(graph.nodes, graph.links)

And build the graph as normal. This works for the simple case provided.

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

Update: To reduce crossings further, Using PQR-trees for reducing edge crossings in layered directed acyclic graphs may be helpful.

Vowelize

This is a very simple and promising approach, thank you. I've yet to test it on more complex examples, but it's a great start. The bounty is yours! – Crushing

@Crushing You're quite welcome. I added a note about likely useful paper. – Vowelize