他の制限付き非循環グラフにエッジを追加する

Question

私は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が満たされるように変更されます。なし

B、直接の親：

C、直接の親：今

、もし

例えば、3つのノード

• A、直接の親が存在します私はBとCの間にエッジを追加します。
  • C、親： B
  ：、B

  が、AがBの親であるが、AがCの直接の親から削除し、我々はC、直接の親

  • を持っているので、要件2を満たしていませんBは、BFSにより、Aの親である場合（このAはBの親になる）
    1. チェック AからBにエッジを追加します。現在、ここに

  は私がやったことです。その場合は、エッジを追加しないでください（サイクルがないことを確認してください）

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

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

私は感覚のステップ1と2を他のアルゴリズムで1ステップで行うことができます。

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

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

Answer 1

あなたの質問は「DAGのエッジをO（v + e）より速く挿入できますか？要件（1）に従う。要件（2）は、グラフ全体のチェックを必要としない、よりローカルな制約です。

私は答えは何だと思いません：あなたは最悪の場合にはO(v+e)より良いを行うことはできません（vノード/頂点の数であるとeは、エッジの数です）。

DAGのプロパティと時間の経過に伴ってどのように変化するかによって、予想されるパフォーマンスを改善するトリックがあることは間違いありません。これは活発な研究課題であると思われる。たとえば、いくつかのグラフでは、ノードをクラスタ化すると有益な場合があります。クラスタ内にエッジを挿入するには、クラスタのサブDAG内でのみチェックが必要です。しかし、その後、私は、このような「到達可能性キャッシュ」を維持するための時間と空間コストは実際にパフォーマンスが大幅に悪化させるだろうと思う

Answer 2

あなたのインプリメントについてはわかりませんが、インデックスを追加することをお勧めします。 それぞれの行インデックスはmetaparent-metachild

metaparentペアを格納する必要があります - リンク内の親である：親、親の親、...

metachidは - リンクに子である：子供、子供の子、...

ようにグラフのA-> B-> Cは、以下の索引が存在する。そのようなエントリが既に存在するため AB、BC、AC はB-との間の明確なエッジを追加> Cは、アサーションを引き起こします。アルゴリズムの複雑さがn^2からln（n）に減少します