Получить топологический порядок графа из списка смежности

Имея файл со списком смежности Graph G, например:

0 -> 13,16,20,22,4,5
1 -> 12,13,16,17,19,22,23,24,25,3,4
10 -> 13,14,17,20,23,24
11 -> 12,19,20,22,23
12 -> 15,20,24
13 -> 20,21,22
15 -> 23
17 -> 25
19 -> 20,25
2 -> 16,19,3,7
20 -> 22,23
21 -> 22,23,24
22 -> 25
24 -> 25
3 -> 15,21,4
4 -> 10,12,14,15,16,17,18,19,21,23,5
5 -> 11,16,17,20,23,8,9
6 -> 12,14,18,22
7 -> 14,17,22
8 -> 21,24
9 -> 12,14

Я хочу получить его топологический порядок, Graph G - это направленный ациклический граф.

Прежде всего, я хочу разобрать текстовый файл и поместить все в словарь. Однако у меня есть некоторые проблемы, сначала при чтении файла мне не хватает чего-то, что я пропускаю первый элемент после ->:

f = open('topo.txt', 'r')
    line_list = f.readlines()
    G = {int(line.split('->')[0]): [int(val) for val in line.split(',')[1:] if val] for line in line_list if line}

Я бы получил:

('G:', {0: [16, 20, 22, 4, 5], 1: [13, 16, 17, 19, 22, 23, 24, 25, 3, 4], 2: [19, 3, 7], 3: [21, 4], 4: [12, 14, 15, 16, 17, 18, 19, 21, 23, 5], 5: [16, 17, 20, 23, 8, 9], 6: [14, 18, 22], 7: [17, 22], 8: [24], 9: [14], 10: [14, 17, 20, 23, 24], 11: [19, 20, 22, 23], 12: [20, 24], 13: [21, 22], 15: [], 17: [], 19: [25], 20: [23], 21: [23, 24], 22: [], 24: []})
[16, 20, 22, 4, 5]

Для каждой строки мне не хватает одного элемента, например, 0 будет: [13, 16, 20, 22, 4, 5] не [16, 20, 22, 4, 5] он пропускает 13

Затем при использовании функции dfs я получаю сообщение об ошибке:

для v в G[s]: # для каждого ребра (s, v) KeyError: 16

"""Performs a depth first search in graph G starting from vertex s
    Input: G - the input graph in the adjacency list representation via a dictionary
    s - the starting vertex
    explored - a set of explored vertices
    distance - a dictionary representing the topological order of the vertices
    current_label - the current order of the topological order, disguised as a mutable list"""
def dfs(G, s, explored, distance, current_label):
    explored.add(s)
    #print G[s]
    for v in G[s]: # for every edge (s, v)
        if v not in explored:
            dfs(G, v, explored, distance, current_label)
    distance[current_label[0]] = s
    current_label[0] -= 1

"""Performs and outputs a topological sort of graph G using dfs
    Input: G - the input graph in the adjacency list representation via a dictionary
    distance - a dictionary representing the topological order of the vertices"""
def topological_sort(G, distance):
    explored = set()
    current_label = [len(G)]
    for v in G.keys():
        if v not in explored:
            dfs(G, v, explored, distance, current_label)

def main():
    f = open('topo.txt', 'r')
    line_list = f.readlines()
    G = {int(line.split('->')[0]): [int(val) for val in line.split(',')[1:] if val] for line in line_list if line}
    print("G:", G)
    distance = dict()
    topological_sort(G, distance)
    topo = iter(sorted(distance.items()))
    print("A topological order of G is:")
    for _, vertex in topo:
        print( vertex + " ")
    print()

if __name__ == '__main__':
    main()

Как будет выглядеть правильный код? Вывод должен быть

1, 0, 2, 6, 3, 7, 4, 5, 18, 10, 11, 16, 8, 9, 13, 17, 19, 12, 14, 21, 15, 20, 24, 23, 22, 25

python graph topological-sort
person edgarmtze    schedule 30.09.2015    source источник

Ответы (1)


arrow_upward
2
arrow_downward

line.split(',')[1:] при запуске на 0 -> 13,16,20,22,4,5 принимает участие 16,20,22,4,5, а это не то, что вам нужно. Должно быть line.split('->')[1].split(','). Лично я бы написал это более явно, чтобы избежать двойного вызова .split('->'):

def parse_graph(lines):
    G = dict()
    for line in lines:
        left, right = line.split('->')
        G[int(left)] = [int(val) for val in right.split(',')]
    return G
...
G = parse_graph(line_list)

Далее, поскольку не каждая вершина находится в G в качестве ключа, вы должны добавить следующую строку в dfs:

#dfs
...
if s in G: #add this
    for v in G[s]: # for every edge (s, v)
        if v not in explored:
            dfs(G, v, explored, distance, current_label, l)
...

#

Наконец, измените print( vertex + " ") на print( str(vertex), end=' '). Остальное вроде нормально.

Еще одна вещь, которую вы, возможно, захотите рассмотреть, это то, что вместо того, чтобы отслеживать два параметра current_label, distance, вы можете просто сохранить один список vertices, скажем, который сохраняет порядок посещенных вершин. Поэтому вместо того, чтобы иметь

distance[current_label[0]] = s
current_label[0] -= 1

вы могли бы просто иметь

vertices.append(s)

Эффект тот же. Однако в конце вы должны вывести reversed(vertices), и это будет ваш топологический порядок.

person sve    schedule 30.09.2015