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

Beitragvon BlackJack » Donnerstag 31. März 2005, 23:06

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

Beitragvon psychodad » Freitag 1. April 2005, 18:16

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:
psychodad

Beitragvon psychodad » Freitag 1. April 2005, 18:17

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.
BlackJack

Beitragvon BlackJack » Freitag 1. April 2005, 22:45

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.
psychodad

Beitragvon psychodad » Samstag 2. April 2005, 18:32

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.
BlackJack

Beitragvon BlackJack » Samstag 2. April 2005, 22:14

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

Beitragvon psychodad » Samstag 2. April 2005, 22:51

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

Beitragvon BlackJack » Sonntag 3. April 2005, 22:10

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

Beitragvon psychodad » Montag 4. April 2005, 19:05

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

Beitragvon BlackJack » Montag 4. April 2005, 22:40

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

Re: Durch Dictionaries iterieren

Beitragvon MarcelF6 » Sonntag 18. Mai 2014, 14:40

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

Re: Durch Dictionaries iterieren

Beitragvon BlackJack » Sonntag 18. Mai 2014, 14:52

@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

Re: Durch Dictionaries iterieren

Beitragvon MarcelF6 » Montag 19. Mai 2014, 17:18

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=python file=Untitled.py]def __str__(self)[/code]
[code=python file=Untitled.py]def __repr__(self)[/code]
überschreiben einfach die "default"-string bzw. -represent-Funktionen, oder?

2.) [code=python file=Untitled.py]def _get_degree(self)[/code]
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=python file=Untitled.py] a_node = graph_a[0]
for b_node in filter(lambda node: node.degree == a_node.degree, graph_b):[/code]
D.h. : "für jeden b_node, der den gleichen Grad hat wie a_node, probiere... "

5.) [code=python file=Untitled.py]result = _iso_search(a_node, b_node, dict(), 2 * len(graph_a))
for node in graph_b:
del result[node][/code]
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=python file=Untitled.py]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):[/code]
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

Re: Durch Dictionaries iterieren

Beitragvon MarcelF6 » Montag 19. Mai 2014, 20:24

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

Re: Durch Dictionaries iterieren

Beitragvon BlackJack » Dienstag 20. Mai 2014, 20:24

@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=python file=Untitled.py]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()
[/code]

Wer ist online?

Mitglieder in diesem Forum: __deets__, Bing [Bot], Majestic-12 [Bot], Yahoo [Bot], !false