5

システムでは、通常のグラフのように接続されているノードのリストがあります。私たちはシステム全体とそれらのすべての接続を知っており、開始点も持っています。すべてのエッジには方向があります。

ここで、これらすべてのノードとエッジを自動的に描画したいと考えています。問題は実際の描画ではなく、(x,y) 座標の計算です。基本的には、見栄えがするようにこのグラフ全体を描きたいと思います。

私のデータ構造は次のようになります。

class node:
string text
List<edge> connections

この問題にはよく知られたアルゴリズムがいくつかあるはずですか? 何も見つかりませんでしたが、間違ったキーワードを使用している可能性があります。

私の考え：

1 つの方法は、開始ノードを (0,0) に配置し、「距離」という定数を設定することです。次に、隣接するノードごとに距離を y 位置に追加し、隣接するノードごとに x= 距離 * n を設定します。

しかし、これは実際には多くの問題を引き起こします。

4

2 に答える 2

10

これに対する最も一般的なアプローチは、決定論的なレイアウトではなく、強制的に指示されたレイアウトを使用することです。要点は、すべてのノードが互いに反発し (反重力)、接続されたノードのペアが互いに引き付け合うようにすることです。物理シミュレーションを数回繰り返した後、妥当なレイアウトを得ることができます。

使用できるレイアウト アルゴリズムは多数あり、結果は大きく異なります。GraphViz fdp ( Fruchterman & Reingold '91 ) および neato ( Kamada & Kawai '89 ) アルゴリズムは機能しますが、かなり古く、より優れた代替手段があります。Fruchterman & Reingold '91アルゴリズムは、 NetworkXのPython でも利用できます。

Prefuseは、非常に高速で優れたForceDirectedLayout Java クラスを提供します。Hachul & Jünger '05は FM^3 アルゴリズムの詳細を説明しています。これは実際には非常にうまく機能しているように見え ( Hachul & Jünger '06 )、C++ でTulipで利用できます。

ネットワーク分析を Excel 2007/2010 に統合する優れた入門ツールであるNodeXL (C#) など、グラフを視覚化するためのオープン ソース ツールは他にもたくさんあります (免責事項: 私はそのアドバイザーです)。その他の優れたツールには、Gephi (Java) やCytoscape (Java) などがありますが、Pajek、UCINet、yEd、およびTom Sawyerは独自の代替ツールです。

于 2012-10-25T16:37:36.840 に答える
2

一般に、これはトリッキーな問題です。特に、エッジ ルーティングを処理して見栄えを良くしたい場合はなおさらです。http://www.graphviz.org/を見て、コマンド ライン ツールを使用するか、graphviz ライブラリを使用してレイアウトを行い、アプリケーション内で x、y 座標を取得します。

于 2012-10-24T18:18:51.670 に答える