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

Question

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

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

Кроме того, у меня возникает ощущение, что может быть полезно удалить все «неявные» ребра (т.е. удалить (v1, v3), если граф содержит как (v1, v2), так и (v2, 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}

Answer 2

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