java函數可以找到最小邊交叉點的圖形

我正在尋找一個java函數來最小化圖中邊交叉點的數量。java函數可以找到最小邊交叉點的圖形

輸入應該是圖G（E []，V []），其中V []是所有節點的數組，E []是所有邊的數組。輸出應該是邊元素（E [] []）的二維數組，它包含所有相互交叉的邊。

請參閱https://www.ads.tuwien.ac.at/research/graphDrawing.html「交叉最小化」部分爲例。圖3a和3b顯示了同一個圖的不同表示。但是圖3b只有極少量的邊緣交叉。因此在這種特殊情況下，功能輸出陣列應具有元素[0] [0] =「節點綠色黃色」和[0] [1] =「節點粉紅色橙色」的長度[1] [2]

I已經看過JUNG，但我找不到最小化的內置功能。大多數做最小化的庫是商業的並且完全超載。我不在尋找圖形輸出。我只需要儘可能少的邊緣交叉和邊緣。

來源

2012-04-10 user1324005

請發佈您想要的更多視覺示例 – Argote 2012-04-10 15:24:24

如果是加權連接圖，那麼最小生成樹會爲您提供一棵樹，所有頂點仍然連接且沒有交叉邊。所有平面圖都是如此。如果要表示非平面圖形，這會稍微複雜一些，並且需要找到可以嵌入邊緣的區域（如果它們可以移動）或基於它們有多少區域的不良成本的可行區域跨度。 – 2012-04-11 07:24:36

我必須保留所有的節點，通常沒有平面圖。我正在實施費米子張量網絡，並且必須在線路交叉處添加額外的張量。因此，我想盡可能減少張量......這不是問題的一部分，而是我爲什麼需要它的動機。 – user1324005 2012-04-11 08:09:23

我相信一般來說，這是一個NP難題，並且您只能獲得最小交叉數的上限：Crossing number。然而，一個OGDF C++庫有一些佈局，試圖最小化輸入圖中的交叉數。

來源

2013-05-25 16:34:52 lynxoid

java函數可以找到最小邊交叉點的圖形

回答

相關問題