Hierarchie-Traversal und Vergleich Module für Python?

Question

Ich habe mit vielen Hierarchien in meinem Tag zu Tag Entwicklung. Dateisysteme, verschachtelter DAG-Knoten in Autodesk Maya, etc.

Ich frage mich, gibt es gute Module für Python speziell Hierarchien von Objekten zu durchqueren und vergleichen?

Von besonderem Interesse wären Wege sein ‚fuzzy‘ Vergleiche zwischen zwei fast zu tun identischen Hierarchien. Einige der Gründe dafür zum Abgleichen zwei Knoten Hierarchien in Maya aus zwei verschiedenen Zeichen, um Animation zu übertragen von einem zum anderen wäre.

Nach dem, was ich gelesen hätte, würde ich wahrscheinlich etwas mit einem Namen Schwelle muß (was ich konnte mich bauen) zum Vergleichen, wie nahe zwei Knotennamen zueinander sind. Ich würde dann einen Weg brauchen, um die Reihenfolge, gegebenenfalls ignorieren, dass untergeordnete Knoten in der Hierarchie angezeigt. Schließlich würde ich brauchen, um mit einer Tiefen Schwelle befassen, in Fällen, in denen ein Knoten leicht bewegt worden sein nach oben oder unten der Hierarchie.

Answer 1

Ich bin mir nicht sicher, ob ich die Notwendigkeit für ein komplettes Modul zu sehen -. Hierarchien ein Entwurfsmuster sind, und jede Hierarchie hat genug einzigartigen Eigenschaften, die es schwer zu verallgemeinern

class Node( object ):
    def __init__( self, myData, children=None )
        self.myData= myData
        self.children= children if children is not None else []
    def visit( self, aVisitor ):
        aVisitor.at( self )
        aVisitor.down()
        for c in self.children:
            aVisitor.at( c )
        aVisitor.up()

class Visitor( object ):
    def __init__( self ):
        self.depth= 0
    def down( self ):
        self.depth += 1
    def up( self ):
        self.depth -= 1

Ich finde, dass das alles ist, was ich brauche. Und ich habe festgestellt, dass es schwer ist, ein wiederverwendbares Modul, weil aus diesem zu machen (a) gibt es so wenig hier und (b) jede Anwendung hinzufügt oder ändert, so viel Code.

Außerdem finde ich, dass die am häufigsten verwendete Hierarchie des Dateisystems ist, für die ich die os Modul. Die zweite am häufigsten verwendete Hierarchie ist XML-Nachrichten, für die ich ElementTree (in der Regel über lxml) haben. Nach diesen beiden, verwende ich die oben genannten Strukturen als Vorlagen für meine Klassen, nicht als wörtliche wieder verwendbare Modul.

Answer 2

Ich empfehle Graben um xmldifff http://www.logilab.org/859 und zu sehen, wie sie vergleichen Knoten und parallel Bäume behandeln. Oder versuchen Sie das Schreiben eines [rekursive] Generator, der jeden [signifikanten] Knoten in einem Baum ergibt, sagen f(t), dann itertools.izip(f(t1),f(t2)) verwenden zu sammeln zusammen Knotenpaare zum Vergleich.

Die meisten der hierarchischen Strukturen beschäftige ich mich mit mehr als eine „Achse“, wie Elemente und Attribute in XML, und einige Knoten sind wichtiger als andere.

Für eine bizarre Lösung, serialisiert die beiden Bäume in Textdateien, machen Sie eine Referenz beachten Sie, dass Zeile #n in einem Baum von Knoten #x kommt. Tun Sie das auf beiden Bäume, füttern Sie die Dateien in diff und scannen die Ergebnisse zu bemerken, welche Teile des Baumes verändert haben. Sie können diese Zeile aus der Datei #n Karte 1 (und daher Knoten #x im ersten Baum) und die Linie aus der Datei #m 2 (und daher Knoten #y des zweiten Baum) bedeuten, dass ein Teil jedes Baums gleich ist oder anders aus.

Für jede Lösung Ihrer haben werden, um eine „kanonische Form“ von Ihrem Baum zu schaffen, eine, die alle nicht relevanten Leerzeichen fallen könnte, Anzeigeattribut, optional Knoten, usw. aus dem Vergleichsverfahren. Es könnte auch ersten vs. Tiefen ersten Durchlauf des Baumes (s) eine Breite bedeuten tun.

Answer 3

http://code.google.com/p/pytree/

diese vielleicht übertrieben oder gar nicht geeignet für das, was Sie brauchen:

http://networkx.lanl.gov/

http://www.osl.iu.edu/~dgregor/ bgl-python /