D3 Sankey尽量减少链路穿越

Question

Mike Bostock在他的d3 Sankey Diagram page上说：“算法可以在未来得到改进，比如说最小化链路穿越”。

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

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

即使在每个x位置只有一个节点的情况下，我仍然需要垂直“分散”节点，这样链路交叉就会大大减少（它不需要是学术型的，一个实际的，比现在更好的结果就足够了）

Here是一个JS小提琴作为一个起点 - 节点定位在一个次优方式，使边缘/链接交叉最开始：

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) 

和构建GR正常。这适用于提供的简单情况。

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