如何分配“级别"到无环有向图的顶点? [英] How to assign "levels" to vertices of an acyclic directed graph?

问题描述

我有一个无环有向图.我想以某种方式为每个顶点分配级别，以保证如果边(v1，v2)在图中，则级别(v1)> 级别(v2).如果 level(v1) = level(v3) 只要 (v1,v2) 和 (v3,v2) 在图中，我也希望它.此外，可能的级别是离散的(也可以将它们视为自然数).理想的情况是 level(v1) = level(v2) + 1 每当 (v1,v2) 在图中并且没有其他从 v1 到 v2 的路径时，但有时这在其他约束下是不可能的 -例如，考虑五个顶点上的图，边为 (a,b) (b,d) (d,e) (a,c) (c,e).
有谁知道一个像样的算法来解决这个问题?我的图相当小(|V| <= 25 左右)，所以我不需要快速的东西——简单更重要.

I have an acyclic directed graph. I would like to assign levels to each vertex in a manner that guarantees that if the edge (v1,v2) is in the graph, then level(v1) > level(v2). I would also like it if level(v1) = level(v3) whenever (v1,v2) and (v3,v2) are in the graph. Also, the possible levels are discrete (might as well take them to be the natural numbers). The ideal case would be that level(v1) = level(v2) + 1 whenever (v1,v2) is in the graph and there is no other path from v1 to v2, but sometimes that isn't possible with the other constraints - e.g, consider a graph on five vertices with the edges (a,b) (b,d) (d,e) (a,c) (c,e).
Does anyone know a decent algorithm to solve this? My graphs are fairly small (|V| <= 25 or so), so I don't need something blazing fast - simplicity is more important.

到目前为止，我的想法是找到一个最小元素，将其指定为 0 级，找到所有父项，将它们指定为 1 级，然后通过向适当的顶点添加 +0.5 来解决矛盾，但这看起来很糟糕.

My thinking so far is to just find a least element, assign it level 0, find all parents, assign them level 1, and resolve contradictions by adding +0.5 to the appropriate vertices, but this seems pretty awful.

此外，我觉得删除所有隐式"边可能会有所帮助(即，如果图形同时包含 (v1,v2) 和 (v2,v3)，则删除 (v1,v3)).

Also, I get the feeling that it might be helpful to remove all "implicit" edges (i.e, remove (v1,v3) if the graph contains both (v1,v2) and (v2,v3).

推荐答案

我认为让 v 的级别是 v 的最长有向路径的长度可能对您有用.在 Python 中:

I think letting the level of v be the length of the longest directed path from v might work well for you. In 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}

这篇关于如何分配“级别"到无环有向图的顶点?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！