添加邊緣以指導其他限制的無環圖

Question

我有一個DAG。我有這個操作來在兩個節點之間添加一條邊。

如果A可以從B到達，那麼B是A的父親。如果A不需要經過另一個節點就可以從B到達，那麼B就是A的直接父節點。

對於該曲線圖的要求是：

1. 沒有循環。
2. 對於任何節點，都有一個直接父節點P [1]，P [2]，P [3] ...的列表。對於任何i和j，P [i]不是P [j]的父親。

如果添加一條邊，不滿足要求1，則不構造邊。 如果添加邊，則不滿足要求2，則會構建邊，但直接父項將以符合要求2的方式進行修改。

例如，有3個節點

• A，直接父母：無
• B，直接父母：甲
• C，直接父母：甲

現在，如果我在B和C之間加了一條邊，我們有

• C，直系父母： A，B

但A是B的父，不符合要求2，因此，一個是由C的直接父刪除，我們有

• C，直接家長：乙

目前這裏是我做過什麼： 從A添加邊B（這方面的一個成爲B的母公司）

1. 檢查B是由BFS A的母公司。如果是這樣，不要添加邊緣（這確保沒有周期）
2. 檢查B是否已經是B的父母。如果是這樣，請不要添加邊緣。
3. 查找A的父母與B的直接父母的交集。這是通過找到B的每個父母來完成的。刪除B的直接父母的交集，並添加A作爲B的直接父代。（2和3確保它符合要求2）

這很慢。它在5k節點級別發生故障（我正在尋找這個處理任何小於100k節點的圖形），速度變得不可接受，0.02秒用於添加節點邊緣。

我有一種感覺，第1步和第2步可以用一些其他算法完成。

我想過使用拓撲排序，但它必須橫跨整個圖，這是我的第一步的最壞情況1 & 2.添加新節點時排序會中斷。所以我必須每次爲插入運行拓撲排序，所以它不會產生任何好處。 對於第3步，必須找到整個A的父母。這個過程相當緩慢，因爲它平均橫跨圖的一個體面的部分。

我該如何提高效率？

Answer 1

您的問題歸結爲「可以在DAG中插入邊緣的速度比O（v + e）快嗎？」根據要求（1）。需求（2）是一個更局部的約束，不需要檢查整個圖。

我認爲答案是否定的：在最壞的情況下（v是節點/頂點的數量，e是邊數），你不可能比O(v+e)做得更好。

毫無疑問，有一些技巧可以提高預期的性能，具體取決於您的DAG的特性以及它隨時間的變化。這似乎是一個活躍的研究課題。例如，我想象一下某些圖表可能對羣集節點有利。在羣集內插入邊緣只需要在羣集子DAG內進行檢查。但是，那麼您需要一個適當的羣集策略，支持在添加節點時便宜地更新羣集等。

Answer 2

不知道你的暗示，但建議你添加索引。 每一行索引必須儲存對metaparent-metachild

metaparent - 是鏈接父母：父母，父母的父母，...

metachid - 是孩子鏈接：兒童，兒童的孩子，...

因此對於圖A-> B-> C存在以下索引： AB，BC，AC 在B-> C之間添加顯式邊將導致斷言，因爲此條目已存在。因此，算法的複雜度從n^2降低到ln（n）