如何为非循环有向图的顶点分配“级别”？

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）。

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}