D3 Sankey giảm thiểu liên kết băng qua

Question

Trên d3 Sankey Diagram page của mình, Mike Bostock nói "Thuật toán có thể được cải thiện trong tương lai, để giảm thiểu sự liên kết".

Tôi muốn đầu tư một thời gian và làm điều đó, nhưng tôi không chắc chắn đã bắt đầu. Có ai có bất kỳ đề xuất hoặc ý tưởng như thế nào để đạt được điều này?

Trực giác của tôi là thư giãn lặp lại được áp dụng trên các nút để giảm thiểu khoảng cách liên kết cũng có thể được sử dụng để định vị lại các nút tương tự để giảm thiểu liên kết chéo. Tôi thực sự cần phải 'trải ra' các nút theo chiều dọc ngay cả trong các tình huống mà chỉ có một nút cho mỗi vị trí x, theo cách mà các liên kết giao cắt được giảm mạnh (nó không cần phải là một học thuật- kết quả cấp, một kết quả thực tế, tốt hơn so với kết quả hiện tại sẽ đủ)

là một điểm khởi đầu ngay từ đầu:

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

Tất cả điều này là trong updated sample.

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

Thêm nút trung gian tại mỗi ban nhạc cho khoảng cách

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

Tạo khoảng cách theo cách thông thường

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

Tháo nút trung gian thêm

strip_intermediate(graph.nodes, graph.links) 

Và xây dựng gr aph như bình thường. Điều này làm việc cho trường hợp đơn giản được cung cấp.

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

Cập nhật: Để giảm cửa hơn nữa, Using PQR-trees for reducing edge crossings in layered directed acyclic graphs có thể hữu ích.