如何给无环有向图的顶点分配“级别”？

Question

我有一个无环有向图。我想为每个顶点分配级别，以保证如果边(v1,v2)在图中，则level(v1)>level(v2)。我还希望当(v1,v2)和(v3,v2)都在图中时，level(v1)=level(v3)。此外，可能的级别是离散的(最好将它们视为自然数)。理想情况下，当(v1,v2)在图中且没有其他路径从v1到v2时，level(v1)=level(v2)+1，但有时在其他约束条件下这是不可能的，例如考虑一个由五个顶点组成的图，其中包含边(a,b) (b,d) (d,e) (a,c) (c,e)。

有人知道解决这个问题的算法吗？我的图相当小(|V|<=25左右)，所以我不需要非常快的算法——简单性更重要。

我目前的想法是找到最小元素，将其分配为级别0，找到所有父节点，将它们分配为级别1，并通过为适当的顶点添加+0.5来解决矛盾，但这似乎非常糟糕。

另外，我感觉删除所有“隐含”的边可能会有帮助(即，如果图包含(v1,v2)和(v2,v3)，则删除(v1,v3)。

- george smiley

Answer 1

我认为将顶点v的级别设定为从v出发的最长有向路径的长度可能对你有很大帮助。在Python中：

# the level of v is the length of the longest directed path from v
def assignlevel(graph, v, level):
    if v not in level:
        if v not in graph or not graph[v]:
            level[v] = 0
        else:
            level[v] = max(assignlevel(graph, w, level) + 1 for w in graph[v])
    return level[v]

g = {'a': ['b', 'c'], 'b': ['d'], 'd': ['e'], 'c': ['e']}
l = {}
for v in g:
    assignlevel(g, v, l)
print l

输出：

{'a': 3, 'c': 1, 'b': 2, 'e': 0, 'd': 1}

- user382751

---

请注意，这种级别方案本质上忽略了“隐式”边缘。 - user382751

Answer 2

你可以使用拓扑排序为每个顶点分配唯一的编号，使其具有所需的属性。同样地，你可以按照拓扑顺序遍历节点并分配max(parents)+1的值。

- Kyle Butt