1
グラフ内のエッジ交差の数を最小限に抑えるJava関数を探しています。最小限のエッジ交差を持つグラフを見つけるJava関数
入力はグラフG（E []、V []）であり、V []はすべてのノードの配列、E []はすべてのエッジの配列です。 出力は、互いに交差するエッジのすべてのペアを含むエッジ要素（E [] []）の2D配列である必要があります。
https://www.ads.tuwien.ac.at/research/graphDrawing.htmlのセクション「クロッシングの最小化」の例を参照してください。図3aおよび3bは同じグラフの異なる表現を示す。しかし、図3bは、最小限のエッジ交差を有する。したがって、この特定の場合、関数outputarrayは要素[0] [0] = "Node Green Yellow"と[0] [1] = "Node Pink Orange"の長さ[1] [2]を持つ必要があります
すでにJUNGを見ていましたが、最小化のための組み込み関数を見つけることができませんでした。最小化を行うライブラリのほとんどは商用であり、完全にオーバーロードされています。私はグラフィック出力を探していません。私は必要最小限の量のエッジクロッシングとエッジを必要とします。
もっと視覚的な例を投稿してください。 – Argote
重み付けされた接続グラフの場合、最小限のスパニングツリーはすべての頂点がまだ接続され、交差するエッジがないツリーを表示します。これは、すべての平面グラフに当てはまります。非平面グラフを表現したい場合は、これはもう少し複雑なので、エッジを埋め込むことができる領域（移動可能な場合）や、いくつの領域の不良コストに基づいて、どのエッジを使用するかの可能な領域を見つける必要がありますスパン。 –
私はすべてのノードを保持しなければならず、通常、平面グラフはありません。私は、フェルミニックテンソルネットワークを実装しており、ラインの交差点に余分なテンソルを追加しなければなりません。したがって、できるだけ少ないテンソルを追加したいと思っています...これは質問の一部ではなく、私が必要とする動機です。 – user1324005