Ich bin verwirrt über die Implementierung von „degree()“ und „incident_edges()“ für die topologische Sortierung in Pytho ⇐ Python

[Anonymous]

Ich studiere Graphalgorithmen und lerne die topologische Sortierung eines gerichteten azyklischen Graphen (DAG).
Die Funktion topological_sort unten ist in unserem Lehrbuch enthalten und ich darf sie nicht ändern. Ich verstehe den Algorithmus konzeptionell, bin mir aber nicht sicher, wie ich die unterstützenden Graph-Methoden, von denen der Algorithmus abhängt, richtig implementieren soll.
Insbesondere bin ich mir nicht sicher über das korrekte Verhalten der folgenden Methoden:

• Code: Select all

  degree(u, incoming)

• Code: Select all

  incident_edges(u)

• wie die Edge.opposite()-Methode mit ihnen funktionieren soll

Ich habe versucht, den Algorithmus mit einem einfachen realen DAG (Rezeptschritte) zu testen, bin mir aber nicht sicher, ob meine Diagrammimplementierung mit den Erwartungen des Algorithmus übereinstimmt.
Unten ist ein minimal reproduzierbares Beispiel.

Code
Topologische Sortierung (aus dem Lehrbuch – unverändert)

Code: Select all

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

Meine Graph- und Edge-Implementierung (wo ich verwirrt bin)

Code: Select all

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

Code: Select all

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

Testen mit einem einfachen DAG (Rezeptschritte)

Code: Select all

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))

Fragen

• Was sollte Degree(u, incoming) zurückgeben, damit es den Erwartungen des Algorithmus korrekt entspricht?
• Wie sollte incident_edges(u) in diesem Fall für einen gerichteten Graphen implementiert werden?
• Ist mein Verständnis von Edge.opposite() in diesem Zusammenhang korrekt?
• Wird erwartet, dass der Algorithmus eine unvollständige Liste zurückgibt, wenn das Diagramm einen Zyklus enthält?

Jede Klarstellung wäre willkommen.