Как назначить уровни вершинам ациклического ориентированного графа?

У меня ациклический ориентированный граф. Я хотел бы назначить уровни каждой вершине таким образом, чтобы гарантировать, что если ребро (v1, v2) находится в графе, то level (v1)> level (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 или около того), поэтому мне не нужно что-то сногсшибательное - простота важнее.

До сих пор я думал просто найти наименьший элемент, присвоить ему уровень 0, найти всех родителей, назначить им уровень 1 и разрешить противоречия, добавив +0,5 к соответствующим вершинам, но это кажется довольно ужасным.

Кроме того, у меня возникает ощущение, что было бы полезно удалить все «неявные» ребра (т.е. удалить (v1, v3), если граф содержит как (v1, v2), так и (v2, v3).


java graph directed-acyclic-graphs algorithm
person george smiley    schedule 06.08.2010    source источник

Ответы (2)


arrow_upward
5
arrow_downward

Я думаю, что если позволить уровню 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}
person user382751    schedule 06.08.2010
comment
Обратите внимание, что эта схема выравнивания по существу игнорирует неявные ребра. - person user382751; 06.08.2010

arrow_upward
2
arrow_downward

Вы можете использовать топологическую сортировку, чтобы присвоить уникальный номер каждой вершине со свойством, которое вы хотите. Точно так же вы можете пройти по узлам в топологическом порядке и назначить max (parent) + 1

person Kyle Butt    schedule 06.08.2010