3

有向非巡回グラフの幅を見つけようとしています...隣接リストさえなくても、任意に順序付けられたノードのリストで表されます。

グラフ/リストは、実行順序の基準としてファイルを使用する並列 GNU Make のようなワークフロー マネージャー用です。各ノードには、ソース ファイルとターゲット ファイルのリストがあります。ファイル名を指定すると、それを生成するノードを決定できるように、ハッシュ テーブルが用意されています。このように、このテーブルを使用して各ソース ファイルを生成するノードを調べることで、ノードの親を特定できます。

これは、コードを大幅に変更することなく、現時点で私が持っている唯一の能力です。コードはしばらく公に使用されてきましたが、構造を大幅に変更して不適切なリリースを行うことは避けたいと考えています。いいえ、厳密にテストする時間はありません (私はアカデミックな環境にいます)。理想的には、ノードにフィールドを追加するよりも危険なことをせずにこれを実行できることを願っています。

私の現在のアプローチとその欠陥の概要を説明するコミュニティ wiki の回答を投稿します。誰かがそれを編集したり、出発点として使用したりしたい場合は、お気軽に. 物事を明確にするためにできることがあれば、質問に答えたり、必要に応じてコードを投稿したりできます。

ありがとう！

編集：気になる人のために、これはCになります。はい、私の疑似コードがひどく失敗したPythonのそっくりさんにあることは知っています。言語はあまり関係ないと思います。

4

3 に答える 3

3

ここで検討している「幅」は、実際には必要なものではないと思います。幅は、選択肢がある各ノードにレベルを割り当てる方法によって異なります。すべてのソースをレベル 0 に割り当てるか、すべてのシンクを最大レベルに割り当てるかを決定しているときに、これに気付きました。

代わりに、ノードの数を数えて、dag の最長パスである「クリティカル パスの長さ」で割ります。これにより、グラフの平均並列処理が得られます。グラフ自体にのみ依存し、グラフの幅を示します。

クリティカル パスの長さを計算するには、現在行っていることを実行します。クリティカル パスの長さは、最終的に割り当てられる最大レベルです。

于 2010-05-08T15:20:14.300 に答える
1

これが私（プラチナ・アズール、原作者）がこれまでに持っているものです。

準備/増強:

  • 「子」フィールドをリンク リスト (「DAG」) ノードに追加する
  • 「レベル」フィールドを「DAG」ノードに追加
  • 「children_left」フィールドを「DAG」ノードに追加します。これは、(アルゴリズムの後の段階で) 親が検査される前に、すべての子が検査されることを確認するために使用されます。

アルゴリズム：

  1. すべてのノードの直接の子の数を見つけます。また、children==0 のノードをリストに追加して葉を決定します。

    for l in L:
  l.children = 0


for l in L:
  l.level = 0
  for p in l.parents:
    ++p.children

Leaves = []
for l in L:
  l.children_left = l.children
  if l.children == 0:
    Leaves.append(l)

  2. すべてのノードに「逆深度」レベルを割り当てます。通常、深さによって、位相的にソートし、親のないノードに深さ = 0 を割り当てることを意味します。ただし、葉に対応する深さ = 0 で、これを逆にする必要があると考えています。また、(適切な「深さレベル」を決定するために) 最初にすべての子ノードを「見て」いない限り、ノードがキューに追加されないようにする必要があります。

    max_level = 0
while !Leaves.empty():
  l = Leaves.pop()
  for p in l.parents:
    --p.children_left
    if p.children_left == 0:
      /* we only want to append parents with for sure correct level */
      Leaves.append(p)
    p.level = Max(p.level, l.level + 1)
    if p.level > max_level:
      max_level = p.level

  3. すべてのノードにレベルがあるので、配列を作成し、リストをもう一度調べて、各レベルのノード数を数えます。

    level_count = new int[max_level+1]
for l in L:
  ++level_count[l.level]

width = Max(level_count)

ということで、ここまで考えています。それを改善する方法はありますか？全体的に線形時間ですが、5 ～ 6 回の線形スキャンが行われるため、キャッシュ ミスなどが発生する可能性があります。ノード拡張を超えて基礎となるコードを実際に変更せずに、より良いデータ構造で局所性を活用する方法がないかどうか疑問に思う必要があります。

何かご意見は？

于 2010-05-07T18:29:13.287 に答える
1

私の意見では、この種の土壇場での開発を行っているときは、新しい構造を既に使用している構造から分離しておくのが最善です。この時点で、時間に追われている場合は、より簡単なソリューションを選択します。

  1. 親データを使用してグラフの隣接行列を作成します (簡単なはずです)
  2. この行列を使用してトポロジカル ソートを実行します。（または、時間を押した場合は tsort を使用することもできます）
  3. トポロジカルな並べ替えができたので、ノードごとに 1 つの要素で配列レベルを作成します。
  4. ノードごとに:
    • ノードに親がない場合は、そのレベルを 0 に設定します
    • それ以外の場合は、親のレベル + 1 の最小値に設定します。
  5. 最大レベル幅を見つけます。

質問は、キース・ランドールが尋ねたように、これはあなたが必要とする正しい測定ですか?

于 2010-05-08T15:50:19.267 に答える