I am following Force directed Graph. How to prevent overlapping of link (line) in force directed graph. Expected output should be like this. Current JSON data does not contain any parent child relation ship.
我正在关注Force指示图。如何防止力导向图中链接(线)的重叠。预期的输出应该是这样的。当前JSON数据不包含任何父子关系。
Here is my Code:
这是我的代码:
var width = 960,
height = 500;
var color = d3.scale.category20();
var force = d3.layout.force()
.charge(-120)
.linkDistance(30)
.size([width, height]);
var svg = d3.select("body").append("svg")
.attr("width", width)
.attr("height", height);
var graph = {
"nodes":[
{"name":"Myriel","group":1},
{"name":"Napoleon","group":1},
{"name":"Mlle.Baptistine","group":1},
{"name":"Mme.Magloire","group":1},
{"name":"CountessdeLo","group":1},
{"name":"Geborand","group":1},
{"name":"Champtercier","group":1},
{"name":"Cravatte","group":1},
{"name":"Count","group":1},
{"name":"OldMan","group":1},
{"name":"Labarre","group":2},
{"name":"Valjean","group":2},
{"name":"Marguerite","group":3},
{"name":"Mme.deR","group":2},
{"name":"Isabeau","group":2},
{"name":"Gervais","group":2},
{"name":"Tholomyes","group":3},
{"name":"Listolier","group":3},
{"name":"Fameuil","group":3},
{"name":"Blacheville","group":3},
{"name":"Favourite","group":3},
{"name":"Dahlia","group":3},
{"name":"Zephine","group":3},
{"name":"Fantine","group":3},
{"name":"Mme.Thenardier","group":4},
{"name":"Thenardier","group":4},
{"name":"Cosette","group":5},
{"name":"Javert","group":4},
{"name":"Fauchelevent","group":0},
{"name":"Bamatabois","group":2},
{"name":"Perpetue","group":3},
{"name":"Simplice","group":2},
{"name":"Scaufflaire","group":2},
{"name":"Woman1","group":2},
{"name":"Judge","group":2},
{"name":"Champmathieu","group":2},
{"name":"Brevet","group":2},
{"name":"Chenildieu","group":2},
{"name":"Cochepaille","group":2},
{"name":"Pontmercy","group":4},
{"name":"Boulatruelle","group":6},
{"name":"Eponine","group":4},
{"name":"Anzelma","group":4},
{"name":"Woman2","group":5},
{"name":"MotherInnocent","group":0},
{"name":"Gribier","group":0},
{"name":"Jondrette","group":7},
{"name":"Mme.Burgon","group":7},
{"name":"Gavroche","group":8},
{"name":"Gillenormand","group":5},
{"name":"Magnon","group":5},
{"name":"Mlle.Gillenormand","group":5},
{"name":"Mme.Pontmercy","group":5},
{"name":"Mlle.Vaubois","group":5},
{"name":"Lt.Gillenormand","group":5},
{"name":"Marius","group":8},
{"name":"BaronessT","group":5},
{"name":"Mabeuf","group":8},
{"name":"Enjolras","group":8},
{"name":"Combeferre","group":8},
{"name":"Prouvaire","group":8},
{"name":"Feuilly","group":8},
{"name":"Courfeyrac","group":8},
{"name":"Bahorel","group":8},
{"name":"Bossuet","group":8},
{"name":"Joly","group":8},
{"name":"Grantaire","group":8},
{"name":"MotherPlutarch","group":9},
{"name":"Gueulemer","group":4},
{"name":"Babet","group":4},
{"name":"Claquesous","group":4},
{"name":"Montparnasse","group":4},
{"name":"Toussaint","group":5},
{"name":"Child1","group":10},
{"name":"Child2","group":10},
{"name":"Brujon","group":4},
{"name":"Mme.Hucheloup","group":8}
],
"links":[
{"source":1,"target":0,"value":1},
{"source":2,"target":0,"value":8},
{"source":3,"target":0,"value":10},
{"source":3,"target":2,"value":6},
{"source":4,"target":0,"value":1},
{"source":5,"target":0,"value":1},
{"source":6,"target":0,"value":1},
{"source":7,"target":0,"value":1},
{"source":8,"target":0,"value":2},
{"source":9,"target":0,"value":1},
{"source":11,"target":10,"value":1},
{"source":11,"target":3,"value":3},
{"source":11,"target":2,"value":3},
{"source":11,"target":0,"value":5},
{"source":12,"target":11,"value":1},
{"source":13,"target":11,"value":1},
{"source":14,"target":11,"value":1},
{"source":15,"target":11,"value":1},
{"source":17,"target":16,"value":4},
{"source":18,"target":16,"value":4},
{"source":18,"target":17,"value":4},
{"source":19,"target":16,"value":4},
{"source":19,"target":17,"value":4},
{"source":19,"target":18,"value":4},
{"source":20,"target":16,"value":3},
{"source":20,"target":17,"value":3},
{"source":20,"target":18,"value":3},
{"source":20,"target":19,"value":4},
{"source":21,"target":16,"value":3},
{"source":21,"target":17,"value":3},
{"source":21,"target":18,"value":3},
{"source":21,"target":19,"value":3},
{"source":21,"target":20,"value":5},
{"source":22,"target":16,"value":3},
{"source":22,"target":17,"value":3},
{"source":22,"target":18,"value":3},
{"source":22,"target":19,"value":3},
{"source":22,"target":20,"value":4},
{"source":22,"target":21,"value":4},
{"source":23,"target":16,"value":3},
{"source":23,"target":17,"value":3},
{"source":23,"target":18,"value":3},
{"source":23,"target":19,"value":3},
{"source":23,"target":20,"value":4},
{"source":23,"target":21,"value":4},
{"source":23,"target":22,"value":4},
{"source":23,"target":12,"value":2},
{"source":23,"target":11,"value":9},
{"source":24,"target":23,"value":2},
{"source":24,"target":11,"value":7},
{"source":25,"target":24,"value":13},
{"source":25,"target":23,"value":1},
{"source":25,"target":11,"value":12},
{"source":26,"target":24,"value":4},
{"source":26,"target":11,"value":31},
{"source":26,"target":16,"value":1},
{"source":26,"target":25,"value":1},
{"source":27,"target":11,"value":17},
{"source":27,"target":23,"value":5},
{"source":27,"target":25,"value":5},
{"source":27,"target":24,"value":1},
{"source":27,"target":26,"value":1},
{"source":28,"target":11,"value":8},
{"source":28,"target":27,"value":1},
{"source":29,"target":23,"value":1},
{"source":29,"target":27,"value":1},
{"source":29,"target":11,"value":2},
{"source":30,"target":23,"value":1},
{"source":31,"target":30,"value":2},
{"source":31,"target":11,"value":3},
{"source":31,"target":23,"value":2},
{"source":31,"target":27,"value":1},
{"source":32,"target":11,"value":1},
{"source":33,"target":11,"value":2},
{"source":33,"target":27,"value":1},
{"source":34,"target":11,"value":3},
{"source":34,"target":29,"value":2},
{"source":35,"target":11,"value":3},
{"source":35,"target":34,"value":3},
{"source":35,"target":29,"value":2},
{"source":36,"target":34,"value":2},
{"source":36,"target":35,"value":2},
{"source":36,"target":11,"value":2},
{"source":36,"target":29,"value":1},
{"source":37,"target":34,"value":2},
{"source":37,"target":35,"value":2},
{"source":37,"target":36,"value":2},
{"source":37,"target":11,"value":2},
{"source":37,"target":29,"value":1},
{"source":38,"target":34,"value":2},
{"source":38,"target":35,"value":2},
{"source":38,"target":36,"value":2},
{"source":38,"target":37,"value":2},
{"source":38,"target":11,"value":2},
{"source":38,"target":29,"value":1},
{"source":39,"target":25,"value":1},
{"source":40,"target":25,"value":1},
{"source":41,"target":24,"value":2},
{"source":41,"target":25,"value":3},
{"source":42,"target":41,"value":2},
{"source":42,"target":25,"value":2},
{"source":42,"target":24,"value":1},
{"source":43,"target":11,"value":3},
{"source":43,"target":26,"value":1},
{"source":43,"target":27,"value":1},
{"source":44,"target":28,"value":3},
{"source":44,"target":11,"value":1},
{"source":45,"target":28,"value":2},
{"source":47,"target":46,"value":1},
{"source":48,"target":47,"value":2},
{"source":48,"target":25,"value":1},
{"source":48,"target":27,"value":1},
{"source":48,"target":11,"value":1},
{"source":49,"target":26,"value":3},
{"source":49,"target":11,"value":2},
{"source":50,"target":49,"value":1},
{"source":50,"target":24,"value":1},
{"source":51,"target":49,"value":9},
{"source":51,"target":26,"value":2},
{"source":51,"target":11,"value":2},
{"source":52,"target":51,"value":1},
{"source":52,"target":39,"value":1},
{"source":53,"target":51,"value":1},
{"source":54,"target":51,"value":2},
{"source":54,"target":49,"value":1},
{"source":54,"target":26,"value":1},
{"source":55,"target":51,"value":6},
{"source":55,"target":49,"value":12},
{"source":55,"target":39,"value":1},
{"source":55,"target":54,"value":1},
{"source":55,"target":26,"value":21},
{"source":55,"target":11,"value":19},
{"source":55,"target":16,"value":1},
{"source":55,"target":25,"value":2},
{"source":55,"target":41,"value":5},
{"source":55,"target":48,"value":4},
{"source":56,"target":49,"value":1},
{"source":56,"target":55,"value":1},
{"source":57,"target":55,"value":1},
{"source":57,"target":41,"value":1},
{"source":57,"target":48,"value":1},
{"source":58,"target":55,"value":7},
{"source":58,"target":48,"value":7},
{"source":58,"target":27,"value":6},
{"source":58,"target":57,"value":1},
{"source":58,"target":11,"value":4},
{"source":59,"target":58,"value":15},
{"source":59,"target":55,"value":5},
{"source":59,"target":48,"value":6},
{"source":59,"target":57,"value":2},
{"source":60,"target":48,"value":1},
{"source":60,"target":58,"value":4},
{"source":60,"target":59,"value":2},
{"source":61,"target":48,"value":2},
{"source":61,"target":58,"value":6},
{"source":61,"target":60,"value":2},
{"source":61,"target":59,"value":5},
{"source":61,"target":57,"value":1},
{"source":61,"target":55,"value":1},
{"source":62,"target":55,"value":9},
{"source":62,"target":58,"value":17},
{"source":62,"target":59,"value":13},
{"source":62,"target":48,"value":7},
{"source":62,"target":57,"value":2},
{"source":62,"target":41,"value":1},
{"source":62,"target":61,"value":6},
{"source":62,"target":60,"value":3},
{"source":63,"target":59,"value":5},
{"source":63,"target":48,"value":5},
{"source":63,"target":62,"value":6},
{"source":63,"target":57,"value":2},
{"source":63,"target":58,"value":4},
{"source":63,"target":61,"value":3},
{"source":63,"target":60,"value":2},
{"source":63,"target":55,"value":1},
{"source":64,"target":55,"value":5},
{"source":64,"target":62,"value":12},
{"source":64,"target":48,"value":5},
{"source":64,"target":63,"value":4},
{"source":64,"target":58,"value":10},
{"source":64,"target":61,"value":6},
{"source":64,"target":60,"value":2},
{"source":64,"target":59,"value":9},
{"source":64,"target":57,"value":1},
{"source":64,"target":11,"value":1},
{"source":65,"target":63,"value":5},
{"source":65,"target":64,"value":7},
{"source":65,"target":48,"value":3},
{"source":65,"target":62,"value":5},
{"source":65,"target":58,"value":5},
{"source":65,"target":61,"value":5},
{"source":65,"target":60,"value":2},
{"source":65,"target":59,"value":5},
{"source":65,"target":57,"value":1},
{"source":65,"target":55,"value":2},
{"source":66,"target":64,"value":3},
{"source":66,"target":58,"value":3},
{"source":66,"target":59,"value":1},
{"source":66,"target":62,"value":2},
{"source":66,"target":65,"value":2},
{"source":66,"target":48,"value":1},
{"source":66,"target":63,"value":1},
{"source":66,"target":61,"value":1},
{"source":66,"target":60,"value":1},
{"source":67,"target":57,"value":3},
{"source":68,"target":25,"value":5},
{"source":68,"target":11,"value":1},
{"source":68,"target":24,"value":1},
{"source":68,"target":27,"value":1},
{"source":68,"target":48,"value":1},
{"source":68,"target":41,"value":1},
{"source":69,"target":25,"value":6},
{"source":69,"target":68,"value":6},
{"source":69,"target":11,"value":1},
{"source":69,"target":24,"value":1},
{"source":69,"target":27,"value":2},
{"source":69,"target":48,"value":1},
{"source":69,"target":41,"value":1},
{"source":70,"target":25,"value":4},
{"source":70,"target":69,"value":4},
{"source":70,"target":68,"value":4},
{"source":70,"target":11,"value":1},
{"source":70,"target":24,"value":1},
{"source":70,"target":27,"value":1},
{"source":70,"target":41,"value":1},
{"source":70,"target":58,"value":1},
{"source":71,"target":27,"value":1},
{"source":71,"target":69,"value":2},
{"source":71,"target":68,"value":2},
{"source":71,"target":70,"value":2},
{"source":71,"target":11,"value":1},
{"source":71,"target":48,"value":1},
{"source":71,"target":41,"value":1},
{"source":71,"target":25,"value":1},
{"source":72,"target":26,"value":2},
{"source":72,"target":27,"value":1},
{"source":72,"target":11,"value":1},
{"source":73,"target":48,"value":2},
{"source":74,"target":48,"value":2},
{"source":74,"target":73,"value":3},
{"source":75,"target":69,"value":3},
{"source":75,"target":68,"value":3},
{"source":75,"target":25,"value":3},
{"source":75,"target":48,"value":1},
{"source":75,"target":41,"value":1},
{"source":75,"target":70,"value":1},
{"source":75,"target":71,"value":1},
{"source":76,"target":64,"value":1},
{"source":76,"target":65,"value":1},
{"source":76,"target":66,"value":1},
{"source":76,"target":63,"value":1},
{"source":76,"target":62,"value":1},
{"source":76,"target":48,"value":1},
{"source":76,"target":58,"value":1}
]
}
//d3.json("miserables.json", function(error, graph) {
force
.nodes(graph.nodes)
.links(graph.links)
.start();
var link = svg.selectAll(".link")
.data(graph.links)
.enter().append("line")
.attr("class", "link")
.style("stroke-width", function(d) { return Math.sqrt(d.value); });
var node = svg.selectAll(".node")
.data(graph.nodes)
.enter().append("circle")
.attr("class", "node")
.attr("r", 5)
.style("fill", function(d) { return color(d.group); })
.call(force.drag);
node.append("title")
.text(function(d) { return d.name; });
force.on("tick", function() {
link.attr("x1", function(d) { return d.source.x; })
.attr("y1", function(d) { return d.source.y; })
.attr("x2", function(d) { return d.target.x; })
.attr("y2", function(d) { return d.target.y; });
node.attr("cx", function(d) { return d.x; })
.attr("cy", function(d) { return d.y; });
});
//});.node {
stroke: #fff;
stroke-width: 1.5px;
}
.link {
stroke: #999;
stroke-opacity: .6;
}<script src="https://cdnjs.cloudflare.com/ajax/libs/d3/3.4.0/d3.min.js"></script>2 个解决方案
#1
1
If by overlapping you mean multiple links between two nodes then they can be resolved by drawing them as arcs with increasing curvature to separate them visually.
如果通过重叠表示两个节点之间存在多个链接,则可以通过将它们绘制为具有增加曲率的弧来解析它们,从而在视觉上将它们分开。
If by overlapping you mean edges crossing then it's only possible if your graph is planar - https://en.wikipedia.org/wiki/Planarity_testing - and looking at your graph it isn't - there's at least 2 sub-graphs with almost complete connectivity. You'd need a graph layout algorithm that specifically tries to reduce edge crossings, and the bad news on that is that it's an NP-complete problem
如果通过重叠你的意思是边缘交叉,那么只有当你的图形是平面的时候才有可能 - https://en.wikipedia.org/wiki/Planarity_testing - 并且看你的图形它不是 - 至少有2个子图形几乎完全连接。你需要一个专门尝试减少边缘交叉的图形布局算法,坏消息就是它是NP完全问题
Crossing Number is NP-Complete: DOI:10.1137/0604033 https://en.wikipedia.org/wiki/Crossing_number_(graph_theory)
交叉号码是NP-Complete:DOI:10.1137 / 0604033 https://en.wikipedia.org/wiki/Crossing_number_(graph_theory)
Some techniques can be employed on complete sub-graphs by replacing their edge sets with confluent edges or motifs but this is stepping into graph drawing research: there's no easy answer
通过用汇合的边缘或图案替换它们的边缘集,可以在完整的子图上使用一些技术,但这是步入图绘制研究:没有简单的答案
Confluent Drawings: Visualizing Non-planar Diagrams in a Planar Way DOI: 10.1007/978-3-540-24595-7_1
汇合图:以平面方式可视化非平面图DOI:10.1007 / 978-3-540-24595-7_1
Motif Simplification: Improving Network Visualization Readability with Fan, Connector, and Clique Glyphs DOI: 10.1145/2470654.2466444
Motif简化:使用Fan,Connector和Clique Glyphs提高网络可视化可读性DOI:10.1145 / 2470654.2466444
In short, the only guaranteed way to not get edge crossings is not to draw edges. Maybe try looking at matrix-type visualisations for graphs? - https://bost.ocks.org/mike/miserables/
简而言之,唯一保证不进行边缘交叉的方法不是绘制边缘。也许试着看图表的矩阵式可视化? - https://bost.ocks.org/mike/miserables/
#2
0
I wanted to leave a comment, but I don't have enough reputation, so I'm "answering" instead - sorry it's not much of an answer...
我想发表评论,但我没有足够的声誉,所以我正在“回答” - 抱歉这不是一个答案......
Your example of your expected output is a tree/acyclical, which more or less magically solves the issue of overlapping links. You can see in this example from Mike Bostock (http://bl.ocks.org/mbostock/1062288) there isn't much link overlap just by way of the data being a tree.
您的预期输出示例是树/非循环,它或多或少地神奇地解决了重叠链接的问题。你可以在这个例子中看到Mike Bostock(http://bl.ocks.org/mbostock/1062288),通过数据作为树,没有太多的链接重叠。
So...
if your data is a tree, you might be lucky and the link overlapping might be a non-issue. You'll notice that the overlapping in the Bostock example happen when sibling nodes have different link distances (causing niece/nephew -- aunt/uncle link overlap). Controlling the link distances (perhaps making them a function of tree depth with longer links near the root), I think will prevent any overlap in your tree.
如果您的数据是树,您可能很幸运,链接重叠可能不是问题。您会注意到Bostock示例中的重叠发生在兄弟节点具有不同的链接距离时(导致侄女/侄子 - 姨妈/叔叔链接重叠)。控制链接距离(可能使它们成为树深度的函数,在根部附近有更长的链接),我认为可以防止树中的任何重叠。
If your data has cycles (like in the Miserables data), preventing overlap is much more complicated and won't just sort itself out. Like others are saying, I don't think it's possible with any D3 layout.
如果你的数据有周期(比如悲惨世界的数据),防止重叠就会复杂得多,而且不会自行排序。就像其他人说的那样,我认为任何D3布局都不可能。
#1
1
If by overlapping you mean multiple links between two nodes then they can be resolved by drawing them as arcs with increasing curvature to separate them visually.
如果通过重叠表示两个节点之间存在多个链接,则可以通过将它们绘制为具有增加曲率的弧来解析它们,从而在视觉上将它们分开。
If by overlapping you mean edges crossing then it's only possible if your graph is planar - https://en.wikipedia.org/wiki/Planarity_testing - and looking at your graph it isn't - there's at least 2 sub-graphs with almost complete connectivity. You'd need a graph layout algorithm that specifically tries to reduce edge crossings, and the bad news on that is that it's an NP-complete problem
如果通过重叠你的意思是边缘交叉,那么只有当你的图形是平面的时候才有可能 - https://en.wikipedia.org/wiki/Planarity_testing - 并且看你的图形它不是 - 至少有2个子图形几乎完全连接。你需要一个专门尝试减少边缘交叉的图形布局算法,坏消息就是它是NP完全问题
Crossing Number is NP-Complete: DOI:10.1137/0604033 https://en.wikipedia.org/wiki/Crossing_number_(graph_theory)
交叉号码是NP-Complete:DOI:10.1137 / 0604033 https://en.wikipedia.org/wiki/Crossing_number_(graph_theory)
Some techniques can be employed on complete sub-graphs by replacing their edge sets with confluent edges or motifs but this is stepping into graph drawing research: there's no easy answer
通过用汇合的边缘或图案替换它们的边缘集,可以在完整的子图上使用一些技术,但这是步入图绘制研究:没有简单的答案
Confluent Drawings: Visualizing Non-planar Diagrams in a Planar Way DOI: 10.1007/978-3-540-24595-7_1
汇合图:以平面方式可视化非平面图DOI:10.1007 / 978-3-540-24595-7_1
Motif Simplification: Improving Network Visualization Readability with Fan, Connector, and Clique Glyphs DOI: 10.1145/2470654.2466444
Motif简化:使用Fan,Connector和Clique Glyphs提高网络可视化可读性DOI:10.1145 / 2470654.2466444
In short, the only guaranteed way to not get edge crossings is not to draw edges. Maybe try looking at matrix-type visualisations for graphs? - https://bost.ocks.org/mike/miserables/
简而言之,唯一保证不进行边缘交叉的方法不是绘制边缘。也许试着看图表的矩阵式可视化? - https://bost.ocks.org/mike/miserables/
#2
0
I wanted to leave a comment, but I don't have enough reputation, so I'm "answering" instead - sorry it's not much of an answer...
我想发表评论,但我没有足够的声誉,所以我正在“回答” - 抱歉这不是一个答案......
Your example of your expected output is a tree/acyclical, which more or less magically solves the issue of overlapping links. You can see in this example from Mike Bostock (http://bl.ocks.org/mbostock/1062288) there isn't much link overlap just by way of the data being a tree.
您的预期输出示例是树/非循环,它或多或少地神奇地解决了重叠链接的问题。你可以在这个例子中看到Mike Bostock(http://bl.ocks.org/mbostock/1062288),通过数据作为树,没有太多的链接重叠。
So...
if your data is a tree, you might be lucky and the link overlapping might be a non-issue. You'll notice that the overlapping in the Bostock example happen when sibling nodes have different link distances (causing niece/nephew -- aunt/uncle link overlap). Controlling the link distances (perhaps making them a function of tree depth with longer links near the root), I think will prevent any overlap in your tree.
如果您的数据是树,您可能很幸运,链接重叠可能不是问题。您会注意到Bostock示例中的重叠发生在兄弟节点具有不同的链接距离时(导致侄女/侄子 - 姨妈/叔叔链接重叠)。控制链接距离(可能使它们成为树深度的函数,在根部附近有更长的链接),我认为可以防止树中的任何重叠。
If your data has cycles (like in the Miserables data), preventing overlap is much more complicated and won't just sort itself out. Like others are saying, I don't think it's possible with any D3 layout.
如果你的数据有周期(比如悲惨世界的数据),防止重叠就会复杂得多,而且不会自行排序。就像其他人说的那样,我认为任何D3布局都不可能。