I moduli traversal e confronto di gerarchia per Python?

Question

ho a che fare con un sacco di gerarchie nel mio giorno per lo sviluppo giorno. I file system, i nodi DAG nidificati in Autodesk Maya, ecc.

Mi chiedo, ci sono dei buoni moduli per Python specificamente progettato per attraversare e confrontare le gerarchie di oggetti?

Di particolare interesse sarebbe il modo di fare paragoni 'sfocati' tra due quasi gerarchie identici. Alcune delle ragioni per fare questo sarebbe per corrispondenza due gerarchie di nodi di Maya da due personaggi differenti al fine di trasferire l'animazione da uno all'altro.

In base a quello che ho letto, probabilmente bisogno di qualcosa con una soglia nome (che ho potuto costruire me stesso) per confrontare quanto vicino due nomi dei nodi sono gli uni agli altri. Avevo poi bisogno di un senso facoltativamente ignorare l'ordine in cui appaiono nodi figlio nella gerarchia. Infine, avrei bisogno di trattare con una soglia di profondità, nei casi in cui un nodo potrebbe essere stato un po 'spostato verso l'alto o verso il basso nella gerarchia.

Answer 1

Non sono sicuro che vedo la necessità di un modulo completo -. Gerarchie sono un modello di progettazione, e ciascuna gerarchia ha caratteristiche abbastanza uniche che è difficile generalizzare

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

Trovo che questo è tutto quello che serve. E ho scoperto che è difficile fare un modulo riutilizzabile da questo perché (a) c'è così poco qui e (b) ogni applicazione aggiunti o modificati in modo molto codice.

Inoltre, trovo che la gerarchia più comunemente usato è il file system, per il quale ho il os modulo. La seconda gerarchia più comunemente usato è messaggi XML, per il quale ho ElementTree (di solito tramite lxml). Dopo quei due, io uso le strutture di cui sopra come modelli per le mie lezioni, non come un modulo riutilizzabile letterale.

Answer 2

Mi consiglia di scavare intorno xmldifff http://www.logilab.org/859 e vedere come si confronta nodi e gestire alberi paralleli. Oppure, provare a scrivere un generatore [ricorsiva] che produce ogni [significativa] nodo in un albero, dire f(t), quindi utilizzare itertools.izip(f(t1),f(t2)) per raccogliere insieme le coppie di nodi per il confronto.

La maggior parte delle strutture gerarchiche mi occupo di avere più di un "asse", come elementi ed attributi in XML, e alcuni nodi sono più importanti di altre.

Per una soluzione più bizzarra, serializzare il due alberi in file di testo, fare una nota referenziale che la linea n # proviene dal nodo #x in un albero. Fatelo per entrambi gli alberi, alimentare i file in diff, e la scansione dei risultati di notare che parti dell'albero sono cambiate. È possibile mappare che #n riga dal file 1 (e quindi il nodo nx nel primo albero) e la linea #m da file 2 (e quindi il nodo #y del secondo albero) significa che una parte di ogni albero è lo stesso o diversa.

Per ogni soluzione la vostra intenzione di avere per stabilire una "forma canonica" del vostro albero, uno che potrebbe far cadere tutti gli spazi ignorabili, attributi di visualizzazione, i nodi opzionali, ecc, dal processo di confronto. Potrebbe anche significare fare una larghezza prima contro la profondità prima attraversamento dell'albero (s).

Answer 3

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

questi forse eccessivo o non adatto a tutti per quello che vi serve:

http://networkx.lanl.gov/

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