Durch Dictionaries iterieren

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
BlackJack

psychodad hat geschrieben: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?
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!

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. :-)
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
Stimmt sollte man nicht. Aber warum veränderst Du die Liste in der Schleife?

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
Noch eine Bemerkung zu den `getCompatible()` Funktionen. Da machst Du etwas, das man in Python typischerweise mit "list comprehensions" ausdrückt. Folgendes ist äquivalent:

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)]
Wobei `pred()` eine Funktion oder ein Ausdruck ist, der einen Wahrheitswert liefert. Eine der beiden Funktionen/Ausdrücke kann man auch weglassen. Eigenlich auch beide, aber eine Kopie kann man auch mit `list()` anlegen.
psychodad

Code: Alles auswählen

def IsomorphieSuche(a, b, traversed):
 if len(traversed) == 10:
  return True
Yeah! Jetzt geht's :lol:

Ja, stimmt, dass mit den while's ist eigentlich viel simpler mit for's :oops:
Noch eine Bemerkung zu den `getCompatible()` Funktionen. Da machst Du etwas, das man in Python typischerweise mit "list comprehensions" ausdrückt.
Ja, das mit den "comprehensions" sieht schon eleganter aus (und ist bestimmt auch schneller), hab bisher nur C++ programmiert, mit Python schaue ich das erste mal sozusagen über den Tellerrand. Solche abgefahrenen Kontrukte sind mir da noch ein bissl fremd. :roll:

Achso, ich wäre jetzt auch mal ganz neugierig wie Du das programmiert hast, mein Code läuft ja jetzt, und das Prinzip habe ich soweit verstanden.

Danke, Stefan!
BlackJack

Ich habe noch ein paar Tests eingebaut bevor die rekursive Funktion aufgerufen wird -- ob beide Graphen die gleiche Anzahl von Knoten und Kanten haben zum Beispiel. Und weil eine konkrete Lösung zurückgegeben wird, gibt's eine Ausnahme für den Fall, das es keine Lösung gibt.

Code: Alles auswählen

from sets import Set as set

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)


class NoIsomorphismFound(Exception): pass


def sorted_degree_list(nodes):
    result = [node.degree for node in nodes]
    result.sort()
    return result


def find_isomorphism(graph_a, graph_b):
    if len(graph_a) != len(graph_b):
        raise NoIsomorphismFound('graphs have different number of nodes')
    if len(graph_a) == 0:
        raise NoIsomorphismFound('no nodes in graphs')
    if sorted_degree_list(graph_a) != sorted_degree_list(graph_b):
        raise NoIsomorphismFound('degrees of the nodes do not match')
    if set(graph_a) & set(graph_b):
        raise ValueError('nodes of graphs are not disjoint')
    
    a_node = graph_a[0]
    for b_node in filter(lambda node: node.degree == a_node.degree, graph_b):
        try:
            result = _iso_search(a_node, b_node, dict(), 2 * len(graph_a))
            for node in graph_b:
                del result[node]
            return result
        except NoIsomorphismFound:
            pass
    
    raise NoIsomorphismFound('graphs are not isomorph')


def _iso_search(a_node, b_node, solution, total_node_count):
    solution[a_node] = b_node
    solution[b_node] = a_node
    
    if len(solution) == total_node_count:
        return solution
    
    for a_neighbour in filter(lambda x: x not in solution, a_node.neighbours):
        for b_neighbour in filter(lambda x: x not in solution
                                            and x.degree == a_neighbour.degree,
                                  b_node.neighbours):
            return _iso_search(a_neighbour, b_neighbour, dict(solution),
                               total_node_count)

    raise NoIsomorphismFound()


def make_graph(name, adjacents):
    nodes = [Node(name + str(i+1)) for i in xrange(len(adjacents))]
    for (i, neighbours) in enumerate(adjacents):
        node = nodes[i]
        for neighbour in neighbours:
            node.add_neighbour(nodes[neighbour])
    return nodes


g1 = make_graph('a', ((1,2,3), (0,4,2), (1,0,4,3), (4,0,2), (3,2,1)))
g2 = make_graph('b', ((1,2,3,4), (0,2,4), (1,0,3), (4,0,2), (1,0,3)))

for nodes in find_isomorphism(g1, g2).iteritems():
    print '%s -> %s' % nodes
psychodad

Schön kurz, mein C++ Programm war viermal so lang.

Aber warum setzt Du Exceptions zur Steuerung des Programmflusses ein. Ist das unter Python gängige Praxis? Also ich habe gelernt dass man Exceptions nur bei Fehlern wirft, also wenn zum normalen Programmfluss eine Ausnahme vorliegt. Aber das zwei Graphen nicht isomorph sind ist doch kein Fehler, dass will ich ja testen.
BlackJack

Ich teste ja nicht, ob die Graphen isomorph sind oder nicht, sondern möchte gerne eine konkrete Lösung, also eine Abbildung von dem einen Graphen in den anderen haben. Dann stellt sich die Frage was passieren soll, wenn die beiden Graphen gar nicht isomorph sind. In dem Fall kann ich keine Lösung zurückgeben. Ohne Ausnahme könnte ich höchstens eine "spezielle" Abbildung, wie zum Beispiel ein leeres Dictionary als "Fehlercode" liefern. Aber genau um so etwas zu vermeiden sind Ausnahmen da.

Generell ist eine Ausnahme eine Situation, die irgendwie vom Regelfall abweicht. Das muss nicht zwingend ein Fehler sein! Das gilt eigentlich für alle Programmiersprachen. Und in Python werden sie häufiger verwendet als in C++ oder Java.

In C++ und Java ist die Ausnahmebehandlung auch ziemlich "teuer" was Rechenzeit angeht. In Python ist der Unterschied zwischen einem Funktionsaufruf und einer Ausnahmebehandlung nicht so gross.

Schau Die mal im Glossar zum Tutorial die Erklärungen der Begriffe/Abkürzungen `EAFP` und `LBYL` an.
MarcelF6
User
Beiträge: 226
Registriert: Samstag 3. März 2012, 21:30

Hallo BlackJack,

dein Beitrag hier ist zwar schon etwas älter, trotzdem hätte ich noch eine Frage dazu.
Am Schluss des Codes erzeugst du ja zwei Beispielgraphen. Ich verstehe die Notation allerdings nicht ganz.
Wenn du den ersten Graphen erzeugst, "g1 = make_graph('a', ((1,2,3), (0,4,2), (1,0,4,3), (4,0,2), (3,2,1)))", was meint dann (1,2,3)? Ich hätte es so interpretiert, dass der nullte 'node' verbunden ist mit dem ersten, dem zweiten und dem dritten. Das kann so aber nicht stimmen, sonst dürften die beiden Beispielgraphen nicht isomorph sein...

Danke für die Aufklärung. :)
BlackJack

@MarcelF6: Du interpretierst die Adjazenzlisten richtig. Wieso dürften die dann nicht Isomorph sein? Da wird ja eine Abbildung von Knoten aus Graph a zu Knoten aus Graph b ausgegeben. Kannst Dir die beiden Graphen ja mal aufzeichnen.
MarcelF6
User
Beiträge: 226
Registriert: Samstag 3. März 2012, 21:30

Hallo BlackJack,

du hast recht! ...man muss sich die Graphen halt auch noch richtig aufzeichnen. ;-)

Ich hätte noch einige Detail-Fragen zum Code (bzw.: stimmen die folgenden Aussagen?):

1.) Die beiden Funktionen:

Code: Alles auswählen

def __str__(self)

Code: Alles auswählen

def __repr__(self)
überschreiben einfach die "default"-string bzw. -represent-Funktionen, oder?

2.)

Code: Alles auswählen

def _get_degree(self)
Gibt den Grad eines Knotens zurück, oder? D.h. wenn ein Knoten mit zwei anderen verbunden ist --> degree = 2.

3.) Zu den Graphen allgemein: Diese werden hier als ungerichtet betrachtet, nicht wahr? Daher die Funktion "def add_neighbour", welche besagt, dass wenn z.B. Knoten 2 mit Knoten 4 verbunden ist, dann auch gilt, dass Knoten 4 mit Knoten 2 verbunden ist.

4.)

Code: Alles auswählen

    a_node = graph_a[0]
    for b_node in filter(lambda node: node.degree == a_node.degree, graph_b):
D.h. : "für jeden b_node, der den gleichen Grad hat wie a_node, probiere... "

5.)

Code: Alles auswählen

result = _iso_search(a_node, b_node, dict(), 2 * len(graph_a))
            for node in graph_b:
                del result[node]
D.h.: Wir rufen die rekursive Funktion auf, übergeben ihr den Knoten von a, von b, ein leeres dict, und die Gesamtanzahl Knoten (von beiden Graphen).
Danach löschen wir jeden bearbeiteten Knoten aus Graph B.

6.)

Code: Alles auswählen

for a_neighbour in filter(lambda x: x not in solution, a_node.neighbours):
        for b_neighbour in filter(lambda x: x not in solution
                                            and x.degree == a_neighbour.degree,
                                  b_node.neighbours):
D.h.: "Für jeden Nachbarn von A, der nicht schon gefunden wurde UND für jeden Nachbarn von B, der nicht schon gefunden wurde und wenn der Grad des gefundenen Knotens == demjenigen des Nachbarn von A ist, dann wird die rekursive Funktion nochmals aufgerufen, wobei das dict eine Lösung mehr enthält."

Herzlichen Dank für die Hilfe,
Marcel
MarcelF6
User
Beiträge: 226
Registriert: Samstag 3. März 2012, 21:30

PS: Oder, vielleicht etwas anders gefragt: Was ist der hier verwendete (in natürlicher Sprache ausgedrückte) Algorithmus, um isomorphe Graphen zu finden?
BlackJack

@MarcelF6: Die Beschreibungen 1-6 stimmen soweit. Das ist halt grundsätzlich eine ganz normale rekursive Suche. Paare einen Knoten aus a mit einem passenden aus b und probiere dann rekursiv ob man die restlichen Knoten auch noch paaren kann.

Da der Code ja schon fast 10 Jahre alt ist, hier mal etwas aufpoliert:

Code: Alles auswählen

class Node(object):
    def __init__(self, name):
        self.name = name
        self.neighbours = set()
   
    def __str__(self):
        return self.name
   
    def __repr__(self):
        return '<{0.__class__.__name__} {0.name!r} at 0x{1:x}>'.format(
            self, id(self)
        )
    
    def __cmp__(self, other):
        return cmp(self.name, other.name)

    def __hash__(self):
        return hash(self.name)

    @property
    def degree(self):
        return len(self.neighbours)
   
    def add_neighbour(self, other):
        self.neighbours.add(other)
        other.neighbours.add(self)
 
 
class NoIsomorphismFound(Exception):
    pass
 
 
def sorted_degree_list(nodes):
    return sorted(node.degree for node in nodes)
 
 
def find_isomorphism(graph_a, graph_b):
    if len(graph_a) != len(graph_b):
        raise NoIsomorphismFound('graphs have different number of nodes')
    if len(graph_a) == 0:
        raise NoIsomorphismFound('no nodes in graphs')
    if sorted_degree_list(graph_a) != sorted_degree_list(graph_b):
        raise NoIsomorphismFound('degrees of the nodes do not match')
    if set(graph_a) & set(graph_b):
        raise ValueError('nodes of graphs are not disjoint')
   
    a_node = graph_a[0]
    for b_node in (n for n in graph_b if n.degree == a_node.degree):
        try:
            result = _iso_search(a_node, b_node, dict(), 2 * len(graph_a))
            for node in graph_b:
                del result[node]
            return result
        except NoIsomorphismFound:
            pass
   
    raise NoIsomorphismFound('graphs are not isomorph')
 
 
def _iso_search(a_node, b_node, solution, total_node_count):
    solution[a_node] = b_node
    solution[b_node] = a_node
   
    if len(solution) == total_node_count:
        return solution
    for a_neighbour in (n for n in a_node.neighbours if n not in solution):
        for b_neighbour in (
            n for n in b_node.neighbours
            if n not in solution and n.degree == a_neighbour.degree
        ):
            return _iso_search(
                a_neighbour, b_neighbour, dict(solution), total_node_count
            )
 
    raise NoIsomorphismFound()
 
 
def make_graph(name, adjacents):
    nodes = [Node(name + str(i)) for i in xrange(len(adjacents))]
    for i, neighbours in enumerate(adjacents):
        node = nodes[i]
        for neighbour in neighbours:
            node.add_neighbour(nodes[neighbour])
    return nodes


def main():
    graph_a = make_graph(
        'a', ((1, 2, 3), (0, 4, 2), (1, 0, 4, 3), (4, 0, 2), (3, 2, 1))
    )
    graph_b = make_graph(
        'b', ((1, 2, 3, 4), (0, 2, 4), (1, 0, 3), (4, 0, 2), (1, 0, 3))
    )
    mapping = find_isomorphism(graph_a, graph_b)
    for node_a, node_b in sorted(mapping.viewitems()):
        print '{0} -> {1}'.format(node_a, node_b)


if __name__ == '__main__':
    main()
MarcelF6
User
Beiträge: 226
Registriert: Samstag 3. März 2012, 21:30

Vielen Dank, BlackJack! :)

Also, damit ich den Algorithmus richtig verstehe. Du gehst also wie folgt vor, oder?
1.) Du nimmst einen Knoten, sagen wir a0.
2.) Du schaust, wie viele Kanten von diesem Knoten aus gehen und versuchst, im zweiten Graphen ebenfalls ein solcher Knoten zu finden.
3.) a) Falls ein solcher gefunden wurde, wiederhole 1.-3. mit dem nächsten Knoten von Graph A.
b) falls keine Entsprechung gefunden wurde --> kein Isomorphismus
c) falls alle Knoten behandelt wurden --> Isomorphismus und fertig.

Ah, und: Wie sieht das mit der Komplexität aus?
Wir haben ja einmal 2x for-Schleifen, d.h. O(n²) ?
BlackJack

@MarcelF6: Nein das ist zu einfach gedacht. Da könnte man die Knoten von beiden Graphen ja auch einfach nach Grad sortieren und dann linear, paarweise vergleichen ob die den gleichen Grad haben. Die Struktur des Graphen muss ja übereinstimmen. Also der Grad von zwei Knoten, *und* dann müssen noch die Grade von allen Nachbarknoten, und deren Nachbarknoten, usw. übereinstimmen. Das ist dann der rekursive Algorithmus.
EyDu
User
Beiträge: 4881
Registriert: Donnerstag 20. Juli 2006, 23:06
Wohnort: Berlin

Wenn BlackJack eine Lösung in O(n²) gefunden hätte, dann hätte er vor lauter Vorträgen hier sicher keine Zeit zu schreiben. Das Isomorphieproblem ist NP-vollständig. Der bisher beste gefundene Algorithmus hat eine Komplexität von O(2^sqrt(n log n)).
Das Leben ist wie ein Tennisball.
MarcelF6
User
Beiträge: 226
Registriert: Samstag 3. März 2012, 21:30

@BlackJack: Ah ok, jetzt ist's klar. :)
Vielen Dank!

@EyDu & BlackJack:
Ja stimmt, das habe ich gelesen.
Aber kann man die Komplexität dieses Algorithmus hier nicht abschätzen?
EyDu
User
Beiträge: 4881
Registriert: Donnerstag 20. Juli 2006, 23:06
Wohnort: Berlin

MarcelF6 hat geschrieben:Aber kann man die Komplexität dieses Algorithmus hier nicht abschätzen?
Das bekommst du selbst hin. Überlege dir mal, wie die schlimmsten zu testenden Graphen aussehen und was dann passieren muss.
Das Leben ist wie ein Tennisball.
MarcelF6
User
Beiträge: 226
Registriert: Samstag 3. März 2012, 21:30

Ich bin nicht sicher, ob das stimmt. Ich würde aber sagen, dass:
Der schlimmste zu testende Graph hat bei jedem Knoten gleich viele Kanten. Dann gilt für die Rekursion nämlich T(n) = T(n²-1)+T(n²-2)+1, also T(n) = O(2^(n^2)).

Kann das sein?

Übrigens: Weisst du, ob igraph in python (man kann das Modul ja importieren) O(2^sqrt(n log n)) erreicht?
MarcelF6
User
Beiträge: 226
Registriert: Samstag 3. März 2012, 21:30

Nochmals zum Algorithmus. Dieser hier wäre also korrekt, oder?
1.) Finde 2 Knoten mit demselben Grad.
2.) Stimmen die Grade der Nachbarsknoten überein?
3.) A) falls ja: wiederhole Schritt 2 mit den nächsten Nachbarsknoten
B) falls nein: kein Isomorphismus!
C) falls alle Knoten bearbeitet: Isomorphismus! :)
BlackJack

@MarcelF6: Für meinen Geschmack ist das noch zu schwammig und missverständlich formuliert. Ich glaube danach könnte niemand den Algorithmus implementieren, oder zumindest nur zufällig richtig.

Ich würde ja versuchen das als Pseudocode zu beschreiben und es auch in zwei Teilalgorithmen zu machen, so wie das ja auch umgesetzt ist. Also erst beschreiben was `_iso_search()` macht, und dann die man das benutzen kann um einen Isomorphismus zu finden. Bei der Beschreibung kann man sich auch etwas von der konkreten Umsetzung entfernen, denn was da zur Lösung hinzugefügt wird, ist semantisch ja auch etwas an anderer Stelle ”wegnehmen” oder ”verschieben”, das mache ich in der Implementierung nur deswegen nicht, weil ich die Graphdatenstrukturen nicht zerstören möchte. Das wäre irgendwie eine unschöne API.
MarcelF6
User
Beiträge: 226
Registriert: Samstag 3. März 2012, 21:30

Ok, dann würde ich den Algorithmus so beschreiben (was nicht 1:1 der eigentlichen Implementierung entspricht, aber das muss ja nicht zwingend sein):

Der Isomorphismus-Check ist in zwei Teile aufgeteilt:
- find_isomorphismus:
Hier werden alle Fälle ausgeschlossen, bei welchen kein Isomorphismus vorliegen kann. D.h. es wird geprüft, ob bei beiden Graphen dieselbe Anzahl an Knoten und dieselbe Anzahl an Kanten vorliget. D.h. also, dass geprüft wird, ob eine Bijektion vorliegt.

- iso_search:
Hier wird versucht, die Knoten des einen Graphen jenen des anderen zuzuordnen. Das geschieht aber nur, wenn jeweils beide Knoten denselben Eingangs- und Ausgangsgrad haben.

Ausserdem fällt mir gerade auf, dass die Komplexität im schlechtesten Fall O((n+1)!) Zeit und O(n²) Platz benötigen würde...
EyDu
User
Beiträge: 4881
Registriert: Donnerstag 20. Juli 2006, 23:06
Wohnort: Berlin

MarcelF6 hat geschrieben:Ausserdem fällt mir gerade auf, dass die Komplexität im schlechtesten Fall O((n+1)!) Zeit und O(n²) Platz benötigen würde...
Genau, es liegt irgendwo bei O(n!), auf die Faktoren und Summanden um das n kommt es dabei nicht drauf an. Wenn alle Knoten gleich wären, würde man die Isomorphie sofort erkennen, da immer der erste Knoten matcht. "Nächstbester" Fall wäre also, dass immer genau zwei Knoten die gleiche Anzahl an Kanten haben, dann landet man bei O((0.5*n)!), darauf kommt es dann aber auch nicht mehr an.
MarcelF6 hat geschrieben:Übrigens: Weisst du, ob igraph in python (man kann das Modul ja importieren) O(2^sqrt(n log n)) erreicht?
Ich kenne die Umsetzung in O(2^sqrt(n log n)) nicht, aber die Komplexität ist in der Praxis nicht immer relevant. Bestest beispiel dafür ist lineare Optimierung. Das Simplex-Verfahren hat auch eine exponentielle Laufzeit, ist den bekannten Verfahren in polynomialer Laufzeit aber deutlich überlegen.
Das Leben ist wie ein Tennisball.
Antworten