4

私はDAGを持っています。この操作で、2 つのノード間にエッジを追加します。

A が B から到達可能な場合、B は A の親です。A が別のノードを経由せずに B から到達できる場合、B は A の直接の親です。

このグラフの要件は次のとおりです。

  1. サイクルなし。
  2. どのノードにも、直接の親のリスト P[1]、P[2]、P[3] があります... P[i] は、任意の i と j の P[j] の親ではありません。

エッジを追加する場合、要件 1 が満たされない場合、エッジは構築されません。エッジを追加する場合、要件 2 が満たされない場合、エッジが構築されますが、要件 2 が満たされるように直接の親が変更されます。

たとえば、3 つのノードがあります。

  • A、直系の父母：なし
  • B、直系の親：A
  • C、直系の親：A

ここで、B と C の間にエッジを追加すると、次のようになります。

  • C、直接の親: A、B

しかし、A は B の親であり、要件 2 を満たしていないため、A は C の直接の親から削除され、次のようになります。

  • C、直系の親：B

現在、私がやったことは次のとおりです。AからBにエッジを追加します（このAはBの親になります）

  1. B が A の親であるかどうかを BFS で確認します。その場合は、エッジを追加しないでください (これにより、サイクルがないことが確認されます)。
  2. A がすでに B の親であるかどうかを BFS で確認します。その場合は、エッジを追加しないでください。
  3. A の親と B の直接の親との交点を見つけます。これは、BFS を介して A のすべての親を見つけることによって行われます。B の直接の親から交差を削除し、A を B の直接の親として追加します (2 と 3 で要件 2 を満たしていることを確認します)。

これは遅いです。5kノードレベルで故障し（100kノード未満のグラフを処理するためにこれを探しています）、速度が許容できなくなり、ノードエッジを追加するのに0.02秒かかります。

ステップ1と2は、他のアルゴリズムを使用して1ステップで実行できると感じています。

トポロジー順序付けを使用することを考えましたが、グラフ全体を横断する必要があり、これはステップ 1 と 2 の最悪のケースです。新しいノードが追加されると、順序が乱れます。そのため、挿入のたびにトポロジー順序付けを実行する必要があるため、メリットはありません。ステップ 3 では、A の親のセット全体を見つける必要があります。平均してグラフのかなりの部分を横断するため、プロセスはかなり遅くなります。

これをより効率的にするにはどうすればよいですか？

4

2 に答える 2

4

あなたの質問は、「DAG へのエッジの挿入を O(v+e) よりも高速に実行できますか?」ということになります。要件（1）に従って。要件 (2) は、グラフ全体をチェックする必要のない、より局所的な制約です。

答えはノーだと思います:O(v+e)最悪の場合よりもうまくやることはできません (vはノード/頂点eの数で、 はエッジの数です)。

DAG のプロパティと、それが時間の経過とともにどのように変化するかに応じて、期待されるパフォーマンスを改善するためのトリックがあることは間違いありません。これは活発な研究テーマのようです。たとえば、一部のグラフでは、ノードをクラスター化することが有益であると思います。クラスター内にエッジを挿入すると、クラスター サブ DAG 内のチェックのみが必要になります。ただし、ノードを追加するときにクラスタリングを安価に更新するためのサポートを備えた適切なクラスタリング戦略が必要になります。

于 2009-08-12T13:25:54.157 に答える
0

実装についてはわかりませんが、インデックスを追加することをお勧めします。各行インデックスは、metaparent-metachildのペアを格納する必要があります

metaparent-リンク内の親です：parent、parent-of-parent、..。

metachid-リンクの子です：子、子の子、..。

したがって、グラフA-> B-> Cの場合、次のインデックスが存在します。AB、BC、AC B-> Cの間に明示的なエッジを追加すると、そのようなエントリがすでに存在するため、アサーションが発生します。したがって、アルゴリズムの複雑さはn ^ 2からln（n）に減少します

于 2009-08-12T12:06:17.157 に答える