3

非巡回有向グラフがあります。エッジ (v1,v2) がグラフ内にある場合、レベル (v1) > レベル (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) を持つ 5 つの頂点上のグラフを考えます。
これを解決するための適切なアルゴリズムを知っている人はいますか? 私のグラフはかなり小さい (|V| <= 25 程度) ので、非常に高速なものは必要ありません。シンプルさがより重要です。

これまでの私の考えでは、最小の要素を見つけてレベル 0 を割り当て、すべての親を見つけてレベル 1 を割り当て、適切な頂点に +0.5 を追加して矛盾を解決するだけですが、これはかなりひどいようです。

また、すべての「暗黙の」エッジを削除する (つまり、グラフに (v1,v2) と (v2,v3) の両方が含まれる場合は (v1,v3) を削除する) と役立つかもしれないと感じています。

4

2 に答える 2

5

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}
于 2010-08-06T04:05:54.563 に答える
2

トポロジー ソートを使用して、必要なプロパティを持つ各頂点に一意の番号を割り当てることができます。同様に、トポロジー順にノードを調べて、max(parents) + 1 を割り当てることができます。

于 2010-08-06T04:33:55.640 に答える