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

问题描述

我有一个无环的有向图。我想以确保如果边（v1，v2）在图中，然后是level（v1）> level（v2）的方式为每个顶点分配级别。如果（v1，v2）和（v3，v2）在图中，level（v1）= level（v3），我也会喜欢它。此外，可能的级别是离散的（不妨将它们视为自然数）。理想的情况是，当（v1，v2）在图中并且从v1到v2没有其他路径时，该级别（v1）=级别（v2）+ 1，但有时这对于其他约束是不可能的 - （a，b）（b，d）（d，e）（a，c）（c，e）的五个顶点上的图。有没有人知道一个体面的算法解决这个问题？我的图很小（| V | <= 25左右），所以我不需要快速的东西 - 简单性更重要。

到目前为止，我的想法是找到最少的元素，将其分配给0级，找到所有父母，将他们分配给1级，并通过将+0.5添加到这样看起来很不错。

另外，我觉得删除所有隐含边缘可能会有所帮助（例如remove（v1，v3 ）如果图形同时包含（v1，v2）和（v2，v3）。

解决方案

我认为让v从v开始最长的定向路径的长度可能适合你。在Python中：

 ＃v的等级是从v 
开始的最长有向路径的长度def assignlevel（graph，v，level）：
如果v不在等级中：
如果v不在图中或者不在图中[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 g：
 assignlevel（g，v，l）
打印l 
  

输出：

<$ p $ c'：'a'：3，'c'：1，'b'：2，'e'：0，'d'：1}

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.

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.

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).

解决方案

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

Output:

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

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