检查有向无环图是否可行

Question

对于给定的有向无环图 G 我正在寻找一种方法来验证列表 L 是否包含活动，优先可行。节省资源的解决方案会很好，因为 G 的大小可能会急剧增加。

示例：

G = {0: [], 1: [0], 2: [0], 3: [0], 4: [1], 5: [1], 6: [4], 7: [4], 8: [3,6,7], 9: [2,5,6], 10: [2,5], 11: [8,9,10]}

现在这个列表

L1 = [0, 1, 2, 3, 4, 5, 10, 6, 7, 9, 8, 11]

例如是可行的但是

L2 = [1, 0, 2, 3, 4, 10, 5, 6, 7, 9, 8, 11]

不是因为 activity 0 是 1 的前导而 activity 5 是 10 的前导。

Answer 1

据我了解，您想检查给定的节点排序是否与图中边定义的部分排序一致。也许我遗漏了一些东西，但是为此，检查列表中 a 的索引低于 b 的所有边 a ---> b 就足够了。如果您首先创建一个字典将元素映射到它们的位置，则复杂度仅为 O(e)，e 是边的数量。

def check(g, l):
    pos = {x: i for i, x in enumerate(l)} # for O(1) index
    return all(pos[a] < pos[b] for b in g for a in g[b])

G = {0: [], 1: [0], 2: [0], 3: [0], 4: [1], 5: [1], 6: [4],
     7: [4], 8: [3,6,7], 9: [2,5,6], 10: [2,5], 11: [8,9,10]}
L1 = [0, 1, 2, 3, 4, 5, 10, 6, 7, 9, 8, 11]
L2 = [1, 0, 2, 3, 4, 10, 5, 6, 7, 9, 8, 11]
print(check(G, L1)) # True
print(check(G, L2)) # False

检查有向无环图是否可行

Check if directed acyclic graph is feasible

python

directed-acyclic-graphs