D3 Sankey 最小化 link 交叉

Question

Mike Bostock 在他的 d3 Sankey Diagram page 上说 "The algorithm could be improved in the future, say to minimize link crossing"。

我想投入一些时间来做这件事，但我不确定是否要开始。有没有人对如何实现这一目标有任何建议或想法？

我的直觉是，应用于节点以最小化 link 距离的迭代松弛也可用于重新定位相同节点以最小化 link 交叉。

我真的需要 'spread out' 垂直节点，即使在每个 x 位置只有一个节点的情况下，这样 link 交叉点会大大减少（它不会需要是学术水平的成绩，一个实用的，比现在更好的成绩就足够了）

Here 是一个 JS Fiddle 作为起点 - 节点以次优方式定位，使得 edges/links 从一开始就交叉：

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

这一切都在updated sample。

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

在每个波段添加中间节点以进行间距

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

以正常方式生成间距

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

删除添加的中间节点

strip_intermediate(graph.nodes, graph.links)

并正常构建图形。这适用于提供的简单案例。

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

更新：要进一步减少交叉点，Using PQR-trees for reducing edge crossings in layered directed acyclic graphs 可能会有所帮助。

D3 Sankey 最小化 link 交叉

D3 Sankey minimize link crossing

d3.js

sankey-diagram