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.
Antworten
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)
Nach oben
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. :roll:
Nach oben
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. :roll:

Achso, die obigen beiden Graphen, die ich intialisiere, sind isomorph zueinander.
Nach oben
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.
Nach oben
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.
Nach oben
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.
Nach oben
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!
Nach oben
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
Nach oben
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.
Nach oben
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.
Nach oben
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. :)
Nach oben
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.
Nach oben
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
Nach oben
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?
Nach oben
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()
Nach oben
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²) ?
Nach oben
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.
Nach oben
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.
Nach oben
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?
Nach oben
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.
Nach oben
Antworten

Zurück zu „Allgemeine Fragen“