Jain. Erstens wird `cand` bei Dir nie leer. Warum das findest Du heraus wenn Du dir mal anschaust was in `start` in der aufrufenden Funktion enthalten ist. Ein Indiz dafür hätte Dir schon auffallen können: Wieviele Knoten gibt es insgesamt, die in `traversed` gespeichert sein können und was gibt Dir das ``print len(traversed)`` aus!psychodad hat geschrieben:Ich entferne doch alle bereits untersuchten KnotenDas meinst Du doch mit Rekursionsaanker?Code: Alles auswählen
# Bereits besuchte Knoten loeschen for x in traversed: if x in aAdj: aAdj.remove(x) if x in bAdj: bAdj.remove(x) # ... # Und wenn alle Knoten besucht worden, dann ist cand leer, also # len(cand) == 0, und damit ist die Rekursion beendet cand = getCompatible2(testnode, bAdj) while len(cand) != 0:
Und zweitens fehlt wirklich noch ein Rekursionsanker. Im Moment wird nur dann `True` zurückgegeben, wenn der rekursive Aufruf `True` ergibt. Und dass tut er nur wenn der rekursive Aufruf in dem rekursiven Aufruf...
Du musst erkennen, ob Du fertig bist und dann `True` zurückgeben. Sonst endet das nie. Geh mal in Gedanken den Code Schritt für Schritt für zwei ganz einfache Graphen durch. Es reicht schon wenn nur ein Knoten in jedem Graphen ist, ohne jede Kante. Wenn man den Rekursionsanker hinzufügt, dann funktioniert dein Code -- sogar mit dem leicht "kaputten" `traversed`. Hab's ausprobiert.
Stimmt sollte man nicht. Aber warum veränderst Du die Liste in der Schleife?Und wie soll ich die while-Schleifen entfernen, wenn ich die Liste im Schleifenrumpf verändere? Denn wenn ich sie verändere, dann habe ich mal gelesen soll man nicht mit for durch die Sequenz iterieren
Code: Alles auswählen
while len(cand) != 0:
if IsomorphieSuche(testnode, cand.pop(), traversed[:]):
return True
# =>
for node in cand:
if IsomorphieSuche(testnode, node, list(traversed)):
return True
Code: Alles auswählen
result = list()
for item in iterable:
if pred(item):
result.append(foo(item))
# <==>
result = [foo(item) for item in iterable if pred(item)]