11

我正在为我的一个项目使用networkx(一个python图形绘图包)http://networkx.lanl.gov/index.html。虽然 networkx 很酷,但由于交叉边缘的数量,显示功能有点糟糕。有没有办法最小化图中的交叉边?我的意思是一种算法,它可以以最小化交叉边缘的方式对节点进行排序?

4

1 回答 1

3

确定最小化交叉数量的平面图布局是 NP-Hard。请参阅有关Crossing Number的 wiki 页面。

您可以尝试一些启发式方法,我相信基于力的布局非常流行(如果我没记错的话,graphviz 会使用它们)。

您也可以尝试一些近似算法,您应该在我链接的 wiki 页面上找到参考资料。

希望有帮助。

于 2011-02-20T16:16:58.253 回答