グラフのクロスエッジを最小化する

私のプロジェクトの1つにnetworkx（pythonグラフ描画パッケージ）http://networkx.lanl.gov/index.htmlを使用しています。 networkxはかなりクールですが、表示機能の種類はクロスエッジの数に起因しています。グラフのクロスエッジを最小限に抑える方法はありますか？私は交差エッジが最小化されるような方法でノードをソートできるアルゴリズムを意味しますか？グラフのクロスエッジを最小化する

出典

2011-02-20 Anil Katti

あなたの描画にGraphvizを試しましたか？交差点を最小限に抑えること（特に、好きな種類のグラフがあればDot）を行う方が良いかもしれません。あなたはどんな種類のグラフを持っていますか（つまり、どこから来たのですか） –

私はnetworkxがgraphydを（pydotを通して）表示するのに使うと思った。これらのグラフは、特別なタイプのネットワークの痕跡からのものです。リングは最悪の打撃を受けています。（ –

[Planar Graph Layouts]の複製が可能です。（http://stackoverflow.com/questions/2347748/planar-graph-layouts） –

交差回数を最小限に抑える平面グラフレイアウトを決定するのはNP-Hardです。 wikiページのCrossing Numberを参照してください。

いくつかのヒューリスティックを試すことができますが、力に基づいたレイアウトはかなり人気があります（graphvizは正しく再考すればそれらを使用します）。

近似アルゴリズムを試すこともできます。リンク先のwikiページで参考文献を見つける必要があります。

希望に役立ちます。

出典

2011-02-20 16:16:58

グラフのクロスエッジを最小化する

答えて

関連する問題