java函数可以找到最小边交叉点的图

2018-06-09 19:20:18

我正在寻找一种Java函数，它可以最小化图形中边缘交叉点的数量。

输入应该是图G（E []，V []），其中V []是所有节点的数组，E []是所有边的数组。输出应该是边缘元素的二维数组（E [] []），其中包含所有相互交叉的边。

例如，请参阅https://www.ads.tuwien.ac.at/research/graphDrawing.html“交叉最小化”部分。图3a和3b显示了同一个图的不同表示。但是图3b只有极少量的边缘交叉。因此在这种特殊情况下，函数outputarray应该具有元素[0] [0] =“节点绿色黄色”和[0] [1] =“节点粉红色橙色”的长度[1] [2]

我已经看过JUNG，但是我找不到最小化的内置函数。大多数做最小化的库是商业的并且完全超载。我不在寻找图形输出。我只需要尽可能少的边缘交叉和边缘。

我相信一般来说，这是一个NP难题，你只能得到最小交叉数的上界：交叉数。但是，OGDF C ++库有一些布局，试图将输入图中的交叉数最小化。

链接地址: http://www.djcxy.com/p/29217.html

上一篇: java function that finds graph with minimal edge crossings

下一篇: What's the fastest, pure Javascript, Graph visualization toolkit?