algorithm - 测试给定的 DAG 是否是格

Question

我得到了一个具有唯一源和汇的有向无环图 (DAG)。有没有一种有效的方法来测试 partial order 是否有效？此图表示的是 lattice ？

换句话说，我需要测试任意两个顶点是否具有唯一最小上界和最大下界。

Answer 1

我不确定这是最佳方法，但在我看来值得一试。

目的是至少检查尽可能多的顶点对是否存在相交和连接。使用相同的方法独立检查会面和连接。第一个边(相遇)比另一边(连接)具有相反的边缘方向。

想法是使用拓扑排序，并检查下一个访问的顶点是否与已经访问的顶点相交。为此，每个顶点 ( v) 必须存储:

• 它的前身集 P(v) = {x; x < v} ,
• 它的拓扑索引I(v) .

查找两个给定顶点 ( a, b ) 是否存在交集是通过以下方式完成的:

P_ab = P(a) intersect P(b)
Find x in P_ab with max I(x).
If |P(x)| = |P_ab| - 1 than x is a meet of a and b.

访问新顶点v ，要检查的节点是否符合 v是 C(v) = all already visited nodes - P(v) .使用部分顺序的属性来减少检查次数。如果v和 a in C(v)开会，如果b in C(v)和 b < a , 比 v和 b已经见面(与 v 和 a 相同)。有了它就足以检查 C(v) 中的顶点具有未解析的传出边 ( U(v) )。可能甚至不需要检查 U(v) 中的所有顶点，因为其中一些顶点可以排序。为了更容易检查来自 U(v) 的顶点按索引降序排列 ( I(x) )。

session 的支票数量按顺序 |V| * width(G) ，可能比 |V|^2 小得多.

存在内存问题，因为每个顶点都必须存储其前身的集合。那可能是|V|^2空间。这可以减少，因为如果访问顶点 x不在 U(v) 中只能检查尺寸 P(x)。所以，对于这些顶点 P(x)可以删除和|P(x)|而是存储起来。

请注意，如果下一个访问的顶点在边上只有一个，则不需要测试它是否与 U(v) 中的顶点相遇。 .这种推理甚至可以扩展到如果子格由一条边连接到访问的顶点，则不必检查所有子格顶点。但是，可能很难检查子格:-)