Непонятно, как реализовать степень() и инцидент_еджес() для топологической сортировки в Python. ⇐ Python

[Anonymous]

Я изучаю графовые алгоритмы и изучаю топологическую сортировку ориентированного ациклического графа (DAG).
Приведенная ниже функция topological_sort представлена ​​в нашем учебнике, и мне не разрешено ее изменять. Я концептуально понимаю алгоритм, но не понимаю, как правильно реализовать вспомогательные методы Graph, от которых зависит алгоритм.
В частности, я не уверен в правильном поведении следующих методов:

• Код: Выделить всё

  degree(u, incoming)

• Код: Выделить всё

  incident_edges(u)

• как с ними должен работать метод Edge.opposite()

Я пытался протестировать алгоритм, используя простой реальный DAG (шаги рецепта), но я не уверен, что моя реализация графа соответствует ожиданиям алгоритма.
Ниже приведен минимальный воспроизводимый пример.

Код
Топологическая сортировка (из учебника – без изменений)

Код: Выделить всё

def topological_sort(g):
'''Return a list of vertices of directed acyclic graph g in topological order.

If graph g has a cycle, the result will be incomplete.
'''
topo = []
ready = []
incount = {}

for u in g.vertices():
incount[u] = g.degree(u, False)
if incount[u] == 0:
ready.append(u)

while len(ready) > 0:
u = ready.pop()
topo.append(u)

for e in g.incident_edges(u):
v = e.opposite(u)
incount[v] -= 1
if incount[v] == 0:
ready.append(v)

return topo

Моя реализация Graph и Edge (где я запутался)

Код: Выделить всё

class Edge:
def __init__(self, u, v):
self.u = u
self.v = v

def opposite(self, u):
# I am not fully sure if this is correct
return self.v

Код: Выделить всё

class Graph:
def __init__(self):
self.outgoing = {}
self.incoming = {}

def add_edge(self, u, v):
if u not in self.outgoing:
self.outgoing[u] = []
self.incoming[u] = []

if v not in self.outgoing:
self.outgoing[v] = []
self.incoming[v] = []

self.outgoing[u].append(v)
self.incoming[v].append(u)

def vertices(self):
return self.outgoing.keys()

def degree(self, u, incoming):
# CONFUSION:
pass

def incident_edges(self, u):
# CONFUSION:
pass

Тестирование с помощью простого DAG (шаги рецепта)

Код: Выделить всё

g = Graph()

g.add_edge("Wash Rice", "Soak Rice")
g.add_edge("Soak Rice", "Boil Rice")
g.add_edge("Boil Rice", "Layer Rice")

g.add_edge("Cook Masala", "Layer Rice")
g.add_edge("Layer Rice", "Dum")
g.add_edge("Dum", "Serve")

print(topological_sort(g))

Вопросы

• Что должна возвращать степень(u, incoming), чтобы она правильно соответствовала ожиданиям алгоритма?
• Как в этом случае следует реализовать Incident_edges(u) для ориентированного графа?
• Правильно ли я понимаю Edge.opposite() в этом контексте?
• Ожидается ли, что алгоритм вернет неполный список, если граф содержит цикл?

Будем признательны за любые разъяснения.>

Подробнее здесь: https://stackoverflow.com/questions/798 ... cal-sort-i