d3.js - D3 Sankey 最小化链路交叉

Question

在他的d3 Sankey Diagram page上，Mike Bostock 说“该算法将来可以改进，比如尽量减少链接交叉”。

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

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

即使在每个 x 位置只有一个节点的情况下，我确实需要垂直“展开”节点，这样可以大大减少链接交叉(不需要是学术级别的)结果，一个实用的、比现在更好的结果就足够了)

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

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可能会有所帮助。