接続されたノードのリストからグラフを描く

Question

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

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

class node: 
string text 
List<edge> connections 

が存在しなければならないいくつかのよく知られたアルゴリズム：

私のデータ構造のようなものでしょうか？私は何かを見つけることができませんでしたが、間違ったキーワードを使用している可能性があります。

私の考え：

一つの方法は、（0,0）で私たちのstartnodeを配置して、「距離」であるいくつかの定数を持っていることであろう。そして、各隣人に対して、それはy位置に距離を加え、隣人である各ノードに対して、x =距離* nを設定する。

しかし、これは本当に多くの問題を引き起こすでしょう - それは確かに行く方法ではありません。

Answer 1

これまでの最も一般的なアプローチは、決定的なものではなくforce-directed layoutを使用することです。要点は、すべてのノードが互いに反発する（反重力）と、接続されたノードのペアがお互いに引き合うことです。物理シミュレーションのいくつかの反復後、合理的なレイアウトを得ることができます。

多くのレイアウトアルゴリズムがあり、大幅に異なる結果が得られます。 GraphViz fdp（Fruchterman & Reingold '91）とneato（Kamada & Kawai '89）のアルゴリズムは動作しますが、どちらかといえば古いものです。 Fruchterman & Reingold '91アルゴリズムは、PythonのNetworkXでも利用できます。

Prefuseは、かなり高速で良好なForceDirectedLayout Java classを提供します。 Hachul & Jünger '05は、FM^3アルゴリズムを詳しく説明していますが、これは実際にはかなりうまくいくようです（​​）。これはC++でTulipにあります。

、 NodeXL（C＃）と同様に、エクセル2007/2010（免責事項：私はそれのアドバイザーです）にネットワーク分析を統合する優れた入門ツールをグラフを可視化する他のオープンソースツールのトンがあります。その他の素晴らしいツールにはGephi（Java）とCytoscape（Java）があり、Pajek,UCINet,およびTom Sawyerは独自の代替品です。

Answer 2

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