3

次の意味で、ほぼツリーである有向非巡回グラフのコレクションがあります。各グラフにはルートがあり、頂点は、v 1とv 2が頂点である場合、v 1のレベルがv 2のレベルよりも小さい場合、グラフにはv 2からv 1へのエッジはありませんが、 v 1からは多くのエッジが存在する可能性があります。同じレベルまたはそれ以上のレベルの頂点に。たとえば、式ツリー、関数呼び出しグラフ、または線形クラス階層は、そのようなグラフの例です。このようなグラフの例を次に示します。

              A1            
             /  \           A1 -> A4, A3
            /    \          A3 -> A2, A6, A7
          A4  A2--A3        A2 -> A6
              | \ / \
              A6 \_ A7

グラフ描画アルゴリズムは数多くありますが、この状況に最適なアルゴリズムを判断することはできません。一部の予備調査では、ハッセ図を描画するためのアルゴリズムが適切である可能性があることが示されていますが、そのようなアルゴリズムの出力は、私がモデル化しようとしているデータ構造のタイプに対応していないようです。階層データをモデル化するためのアルゴリズムもいくつかありますが、どれが実装の容易さと効率のバランスを取るかはわかりません。前者のアプローチの問題点の 1 つは、これらのグラフにルートと方向があることです。可能であれば、アルゴリズムは巡回グラフをサポートし、数値計算の数を最小限に抑えますが、これは必須ではありません。これらの理由から、力指向のアルゴリズムは避けたいと思います。ドット。

4

2 に答える 2

1

これは実際には答えではありませんが、コメントするには長すぎました。

あなたのグラフは、一般的な有向非巡回グラフとどう違うのですか?

DAG はルートを持つ必要はありませんが、グラフの描画にはほとんど違いはないと思います。

レベルに関する限り、任意の DAG に対して、任意のエッジ v i → v jに対して level(i) ≤ level(j) となるように関数 level(v) を定義できます。自明レベル関数は、頂点のトポロジー順序における頂点のインデックスです。もう 1 つは、ルートから頂点までの最長パスの長さです。

Reingold-Tilford ツリー描画アルゴリズムは、順序付けられたツリー (つまり、頂点からのエッジが順序付けられたツリー) を描画します。あなたの例は、グラフが順序付けられていないことを示唆しており、実際に直面している主な問題は、エッジ交差を最小限に抑えるエッジ順序付けを見つけることです。おそらく、これはあなたが解決しようとしている問題です。（簡単な問題ではありません。）

dot私の経験では、実際には DAG でかなりうまく機能しますが、少し助けが必要な場合もあります。特に、各頂点のレベルがわかっている場合は、属性 `rank = "same"' を使用して各レベルのサブグラフを作成できます。(この例を参照してください。)

于 2012-11-15T06:50:32.847 に答える
1

それがまさに木である場合、このReingold-Tilford Tree 描画アルゴリズムが非常にうまく機能するのを見たことがあります。

ところで、ノード A2 をその祖先と同じレベルに「上げる」ことを許可するという決定は、実際にはあまり役に立たないと感じています。

代わりに、ノードが上昇する代わりにさらに下降することを許可します。私の意見では、以下に示すように例をより適切に描くことができます。

          A1            
         /  \           A1 -> A4, A3
        /    \          A3 -> A2, A6, A7
      A4     A3         A2 -> A6
            / | \
          A2  |  A7
            \ |
             A6

この方法では、エッジの方向にラベルを付ける必要さえありません。[元の図を誤解していませんか? A2 と A7 の間にエッジはないと思いますよね?]

于 2012-11-15T01:47:47.713 に答える