Hierarchy traversal e moduli di confronto per Python?

Question

Mi occupo di molte gerarchie nel mio sviluppo quotidiano. File system, nodi DAG nidificati in Autodesk Maya, ecc.

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

Di particolare interesse sarebbe il modo di fare confronti "sfocati" tra due quasi gerarchie identiche a. Alcuni dei motivi per farlo sarebbe quello di far combaciare due gerarchie di nodi in Maya con due caratteri diversi per trasferire l'animazione da una all'altra.

Sulla base di ciò che ho letto, probabilmente avrei bisogno di qualcosa con una soglia di nome (che potrei costruire io stesso) per confrontare quanto vicini due nomi di nodi sono tra loro. Avrei quindi bisogno di un modo per ignorare facoltativamente l'ordine in cui i nodi figlio appaiono nella gerarchia. Infine, dovrei occuparmi di una soglia di profondità, nei casi in cui un nodo potrebbe essere stato spostato leggermente in alto o in basso nella gerarchia.

Answer 1

Non sono sicuro che vedo la necessità di un modulo completo - - Le gerarchie sono un modello di progettazione e ogni gerarchia ha abbastanza caratteristiche 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 sia tutto ciò di cui ho bisogno. E ho scoperto che è difficile creare un modulo riutilizzabile perché (a) c'è così poco qui e (b) ogni applicazione aggiunge o cambia tanto codice.

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

Answer 2

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/

Answer 3

Suggerisco di scavare intorno xmldifff http://www.logilab.org/859 e di vedere come confrontano i nodi e gestiscono alberi paralleli. Oppure, prova a scrivere un generatore [ricorsivo] che produce ciascun nodo [significativo] in un albero, ad esempio f(t), quindi utilizza itertools.izip(f(t1),f(t2)) per raccogliere insieme coppie di nodi per il confronto.

La maggior parte delle strutture gerarchiche con cui ho a che fare hanno più di un "asse", come elementi e attributi in XML, e alcuni nodi sono più significativi di altri.

Per una soluzione più bizzarra, serializzare i due alberi in file di testo, fare una nota di riferimento che la linea n viene dal nodo #x in un albero. Fatelo su entrambi gli alberi, fornite i file in diff e analizzate i risultati per vedere quali parti dell'albero sono cambiate. Puoi mappare la riga #n dal file 1 (e quindi il nodo #x nel primo albero) e la riga #m dal file 2 (e quindi il nodo #y del secondo albero) significa che una parte di ogni albero è la stessa o diverso.

Per qualsiasi soluzione, è necessario stabilire una "forma canonica" del proprio albero, una che potrebbe eliminare tutti gli spazi bianchi ignorabili, visualizzare attributi, nodi facoltativi, ecc., Dal processo di confronto. Potrebbe anche significare fare una prima spaziatura rispetto alla prima traversata di profondità dell'albero o degli alberi.