我正在使用networkx（一个Python图形绘制包）http://networkx.lanl.gov/index.html进行我的一个项目。虽然networkx非常酷，但由于交叉边的数量，其显示功能有些糟糕。是否有一种算法可以对节点进行排序，以便最小化交叉边？
在图中最小化交叉边
11
- Anil Katti
6
你尝试过使用Graphviz进行绘图吗？它可能会更好地减少交叉（特别是Dot，如果您有它喜欢的那种图形）。您拥有什么样的图形（即，它来自哪里）？ - Jeremiah Willcock
我认为networkx使用graphviz来显示（通过pydot）。这些图形来自特定类型网络的跟踪。环是受影响最严重的 :( - Anil Katti
可能是[平面图布局]的重复问题（https://dev59.com/InE95IYBdhLWcg3wWMlQ）。 - Dr. belisarius
@belisarius：哇！我甚至都不记得那个了…… - Aryabhatta
谢谢belisarius！抱歉，我漏掉了那个。 - Anil Katti
@Moron 哈！我刚刚才意识到你回答了两个问题 :) - Dr. belisarius
1个回答
3
确定一个平面图布局，使交叉数量最小化是NP-Hard问题。请参阅Crossing Number上的维基页面。
您可以尝试一些启发式算法，力导向布局应该很受欢迎（如果我没记错的话，graphviz使用它们）。
您还可以尝试一些近似算法，您应该在我提供的维基页面中找到参考资料。
希望这能有所帮助。
您可以尝试一些启发式算法，力导向布局应该很受欢迎（如果我没记错的话，graphviz使用它们）。
您还可以尝试一些近似算法，您应该在我提供的维基页面中找到参考资料。
希望这能有所帮助。
- Aryabhatta
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接