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

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.