最小化径向图中的交叉(networkx，graphviz) [英] Minimize crossings in a radial graph (networkx, graphviz)

问题描述

我有一个使用python networkx库构建的复杂图形，我试图以一种易于理解的方式绘制它.我的数据的结构方式是:我始终有一个中心节点，然后是一组离中心距离为1的节点，然后是另一组离中心距离为2的节点.距离"是指到达中心节点之前的最小边数.由于这种结构，我想以径向方式绘制图形，其中距离1的节点位于距中心固定半径的圆周上，假设 r = 1 ，距离为 r = 2 的距离为2的节点.像这样的东西:我尝试了不同的方法，但迄今为止最有前途的方法是使用所有节点都与中心节点相距适当的距离，但是问题是，没有选择节点在圆周上的位置以最小化边缘交叉.链接页面中明确指出:该算法目前仅在二维上有效，并且未尝试最小化边缘交叉".我在是的，它仍然有点混乱，但是我应该可以通过调整边缘的长度来改善它，无论如何，我想这是我可以对我的混乱数据进行的最佳处理！

I have a complicated graph that I build using the python networkx library and I am trying to draw it in an understandable way. My data is structured in a way that I always have a central node, then a set of nodes that are at distance 1 from the center, and then another set of nodes which are at distance 2 from the center. By "distance" I mean the minimum number of edges before reaching the central node. Because of this structure, I would like to draw the graph in a radial fashion, where the distance-1 nodes lay on a circumference of a fixed radius from the center, let's say r=1, and the distance-2 nodes on a circumference of r=2. Something like this: I tried different approaches, but the most promising one so far has been to use the networkx.drawing.layout.shell_layout, that produces the following layout: All the nodes are at the right distance from the central one, but the problem is that the position of the nodes on the circumferences is not chosen to minimize the edge crossings. This is clearly stated in the linked page "This algorithm currently only works in two dimensions and does not try to minimize edge crossings". I have looked both in the networkx library documentation and in the pygraphviz one, but I have not found layouts that allow for minimisation of crossings and positioning the nodes on concentric circumferences at the same time. Does anybody know how to do that?

Edit: Here are the edges of the graph shown in figure 2 (it's a directed graph!).

edges = [((3, 446), (3, 439)), ((3, 446), (3, 502)), ((3, 446), (3, 2366)), ((3, 446), (3, 382)), ((3, 446), (3, 3556)), ((3, 446), (4, 1778)), ((3, 446), (3, 1214)), ((3, 446), (3, 445)), ((3, 446), (4, 758)), ((3, 439), (2, 253)), ((3, 439), (3, 446)), ((3, 439), (3, 3482)), ((3, 439), (4, 1763)), ((3, 439), (3, 2359)), ((3, 439), (3, 319)), ((2, 253), (3, 439)), ((2, 127), (3, 502)), ((3, 502), (2, 127)), ((3, 502), (3, 446)), ((3, 502), (3, 4004)), ((3, 502), (3, 508)), ((3, 502), (4, 998)), ((3, 502), (3, 3986)), ((3, 502), (4, 2018)), ((3, 502), (3, 1270)), ((3, 4004), (3, 502)), ((3, 4004), (3, 3556)), ((4, 1270), (4, 758)), ((4, 758), (3, 446)), ((4, 758), (4, 998)), ((4, 758), (4, 502)), ((4, 758), (4, 638)), ((4, 758), (4, 743)), ((4, 758), (4, 1270)), ((3, 508), (3, 502)), ((4, 2300), (3, 382)), ((3, 382), (4, 2300)), ((3, 382), (3, 254)), ((3, 382), (3, 446)), ((3, 1270), (3, 1214)), ((3, 1270), (3, 502)), ((3, 1214), (3, 1270)), ((3, 1214), (3, 446)), ((3, 1214), (3, 1207)), ((3, 1214), (3, 254)), ((3, 3482), (3, 439)), ((3, 3482), (3, 3538)), ((2, 254), (3, 3556)), ((3, 3556), (3, 4004)), ((3, 3556), (2, 254)), ((3, 3556), (4, 1660)), ((3, 3556), (3, 446)), ((4, 1763), (3, 439)), ((4, 1763), (4, 1778)), ((2, 191), (3, 2366)), ((3, 2366), (4, 3190)), ((3, 2366), (3, 2359)), ((3, 2366), (3, 446)), ((3, 2366), (2, 191)), ((4, 3190), (3, 2366)), ((4, 998), (4, 758)), ((4, 998), (3, 502)), ((3, 3986), (3, 502)), ((3, 3986), (3, 3538)), ((3, 2359), (3, 2366)), ((3, 2359), (3, 439)), ((4, 1660), (3, 3556)), ((4, 3698), (4, 1778)), ((4, 1778), (4, 2018)), ((4, 1778), (4, 1780)), ((4, 1778), (4, 1763)), ((4, 1778), (3, 446)), ((4, 1778), (4, 3698)), ((4, 2018), (4, 1778)), ((3, 254), (3, 382)), ((3, 254), (3, 1214)), ((4, 1780), (4, 1778)), ((4, 502), (3, 382)), ((4, 502), (4, 758)), ((4, 638), (4, 758)), ((3, 319), (3, 439)), ((4, 743), (4, 758)), ((4, 743), (3, 439)), ((3, 1207), (3, 439)), ((4, 3320), (3, 445)), ((3, 445), (3, 446)), ((3, 445), (4, 3320)), ((3, 445), (3, 443)), ((3, 443), (3, 3538)), ((3, 3538), (3, 3986)), ((3, 3538), (3, 3482)), ((3, 3538), (3, 446)), ((3, 3538), (3, 443)), ((4, 1777), (4, 1778))]

解决方案

I did it! By using the twopi layout of pygraphviz (as initially suggested by @sroush in a comment to this similar question) and specifying the node I want to be in the center as the 'root' node (this is the part I was missing!). The output is the following: Yes, it's still a bit messy, but I should be able to improve it by tweaking the length of the edges, and anyhow, I guess that's the best I can do with my messy data!

这篇关于最小化径向图中的交叉(networkx，graphviz)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！