Das deutsche Python-Forum

Hallo zusammen,

ich beschäftige mich zur Zeit ein bischen mit Graphen-Theorie und Such-Algorithmen. Ich wollte eine Tiefensuche implementieren. Diese läuft auch direkt, doch wenn ich mir das passende Objekt in der Funktion zurückgeben lasse herhalte ich immer den Type None. Ich kann mir gut vorstellen, dass es was mit der Referenzierung von dem Objekt "Node" zu tun hat.

Code: Alles auswählen

class Node(object):
    def __init__(self,x,y,wert):
        self.x = x
        self.y = y
        self.wert = wert
        self.nachbar = []

        
    def __str__(self):
        string = "(%d,%d) = %d \n" % (self.x,self.y,self.wert)
        return string

    def add_nachbar(self,node):
        self.nachbar.append(node)

    def expand(self):
        return self.nachbar


def dfs(node,goal):
    print("Node-DFS",node,"GOAL:",goal,"Node.wert:",node.wert)
    if(node.wert == goal):
        print("in der If",node)
        return node
    else:
        stack = node.expand()
        while len(stack) != 0:
            node1 = stack.pop()
            print("Node1-DFS",node1)
            dfs(node1,goal)


root = Node(0,0,100)
n1 = Node(1,0,101)
n2 = Node(0,1,102)
n3 = Node(1,1,103)
print(root,n1,n2,n3)

root.add_nachbar(n1)
root.add_nachbar(n2)
n2.add_nachbar(n3)


print("Gefunder Node:",dfs(root,101))

Für einen Tipp wo mein Fehler liegt, wäre ich sehr dankbar.

Gruß Leus.

P.S.: Das Beispiel ist mit Python 3.1 geschrieben und die print-Anweisungen dienen mir als Debug-Hilfe.

Im else-Zweig gibst du nie etwas zurück.

Vielen Dank und da war auch mein Fehler. Eine kleine Änderung und schon war das Problem gelöst.

Code: Alles auswählen

       while len(stack) != 0:
            node1 = stack.pop()
            print("Node1-DFS",node1)
            return dfs(node1,goal)

Ich hatte in der while-Schleife ein return vergessen.

Es sei kurz noch der ein oder andere Hinweis erlaubt

Ist es Absicht, dass Du die Struktur des Graphen "zerstörst"? Lass Dir mal die Nachbarn der Knoten des Graphen nach einem Suchdurchlauf anzeigen

Kleiner Tipp:

Code: Alles auswählen

In [31]: a = range(5)

In [32]: a
Out[32]: [0, 1, 2, 3, 4]

In [33]: b = a

In [34]: b
Out[34]: [0, 1, 2, 3, 4]

In [35]: b.pop()
Out[35]: 4

In [36]: b
Out[36]: [0, 1, 2, 3]

In [37]: a
Out[37]: [0, 1, 2, 3]

Ich würde wohl die Knoten, die schon besucht wurden in eine Liste aufnehmen oder "markieren", also z.B. ein Attribut "visited" im Knoten auf True / False setzen. Vor einem erneuten Suchlauf kann man diese dann einfach wieder resetten.

expand() kannst Du Dir sparen; in Python braucht man keine getter und setter-Methoden, wenn man nur auf ein Attribut zugreifen will, ohne besondere Tests oder Logik. Sollte das der Fall sein, so nutzt man dafür Properties.

Über add_nachbar() kann man streiten. Ich würde mir die Methode wohl erst einmal sparen.

"string" als Name überschreibt ein Modul aus der Standard-Lib, namens "string". So etwas solltest Du vermeiden. In diesem Falle ist das besonders einfach, weil Du Dir das Binden an einen Namen sparen kannst und den String direkt zurückgeben kannst:

Code: Alles auswählen

def __str__(self):
        return "(%d,%d) = %d \n" % (self.x,self.y,self.wert)

Das nur als kurze Tipps / Anmerkungen. Viel Erfolg weiterhin

@leus: Jetzt solltest Du aus dem ``while`` noch ein ``if`` machen -- sonst denkt noch jemand das sei eine Schleife.

Hyperion hat geschrieben:expand() kannst Du Dir sparen; in Python braucht man keine getter und setter-Methoden, wenn man nur auf ein Attribut zugreifen will, ohne besondere Tests oder Logik. Sollte das der Fall sein, so nutzt man dafür Properties.

Nein kann er nicht, sowas nennt man eine Schnittstelle. Was ist, wenn er auf einmal einen Binärbaum implementieren will mit left und right Attribut? Klar kann man da jetzt eine property nehmen, aber wozu? Um sich die Klammer zu sparen?

Über add_nachbar() kann man streiten. Ich würde mir die Methode wohl erst einmal sparen.

Nein kann man nicht. Die gehört da hin.

Da schafft es mal jemand ein vernünftiges Interface für seine Klassen zu erstellen und schon wird das in Simplifizierungseifer zerredet. War mir klar, das von irgendwem so ein Kommentar kommen musste. :/

Guten Morgen zusammen,

ich weiss, dass man bei Python keine setter und getter funktion braucht, aber die funktion add_nachbar soll noch erweitert werden indem nur noch über den root-Knoten die anderen Knoten eingefügt werden.

Bin ich eigentlich der einzige der bei ``add_nachbar`` innerlich zusammenzuckt? Zudem alle anderen Namen durchgehend englisch sind?

Leonidas hat geschrieben:Bin ich eigentlich der einzige der bei ``add_nachbar`` innerlich zusammenzuckt? Zudem alle anderen Namen durchgehend englisch sind?

Nein. Wobei mich schon die Existenz der Methode schon verwundert hat. Ist `nachbar` kein Teil der öffentlichen API? Wieso sind die Nachbaren unter `nachbar` zu finden und wieso gibt `expand` eine interne(?) Datenstruktur zurück? Desweiteren sollte `dfs` imho eine Methode von `Node` sein.

So habe jetzt das Problem gelöst, es lag noch ein zweiter Fehler in meiner Denkweise.

@Hyperion: Nein es war nicht die Absicht, dass die Struktur zerstört wird. Dies habe ich per Slice gelöst. Die Idee Knoten, die schon besucht wurden zumarkieren iat gut, da ich vielleicht später nicht nur Bäume sondern auch geschlossene Graphen betrachte.

@BlackJack: Es muss sogar eine Schleife sein. Denn wäre es keine Schleife würde immer nur ein Nachbar untersucht werden, und ein Knoten kann mehre Nachbarn haben:

Hier nochmal eine Überarbeitete Version:

Code: Alles auswählen

class Node(object):
    def __init__(self,x,y,wert):
        self.x = x
        self.y = y
        self.wert = wert
        self.neighbor = []

        
    def __str__(self):
        return "(%d,%d, %d) = %d \n" % (self.x,self.y,len(self.neighbor),self.wert)
        

    def add_neighbor(self,node):
        self.neighbor.append(node)

    def expand(self):
        return self.neighbor[:]



def dfs(node,goal):

    if(node.wert == goal):

        return node
    else:
        stack = node.expand()
        while len(stack) != 0:
            node1 = stack.pop()

            tmp =  dfs(node1,goal)
            if(tmp != None):
                return tmp


root = Node(0,0,100)
n1 = Node(1,0,101)
n2 = Node(0,1,102)
n3 = Node(1,1,103)


root.add_neighbor(n1)
root.add_neighbor(n2)
n2.add_neighbor(n3)



print("Gefunder Node:",dfs(root,104))

Wenn du vorhast bei der rekursiven Variante zu bleiben (schlechte Idee mit Python), kannst du dfs so umschreiben:

Code: Alles auswählen

 def dfs(node,goal):
    if node.wert == goal:
        return node
    for neighbor in node.expand():
        tmp =  dfs(node1,goal)
        if tmp is not None:
            return tmp

Das hat auch den Vorteil, dass du hier nicht die Struktur veraenderst und in `Node.expand` keine Kopie zurueckgeben muesstest.

Und lass die Klammern bei `if` weg, die sind unnoetig und halten boese Ueberaschungen bereit.

Darii hat geschrieben:
Hyperion hat geschrieben:expand() kannst Du Dir sparen; in Python braucht man keine getter und setter-Methoden, wenn man nur auf ein Attribut zugreifen will, ohne besondere Tests oder Logik. Sollte das der Fall sein, so nutzt man dafür Properties.
Nein kann er nicht, sowas nennt man eine Schnittstelle. Was ist, wenn er auf einmal einen Binärbaum implementieren will mit left und right Attribut? Klar kann man da jetzt eine property nehmen, aber wozu? Um sich die Klammer zu sparen?

Und wie setzt Du dann "right" und "left" ohne API-Änderung? Wie unterscheidet man dann "right" oder "left"? Wenn man es nicht unterscheiden kann, dann ist es doch nur ein Baum mit maximal zwei Nachbarn. Und wenn Du das im Hintergrund prüfen willst, dann führt der Weg doch eh wieder über eine Property. Ich sehe da jetzt kein Problem.

Und wenn Du von Node erbst und die Klasse erweiterst und modifizierst, so erbst Du ja ein Attribut wie "neighbours" eh mit.

Zudem habe ich doch auf die evtl. noch fehlende Logik hingewiesen und der OP hat das dann ja auch bestätigt, dass da noch was kommt.

Und ganz zum Schluss: Wie oft sehen wir hier Code von Leuten, die sich über das Problem getter / setter in Python nicht bewusst sind, weil sie es von Java o.ä. kennen bzw. von den Herren Ernesti und Kaiser so gelernt haben? Da ist ein Hinweis diesbezüglich doch wohl gestattet.

cofi hat geschrieben:Wenn du vorhast bei der rekursiven Variante zu bleiben (schlechte Idee mit Python), ...

Inwiefern schlechte Idee? Ist Rekursion in Python denn verpönt?

Code: Alles auswählen

        tmp =  dfs(node1,goal)
        # if tmp is not None:
        # ist das nicht einfacher? ;-)
        if tmp:
            return tmp

@leus: Die ``while``-Schleife auf die ich mich bezog, war keine echte Schleife, die war wirklich nur ein umständlich geschriebenes ``if``.

Jetzt hast Du `nachbar` übersetzt, aber immer noch ein `wert`-Attribut. Und `neigbor` sollte besser `neigbors` heissen, denn es ist ja nicht ein einzelner Nachbar, der sich hinter diesem Namen verbirgt. Statt "slicing" würde ich in `expand()` übrigens `list()` verwenden -- das funktioniert mit mehr Datentypen als ``[:]``.

Du nutzt in `dfs()` das implizite ``return None`` was IMHO unschön ist.

@Hyperion: Spätestens wenn der Baum oder Graph gross genug wird, dass man das Rekursionslimit trifft, dann muss man eine nicht-rekursive Implementierung schreiben.

Ich würde auch explizit auf `None` prüfen, denn sonst prüft man ja den Wahrheitswert eines `Node`-Objektes. *Das* möchte man ja aber vielleicht irgendwann mit einer eigenen Semantik überladen wann ein Node "wahr" oder "falsch" ist. Man könnte sich alternativ auch überlegen, ob man statt `None` als speziellem Rückgabewert nicht mit einer `NodeNotFound`-Ausnahme arbeiten möchte.

Hyperion hat geschrieben:
cofi hat geschrieben:Wenn du vorhast bei der rekursiven Variante zu bleiben (schlechte Idee mit Python), ...
Inwiefern schlechte Idee? Ist Rekursion in Python denn verpönt?

Zusaetzlich zum von BlackJack erwaehnten Rekursionslimit kommen die relativ teuren Funktionsaufrufe dazu, da ist man einfach mit einer Queue und einer Schleife besser dran.

Hyperion hat geschrieben:Und wie setzt Du dann "right" und "left" ohne API-Änderung? Wie unterscheidet man dann "right" oder "left"?

Gar nicht. Das erstellen des Baumes ist Baumspezifisch und nichts was sich verschiedene Baumtypen teilen sollten. Die Suche hingegen kann man aber generalisieren.

Und wenn Du von Node erbst und die Klasse erweiterst und modifizierst, so erbst Du ja ein Attribut wie "neighbours" eh mit.

Wie du gerade selbst schön ausgeführt hast hätte neighbours in Node nichts zu suchen, weil eine hypotetische Subklasse BinaryTreeNode damit rein gar nichts anfangen könnte (außer eine readonly-Property draus zu machen dann bricht man aber mit dem obj.neighbours.append-Interface das vorher funktionierte).

Zudem habe ich doch auf die evtl. noch fehlende Logik hingewiesen und der OP hat das dann ja auch bestätigt, dass da noch was kommt.

Völlig unerheblich. Man verändert keine internen Datenstrukturen von irgendwelchen Klassen. obj.neighbours.append(child) statt obj.add_neighbour(child) ist einfach schlechter Stil. Selbst wenn add_child selbst nichts anderes macht.

Darii hat geschrieben:
Hyperion hat geschrieben:Und wie setzt Du dann "right" und "left" ohne API-Änderung? Wie unterscheidet man dann "right" oder "left"?
Gar nicht. Das erstellen des Baumes ist Baumspezifisch und nichts was sich verschiedene Baumtypen teilen sollten. Die Suche hingegen kann man aber generalisieren.

Ja eben weil man das kann, bietet sich doch eine (read-only)-Property an! Das erstellen hat doch mit der Suche eh nichts zu tun. Und genau deswegen ist es doch für die Suche unerheblich, ob ich direkt ein neighbours-Attribut oder zwei separate Attribute right / left ändern kann. Mit einer Property, die mir die Nachbarn zurückliefert, ist die Suche doch dann genau unabhängig von der Implementierung eines Nodes.

Darii hat geschrieben:
Und wenn Du von Node erbst und die Klasse erweiterst und modifizierst, so erbst Du ja ein Attribut wie "neighbours" eh mit.
Wie du gerade selbst schön ausgeführt hast hätte neighbours in Node nichts zu suchen, weil eine hypotetische Subklasse BinaryTreeNode damit rein gar nichts anfangen könnte (außer eine readonly-Property draus zu machen dann bricht man aber mit dem obj.neighbours.append-Interface das vorher funktionierte).

Mit dem bisherigen add_neighbour geht das doch auch nicht! Wenn Du intern zwei neue Attribute einführst, müssen die doch nach außen auch zu benutzen sein.

Auf der einen Seite forderst Du Kapselungen fürs Setzen und Abfragen von Nachbarn, auf der anderen Seite stellst Du dann die Generalisierung dafür selber in Frage. Wie solls denn nun aussehen?

Darii hat geschrieben:Wie du gerade selbst schön ausgeführt hast hätte neighbours in Node nichts zu suchen, weil eine hypotetische Subklasse BinaryTreeNode damit rein gar nichts anfangen könnte (außer eine readonly-Property draus zu machen dann bricht man aber mit dem obj.neighbours.append-Interface das vorher funktionierte).
Mit dem bisherigen add_neighbour geht das doch auch nicht!

Hab ich das behauptet? Du willst doch neighbours vererben lassen. Das würde ein vorhandenes Interface brechen. add_neighbours hat da selbstverständlich genauso wenig was zu suchen.

Auf der einen Seite forderst Du Kapselungen fürs Setzen und Abfragen von Nachbarn, auf der anderen Seite stellst Du dann die Generalisierung dafür selber in Frage

Lies mal aufmerksam meine Posts, ich fordere nur eine Generalisierung für das Abfragen. Für das Setzten macht das wenig Sinn, was aber nichts daran ändert, dass das direkte Manipulieren einer evtl. vorhandenen neighbours-Liste eine schlechte Idee ist. Wenn man dann nämlich irgendwann noch Logik hinzufügen will oder die Art der Datenspeicherung ändern will hat man ein Problem.

Vielleicht mal zur Illustration:

Code: Alles auswählen

class TreeNode(object):
    def __init__(self, payload):
        self.payload = payload
        
    def expand(self):
        raise NotImplementedError
        
    def __repr__(self):
        return str(self)
        
    def __str__(self):
        return "<%s %s -> %s>" % (type(self).__name__, self.payload, self.expand())

class GenericTreeNode(TreeNode):
    def __init__(self, payload, children=None):
        TreeNode.__init__(self, payload)
        self._children = children[:] if children else []
    
    def expand(self):
        return self._children
    
    def add_child(self, child):
        self._children.append(child)
    
class BinaryTreeNode(TreeNode):
    def __init__(self, payload, left=None, right=None):
        TreeNode.__init__(self, payload)
        self.left = left
        self.right = right
        
    def expand(self):
        return filter(bool, [self.left, self.right])

def search_tree(node, payload):
    for node in node.expand():
        if node.payload == payload:
            return node
        else:
            return search_tree(node, payload)

tree = GenericTreeNode(2, [GenericTreeNode(4), GenericTreeNode(7)])
tree2 = BinaryTreeNode(2, BinaryTreeNode(4), BinaryTreeNode(7))
print search_tree(tree, 4)
print search_tree(tree2, 4)

search_tree funktioniert in beiden Fällen.

Das deutsche Python-Forum

Problem mit Rückgabe von Objekten in Rekusiven Funktionen

Problem mit Rückgabe von Objekten in Rekusiven Funktionen

Re: Problem mit Rückgabe von Objekten in Rekusiven Funktione

Re: Problem mit Rückgabe von Objekten in Rekusiven Funktione

Re: Problem mit Rückgabe von Objekten in Rekusiven Funktione

Re: Problem mit Rückgabe von Objekten in Rekusiven Funktione

Re: Problem mit Rückgabe von Objekten in Rekusiven Funktione

Re: Problem mit Rückgabe von Objekten in Rekusiven Funktione

Re: Problem mit Rückgabe von Objekten in Rekusiven Funktione

Re: Problem mit Rückgabe von Objekten in Rekusiven Funktione

Re: Problem mit Rückgabe von Objekten in Rekusiven Funktione

Re: Problem mit Rückgabe von Objekten in Rekusiven Funktione

Re: Problem mit Rückgabe von Objekten in Rekusiven Funktione

Re: Problem mit Rückgabe von Objekten in Rekusiven Funktione

Re: Problem mit Rückgabe von Objekten in Rekusiven Funktione

Re: Problem mit Rückgabe von Objekten in Rekusiven Funktione

Re: Problem mit Rückgabe von Objekten in Rekusiven Funktione

Re: Problem mit Rückgabe von Objekten in Rekusiven Funktione

Re: Problem mit Rückgabe von Objekten in Rekusiven Funktione