Seite 1 von 2
Durch Dictionaries iterieren
Verfasst: Mittwoch 30. März 2005, 11:14
von psychodad
Hi,
also ich möchte ein C++ Programm in ein Python neu schreiben, jetzt stehe ich jedoch vor einem Problem. In dem C++ Programm kommt folgender Code vor.
Code: Alles auswählen
void backtrack(map m, aktKnoten ) {
// ...
// rekursiver Aufruf
backtrack(m, nächsterKnoten(aktKnoten));
}
// ...
map m;
backtrack(m, m.first_node());
Das ist Pseudo-C++-Code, da ich nicht weiß ob hier alle C++ können.
Also die Klasse 'map' entspricht in der dictionary-Klasse aus Python, in dem Backtrackingalgorithmus muss ich die Elemente der Map einzeln durchlaufen.
In Python sieht dass bei mir in etwas so aus.
Code: Alles auswählen
def backtrack(dict, cur):
value = cur
# do stuff ...
# rekursiver Aufruf
try:
backtrack(dict, cur.next())
except StopIteration:
pass # Keine weiteren Elemente
# ...
# Aufruf
backtrack(d, iter(d))
Das funktioniert auch, nur sieht das für mich wie ein schlechter 'Hack' aus, denn ich setze hier eine Exception als 'reguläres' Mittel zu Steuerung des Programmflusses ein. Nun sind Exception aber nur zum Abfangen von Fehlern da, und nicht zum festlegen von Programmabläufen wenn keine Fehler auftreten, das oben ist also ganz mieser Stil. Da gibt es doch bestimmt eine bessere Lösung?
PS: Falls diese Frage trivial ist, bin relativ neu in Python.
Danke, Stefan
Verfasst: Mittwoch 30. März 2005, 11:52
von leoel
Probier doch mal aus, dass Dir 'backtrack' einen Rückgabewert gibt:
Code: Alles auswählen
def backtrack(...):
if not <Abbruchbedingung>:
backtrack(...)
==> so (oder so ähnlich) sollte es gehen...
Verfasst: Mittwoch 30. März 2005, 12:19
von Gast
Die Abbruchbedinung ist ja eben, dass alle Elemente durchlaufen wurden.
Wie frage ich den Ierator ab, ob er schon am Ende ist ??
Also nochmal in das Problem in Pseudocode:
Gegeben ist eine Liste, und nun möchte ich, mit einer Funktion, die sich rekursiv aufruft, die Elemente durchlaufen.
Code: Alles auswählen
backtrack( element )
print element
if noch Elemente in der Liste
backtrack( nächstes Element ) # Mit nächstem Element aufrufen
Bsp.
backtrack( l.firstElement() )
sollte dann folgende Ausgabe erzeugen:
a
b
c
d
Das oben ist ja kein Pythoncode, sondern nur Pseudo. In C++ sieht das etwa so aus.
Code: Alles auswählen
void backtrack( list<string>::iterator it, list<string>::iterator end ) {
cout << *it << endl;
if( it != end ) {
++it;
backtrack(it);
}
}
// ...
list<string> li;
li.push_back("a");
li.push_back("b");
li.push_back("c");
li.push_back("d");
Hoffentlich ist jetzt klar was ich meine. Suche wie verrückt, aber finde keine passende, saubere Lösung, um dieses Kontrukt in Python umzusetzen.
Verfasst: Mittwoch 30. März 2005, 13:54
von CM
Hi
so ganz 100%ig ist mir nicht klar was Du willst. Über ein Dictionary iterieren? Warum nicht auf Pythonart:
Code: Alles auswählen
d = {1:'a',2:'b'}
for key in d: print d
#oder
for key,value in d.iteritems(): print key,value
Oder Du beschäftigst Dich mit Listen und willst reverse drüber gehen. Schau mal was das Tutorial dazu hergibt. Ein Beispiel:
Code: Alles auswählen
l = [1,2,3,4]
print l[::-1] #siehe Tutorial
#und dann dies
l.reverse()
print l
Du kannst natürlich auch einen rekursiven Algorithmus basteln. Aber warum von hinten durch die Brust ins Auge? Oder Du müsstest vielleicht doch noch mal Deine Motivation näher erläutern ...
Gruß und viel Spaß mit Python,
Christian
Verfasst: Mittwoch 30. März 2005, 14:50
von Gast
Auf Pythonart iteriere ich ja linear durch die Elemente, ich will aber einen Suchbaum aufbauen. Und das macht üblicherweise mit Rekursion.
Okay, um vielleicht klar zu machen was ich will.
Code: Alles auswählen
def extendIso(sub, graph, cand, it):
try:
v = it.next() # 'v' ist ein Knoten aus dem Untergraphen
go = True
print "Go on"
except StopIteration:
print "Stop"
print cand
go = False
return True
print "Extend: ", v
for w in graph:
print "Test: ", w
# Kann der Knoten 'v' dem Knoten 'w' zugeordnet werden?
if cand[v].has_key(w):
#next = cand.copy() # TODO: Verifizieren, deepcopy?
next = copy.deepcopy(cand)
for i in next: # ??
next[i] = copy.deepcopy(cand[i])
print "Map %s to %s " % (v, w)
# Ordne 'v' 'w' zu
for x in sub:
if x!=v and next[x].has_key(w):
del next[x][w]
# print "t: ", w
for y in graph:
if y!=w and next[v].has_key(y):
del next[v][y]
# print "OK"
assert len(next[v]) == 1 and next[v].has_key(w), "Zuordnung OK"
# print "Ausgabe"
# Ausgabe
for x in sub:
# print next.keys()
assert len(next[x])==1, "Zuordnung"
print "{ %s, %s }" % ( x, next[x].keys() )
if x == v:
break
if refineIso(sub, graph, next, v, w): # 1. Testen, ob Lösung legal
return extendIso(sub, graph, next, it) # 2. Weitersuchen
return False
Das ist der aktuelle Code aus meinem Projekt.
Unter 1) und 2) sind die relevanten Backtrackingteile.
Verfasst: Mittwoch 30. März 2005, 15:32
von leoel
Könntest Du vielleicht in Worten erklären, was Du machen willst. Ich habe nämlich keine Ahnung, was Dein Problem ist
Wenn es gar nicht anders geht, machst Du es eben nicht über .next() sondern über eine Zählvariable und du überprüfst halt, ob Du das Ende des Dictionarys erreicht hast.
(ist aber auch nicht hübsch...)
Verfasst: Mittwoch 30. März 2005, 15:37
von CM
Kann mich leoels Worten nur anschließen. Auch wenn ich mittlerweile so ungefähr zu verstehen glaube wohin die Reise geht, ist es ein wenig schwierig Deinen Wunsch nachzuvollziehen, ohne ihn zu kennen. Und wenn Du nur eine Funktion pastest, solltest Du vielleicht auch noch genau schreiben, was das für Parameter sind, die übergeben werden, und was herauskommen soll (würde ich ja in einem C++-Forum nicht anders machen
), ggf. auch mittels einer Testfunktion.
Gruß,
Christian
Re: Durch Dictionaries iterieren
Verfasst: Mittwoch 30. März 2005, 15:49
von jens
psychodad hat geschrieben:Code: Alles auswählen
def backtrack(dict, cur):
value = cur
# do stuff ...
# rekursiver Aufruf
try:
backtrack(dict, cur.next())
except StopIteration:
pass # Keine weiteren Elemente
# ...
# Aufruf
backtrack(d, iter(d))
Ich weiß auch nicht so recht, was gemacht werden soll, aber try und StopIteration kommt mir sehr komisch vor...
Warum nicht einfach den rekursiven Aufruf nur unter der Bedingung machen, wenn weitere Daten vorhanden sind:
Code: Alles auswählen
def backtrack(dict, cur):
value = cur
# do stuff ...
# rekursiver Aufruf
if da gibts noch mehr == True:
backtrack(dict, cur.next())
backtrack(d, iter(d))
Tip: Such doch einfach mal im Forum nach "rekursiv" vielleicht siehst du da Codeschnipsel, die dir weiter helfen!
Re: Durch Dictionaries iterieren
Verfasst: Mittwoch 30. März 2005, 16:01
von joe
jens hat geschrieben:
Ich weiß auch nicht so recht, was gemacht werden soll, aber try und StopIteration kommt mir sehr komisch vor...
Das ist schon ok so. "StopIteration" ist für die programmablaufsteuerung vorgesehen. Deshalb sind "StopIteration" und "SystemExit" auch die einzigen buildin-ausnahmen, die nicht von "StandardError" erben, sondern direkt von "Exception".
joe
Verfasst: Mittwoch 30. März 2005, 17:30
von psychodad
Ja, einfach den Quellcode zu posten ist sicherlich nicht besonders schlau, da ist viel dabei was nicht zum Problem gehört und es zu erklären würde hier vielleicht den Rahmen sprengen.
Aber glücklicherweise scheint ihr schon verstanden zu haben, worum es geht.
Also eine Zählvariable wäre prinzipiell möglich, nur ist das nicht ineffizient, auf die Elemente in einem Dictionary jedesmal mit einem Index zuzugreifen?? Dann müsste am Anfang meiner Funktion in etwa folgendes stehen bzw. folgende Funktion müsste ich nutzen.
Code: Alles auswählen
def getElement(offset, dict):
for x in dict:
++i
if i == offset:
return x
Ja, und das mit der Exception scheint mir nicht nur vom Design schlecht zu sein, es ist auch so umständlich. Normalerweise wird doch immer gesagt Pythonkontrukte sind besonders elegant, aber das find ich nicht elegant.
Achja. und nur eine Bedingung? Wie soll das gehen?
Ja, ich muss doch immer auf das aktuelle Element in dem Dictionary zugreifen, und das durchlaufen tue ich in den rek. Aufrufen.
Achso, das Programm ist zum Test auf Graphenisomorphie. Eine Beschreibung des Algorithmus gibt es hier.
http://www.strange-phenomenom.de/pmwiki ... Isomorphie
Wie man sieht eine klassische Tiefensuche bzw. Backtracking, wie man es aus der typ. Informatik-Algorithmen&Datenstrukturen-Vorlesung kennt
Verfasst: Mittwoch 30. März 2005, 19:49
von jens
Aha... Backtracking mußte ich erstmal nachschauen:
http://de.wikipedia.org/wiki/Backtracking
Ach, vielleicht hilft dir .pop() weiter...
Verfasst: Mittwoch 30. März 2005, 20:07
von Gast
dann würde ich ja die elemente aus meinem dictionary entfernen, dass will ich aber nicht unbedingt.
Prinzipiell wäre das schon möglich, aber nebenbei müsste ich dann auch viele kopien von meinem dictionary machen, da ja jeder Lösungsweg, den ich "Rückverfolge" sein eigenes unveändertes Dictionary brauch.
Verfasst: Donnerstag 31. März 2005, 06:18
von BlackJack
Dein Code sieht aber doch ein wenig(?) anders aus als der Algorithmus unter der angegebenen URL.
Musst Du denn wirklich einen Iterator beim Aufruf übergeben? Kannst Du das nicht in einer Schleife lösen in der dann der rekursive Aufruf mit nur einem Element gemacht wird? In dem Beispielcode auf der Wiki-Seite wird das jedenfalls so gemacht.
Was an dem C++ Quelltext furchtbar ist, sind die ``while``-Schleifen. Die sollte man unter Python ganz dringend surch ``for``-Schleifen ersetzen. Ich weiss gar nicht warum das nicht auch im C++ Quelltext gemacht wurde. Dann wäre der Algorithmus IMHO viel lesbarer/verständlicher.
Willst Du eine Lösung finden, also am Ende eine Abbildung von Knoten aus Graph A auf Knoten von Graph B haben, oder wie im Beispiel nur wissen ob es überhaupt eine Lösung gibt?
Wenn man mal davon absieht, dass in der `IsomorphieSuche()` ein Rekursionsanker fehlt, ist das ziemlich einfach nach Python umzusetzen. Sieht bei mir aber komplett anders aus als der Quelltext, den Du hier gepostet hast!?
Verfasst: Donnerstag 31. März 2005, 08:48
von CM
Hoi,
kann mich so manchem Vorschlag wieder mal nur anschließen. Eine Bemerkung kann ich mir denn doch aber nicht verkneifen: Vermeide doch bitte Schlüsselwörter wie "dict" im Code, wenn Du es nicht mußt. Du überschreibst doch auch in C/C++ nicht Funktionen wie "assert" oder "malloc", wenn Du nicht mußt
.
Mit Sicherheit von Interesse ist von folgendes
Essay von Guido von Rossum. Etwas veraltet wie Du feststellen wirst, aber vielleicht ... Und sonst google mal mit "Python graph theory".
Außerdem gibt es noch "Algorithms in C" von O'Reilly mit einer Einführung zu Graphen: Mir ist aufgefallen, daß man dies sehr leicht in Python übersetzen kann.
Gruß,
Christian
Verfasst: Donnerstag 31. März 2005, 12:02
von psychodad
Ja, mein Algorithmus arbeitet etwas anders als der in dem Script angegebene. Es ist mir nicht gelungen denn aus dem Script 1 zu 1 umzusetzen, meiner basiert eher auf einem Algorithmus aus "Algorithms on Trees and Graphs" von Gabriel Valiente.
Mich interessiert nur ob eine Lösung existiert, die genaue Abbildung brauche ich nicht unbedingt.
"Musst Du denn wirklich einen Iterator beim Aufruf übergeben? Kannst Du das nicht in einer Schleife lösen in der dann der rekursive Aufruf mit nur einem Element gemacht wird? In dem Beispielcode auf der Wiki-Seite wird das jedenfalls so gemacht. "
Gelingt mir eben nicht, auch wenn es in dem Script so beschrieben wird.
Code: Alles auswählen
def extendIso(sub, graph, cand, it):
# ...
if refineIso(sub, graph, next, v, w): # 1. Testen, ob Lösung legal
return extendIso(sub, graph, next, it) # 2. Weitersuchen
Wenn ich mit einer äußeren Schleife die Knoten durchgehe, dann suche ich ja nicht in jedem "Zweig" des Suchbaumes weiter. Vielleicht gibt es da eine einfache algorithmische Formulierung (wie z.B. in dem Script) aber mir ist diese Umsetzung nicht gelungen.
Abgesehen davon lief das in meinem C++ Programm so auch wunderbar, mich stört halt nur dieses umständliche explizite (also nicht mit einer for-Schleife) iterieren durch das Dictionary.
PS: Ja, sorry, hab grad nicht dran gedacht, dass dict ein Schlüsselwort ist. Wie gesagt, bin noch relativer neu im Umgang mit Python.
Verfasst: Donnerstag 31. März 2005, 23:06
von BlackJack
psychodad hat geschrieben:Mich interessiert nur ob eine Lösung existiert, die genaue Abbildung brauche ich nicht unbedingt.
Na dann würde sich mein Code nochmal vereinfachen.
"Musst Du denn wirklich einen Iterator beim Aufruf übergeben? Kannst Du das nicht in einer Schleife lösen in der dann der rekursive Aufruf mit nur einem Element gemacht wird? In dem Beispielcode auf der Wiki-Seite wird das jedenfalls so gemacht. "
Gelingt mir eben nicht, auch wenn es in dem Script so beschrieben wird.
Hm, ich habe den Code direkt auf der Webseite fast 1:1 übernommen. Aus den ``while``-Schleifen habe ich ``for``-Schleifen gemacht und in der zweiten Funktion noch den Rekursionsanker hinzugefügt.
Wenn ich mit einer äußeren Schleife die Knoten durchgehe, dann suche ich ja nicht in jedem "Zweig" des Suchbaumes weiter. Vielleicht gibt es da eine einfache algorithmische Formulierung (wie z.B. in dem Script) aber mir ist diese Umsetzung nicht gelungen.
Wieso wird da nicht jeder Zweig durchsucht? Mal ein kleines anderes Beispiel:
Code: Alles auswählen
def dirs(path, level=0):
for directory in filter(os.path.isdir,
map(lambda x: os.path.join(path, x),
os.listdir(path))):
print '%s%s' % (' ' * level, directory)
dirs(directory, level + 1)
Das geht in jedes Unterverzeichnis rein. Genauso kann man auch in einer ``for``-Schleife alle möglichen Lösungen des Isomorphismus-Problems durchgehen.
Das ganze klingt übrigens ziemlich nach einer Hausaufgabe, darum habe ich auch noch keinen konkreten Quelltext gepostet.
Als Anfang mal meine Node-Klasse, auf der der Algorithmus arbeitet:
Code: Alles auswählen
class Node(object):
def __init__(self, name):
self.name = name
self.neighbours = list()
def __str__(self):
return self.name
def __repr__(self):
return '<%s.%s %r at 0x%x>' % (self.__module__,
self.__class__.__name__,
self.name,
id(self))
def _get_degree(self):
return len(self.neighbours)
degree = property(_get_degree, doc='Degree of the node.')
def add_neighbour(self, other):
self.neighbours.append(other)
other.neighbours.append(self)
Verfasst: Freitag 1. April 2005, 18:16
von psychodad
Also ich habs jetzt nochmal mit deiner Nodeklasse versucht zu implementieren, aber es gelingt mir nicht. Das Programm bleibt in einer Endlosschleife.
Code: Alles auswählen
class Node(object):
def __init__(self, name):
self.name = name
self.neighbours = list()
def __str__(self):
return self.name
def __repr__(self):
return '<%s.%s %r at 0x%x>' % (self.__module__,
self.__class__.__name__,
self.name,
id(self))
def _get_degree(self):
return len(self.neighbours)
degree = property(_get_degree, doc='Degree of the node.')
def add_neighbour(self, other):
self.neighbours.append(other)
other.neighbours.append(self)
def getCompatible( a, b ): # a,b sind Knoten
r = []
for x in b.neighbours:
if x.degree == a.degree:
r.append(x)
return r
def getCompatible2( a, li ): # a ist ein Knoten, li eine Liste mit Knoten
r = []
for x in li:
if x.degree == a.degree:
r.append(x)
return r
def IsomorphieSuche(a, b, traversed):
print len(traversed)
traversed.append(a)
traversed.append(b)
aAdj = a.neighbours[:]
bAdj = b.neighbours[:]
# Bereits besuchte Knoten loeschen
for x in traversed:
if x in aAdj:
aAdj.remove(x)
if x in bAdj:
bAdj.remove(x)
for testnode in aAdj:
cand = getCompatible2(testnode, bAdj)
while len(cand) != 0:
if IsomorphieSuche(testnode, cand.pop(), traversed[:]):
return True
return False
def IsomorphieTest(g1,g2):
x = g1[0]
start = [] # Liste mit zu x kompatiblen Knoten aus g2
for n in g2:
start = start + getCompatible(x, n)
while len(start) != 0:
if(IsomorphieSuche(x, start.pop(), [])):
return True
return False
## MAIN ##
g1 = []
g1.append(Node("a1"))
g1.append(Node("a2"))
g1.append(Node("a3"))
g1.append(Node("a4"))
g1.append(Node("a5"))
g1[0].add_neighbour(g1[1])
g1[0].add_neighbour(g1[2])
g1[0].add_neighbour(g1[3])
g1[1].add_neighbour(g1[0])
g1[1].add_neighbour(g1[4])
g1[1].add_neighbour(g1[2])
g1[2].add_neighbour(g1[1])
g1[2].add_neighbour(g1[0])
g1[2].add_neighbour(g1[4])
g1[2].add_neighbour(g1[3])
g1[3].add_neighbour(g1[4])
g1[3].add_neighbour(g1[0])
g1[3].add_neighbour(g1[2])
g1[4].add_neighbour(g1[3])
g1[4].add_neighbour(g1[2])
g1[4].add_neighbour(g1[1])
g2 = [Node("b1"), Node("b2"), Node("b3"), Node("b4"), Node("b5") ]
g2[0].add_neighbour(g2[1])
g2[0].add_neighbour(g2[2])
g2[0].add_neighbour(g2[3])
g2[0].add_neighbour(g2[4])
g2[1].add_neighbour(g2[0])
g2[1].add_neighbour(g2[2])
g2[1].add_neighbour(g2[4])
g2[2].add_neighbour(g2[1])
g2[2].add_neighbour(g2[0])
g2[2].add_neighbour(g2[3])
g2[3].add_neighbour(g2[4])
g2[3].add_neighbour(g2[0])
g2[3].add_neighbour(g2[2])
g2[4].add_neighbour(g2[1])
g2[4].add_neighbour(g2[0])
g2[4].add_neighbour(g2[3])
if IsomorphieTest(g1, g2):
print "Isomorph"
else:
print "Nicht isomorph"
Bei deinem dirs-Beispiel ist die Rekursion irgendwie in listdir() implementiert, wer weiß wie die Programmierprofis der Pythonimplementierung das umgesetzt haben
Also ich weiss nicht wie dies gemacht haben.
Ne, also ich verlange gar nicht von euch dass ihr meine Hausaufgaben macht! Wäre mir auch angenehmer, und sinnvoller, wenn ich selbst auf die Lösung komme. Aber ich hoffe natürlich dass ihr mir auf meinem Weg zu Erkenntnis helft.
Verfasst: Freitag 1. April 2005, 18:17
von psychodad
Also ich habs jetzt nochmal mit deiner Nodeklasse versucht zu implementieren, aber es gelingt mir nicht. Das Programm bleibt in einer Endlosschleife.
Code: Alles auswählen
class Node(object):
def __init__(self, name):
self.name = name
self.neighbours = list()
def __str__(self):
return self.name
def __repr__(self):
return '<%s.%s %r at 0x%x>' % (self.__module__,
self.__class__.__name__,
self.name,
id(self))
def _get_degree(self):
return len(self.neighbours)
degree = property(_get_degree, doc='Degree of the node.')
def add_neighbour(self, other):
self.neighbours.append(other)
other.neighbours.append(self)
def getCompatible( a, b ): # a,b sind Knoten
r = []
for x in b.neighbours:
if x.degree == a.degree:
r.append(x)
return r
def getCompatible2( a, li ): # a ist ein Knoten, li eine Liste mit Knoten
r = []
for x in li:
if x.degree == a.degree:
r.append(x)
return r
def IsomorphieSuche(a, b, traversed):
print len(traversed)
traversed.append(a)
traversed.append(b)
aAdj = a.neighbours[:]
bAdj = b.neighbours[:]
# Bereits besuchte Knoten loeschen
for x in traversed:
if x in aAdj:
aAdj.remove(x)
if x in bAdj:
bAdj.remove(x)
for testnode in aAdj:
cand = getCompatible2(testnode, bAdj)
while len(cand) != 0:
if IsomorphieSuche(testnode, cand.pop(), traversed[:]):
return True
return False
def IsomorphieTest(g1,g2):
x = g1[0]
start = [] # Liste mit zu x kompatiblen Knoten aus g2
for n in g2:
start = start + getCompatible(x, n)
while len(start) != 0:
if(IsomorphieSuche(x, start.pop(), [])):
return True
return False
## MAIN ##
g1 = []
g1.append(Node("a1"))
g1.append(Node("a2"))
g1.append(Node("a3"))
g1.append(Node("a4"))
g1.append(Node("a5"))
g1[0].add_neighbour(g1[1])
g1[0].add_neighbour(g1[2])
g1[0].add_neighbour(g1[3])
g1[1].add_neighbour(g1[0])
g1[1].add_neighbour(g1[4])
g1[1].add_neighbour(g1[2])
g1[2].add_neighbour(g1[1])
g1[2].add_neighbour(g1[0])
g1[2].add_neighbour(g1[4])
g1[2].add_neighbour(g1[3])
g1[3].add_neighbour(g1[4])
g1[3].add_neighbour(g1[0])
g1[3].add_neighbour(g1[2])
g1[4].add_neighbour(g1[3])
g1[4].add_neighbour(g1[2])
g1[4].add_neighbour(g1[1])
g2 = [Node("b1"), Node("b2"), Node("b3"), Node("b4"), Node("b5") ]
g2[0].add_neighbour(g2[1])
g2[0].add_neighbour(g2[2])
g2[0].add_neighbour(g2[3])
g2[0].add_neighbour(g2[4])
g2[1].add_neighbour(g2[0])
g2[1].add_neighbour(g2[2])
g2[1].add_neighbour(g2[4])
g2[2].add_neighbour(g2[1])
g2[2].add_neighbour(g2[0])
g2[2].add_neighbour(g2[3])
g2[3].add_neighbour(g2[4])
g2[3].add_neighbour(g2[0])
g2[3].add_neighbour(g2[2])
g2[4].add_neighbour(g2[1])
g2[4].add_neighbour(g2[0])
g2[4].add_neighbour(g2[3])
if IsomorphieTest(g1, g2):
print "Isomorph"
else:
print "Nicht isomorph"
Bei deinem dirs-Beispiel ist die Rekursion irgendwie in listdir() implementiert, wer weiß wie die Programmierprofis der Pythonimplementierung das umgesetzt haben
Also ich weiss nicht wie dies gemacht haben.
Ne, also ich verlange gar nicht von euch dass ihr meine Hausaufgaben macht! Wäre mir auch angenehmer, und sinnvoller, wenn ich selbst auf die Lösung komme. Aber ich hoffe natürlich dass ihr mir auf meinem Weg zu Erkenntnis helft.
Achso, die obigen beiden Graphen, die ich intialisiere, sind isomorph zueinander.
Verfasst: Freitag 1. April 2005, 22:45
von BlackJack
psychodad hat geschrieben:Bei deinem dirs-Beispiel ist die Rekursion irgendwie in listdir() implementiert, wer weiß wie die Programmierprofis der Pythonimplementierung das umgesetzt haben
Also ich weiss nicht wie dies gemacht haben.
`listdir()` ist nicht rekursiv. Meine Funktion heisst `dirs()` und wird in der ``for``-Schleife von mir rekursiv aufgerufen. Da haben die Python-Programmierer nichts mit zu tun.
Wie ich schon geschrieben habe fehlt auf der Webseite in der zweiten Funktion, also in der `IsomorphieSuche()`, der
Rekursionsanker! Ohne den läuft es natürlich endlos. Du musst da irgendwann mal erkennen das Du fertig bist, sonst wird die immer und immer wieder aufgerufen. Die erste print-Anweisung in der Funktion sollte Dir auch einen Anhaltspunkt geben, was die Abbruchbedingung sein könnte.
Wenn's dann läuft solltest Du wirklich die ``while``-Schleifen durch ``for``-Schleifen ersetzen. In C++ ist `List` eine verkettete Liste, da ist das `pop()` sehr schnell, aber Python-Listen sind eher so etwas wie `Vector` oder `ArrayList` in Java. Da kann `pop()` ziemlich "teuer" werden.
Und `traversed` kannst Du durch ein Set ersetzen. In Python 2.4 ist `set` ein eingebauter Datentyp, in 2.3 ist ein Modul enthalten, das man mit ``from sets import Set as set`` importieren kann. Dann geht das überprüfen ob ein `Node` schon bearbeitet wurde schneller und braucht nicht lineare Zeit wie bei der Liste. Ansonsten sieht es auf den ersten Blick ganz gut aus.
Verfasst: Samstag 2. April 2005, 18:32
von psychodad
Ich entferne doch alle bereits untersuchten Knoten
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:
Das meinst Du doch mit Rekursionsaanker?
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?
Übrigens Danke für die Hinweise für die Datentypen, dass wusste ich bisher noch nicht.