Hiérarchie et modules traversal comparaison pour Python?

Question

Je traite avec beaucoup de hiérarchies dans mon jour au développement de jour. Les systèmes de fichiers, les noeuds DAG imbriqués dans Autodesk Maya, etc.

Je me demande, y at-il de bons modules pour Python spécialement conçu pour parcourir et comparer les hiérarchies d'objets?

Il serait particulièrement intéressant des moyens de faire des comparaisons « floues » entre deux presque hiérarchies identiques. Certaines des raisons pour ce faire serait de deux hiérarchies de noeud correspondant à Maya de deux personnages différents afin de transférer l'animation d'un à l'autre.

D'après ce que je lis, je serais probablement besoin de quelque chose avec un seuil de nom (que je pourrais me construire) pour comparer comment les noms de près de deux nœuds sont les uns aux autres. Je alors besoin d'un moyen pour éventuellement ignorer l'ordre que les noeuds enfants apparaissent dans la hiérarchie. Enfin, je dois traiter avec un seuil de profondeur, dans les cas où un nœud peut avoir été légèrement déplacé vers le haut ou en bas de la hiérarchie.

Answer 1

Je ne suis pas sûr que je vois la nécessité d'un module complet -. Les hiérarchies sont un modèle de conception, et chaque hiérarchie a assez des caractéristiques uniques qu'il est difficile de généraliser

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

Je trouve que cela est tout ce que je dois. Et je l'ai trouvé qu'il est difficile de faire un module réutilisable de cela parce que (a) il y a si peu ici et (b) chaque application permet d'ajouter ou des modifications du code tant.

De plus, je trouve que la hiérarchie la plus utilisée est le système de fichiers, pour lequel j'ai le module os. La deuxième hiérarchie le plus couramment utilisé est des messages XML, pour que j'ai ElementTree (généralement via lxml). Après ces deux, j'utilise les structures ci-dessus en tant que modèles pour mes classes, et non comme un module réutilisable littéral.

Answer 2

Je recommande de creuser autour xmldifff http://www.logilab.org/859 et de voir comment ils comparent les nœuds et gérer des arbres parallèles. Ou, essayez d'écrire un générateur [récursive] qui produit chaque noeud [important] dans un arbre, par exemple f(t), puis utilisez pour rassembler itertools.izip(f(t1),f(t2)) paires de noeuds pour la comparaison.

La plupart des structures hiérarchiques avec qui je traite ont plus d'un « axe », comme éléments et attributs en XML, et certains noeuds sont plus importants que d'autres.

Pour une solution plus bizarre, sérialiser les deux arbres fichiers texte, notez que référentielle #n ligne vient de noeud # x dans un arbre. Faire les deux arbres, nourrir les fichiers dans diff, et analyser les résultats remarquer que les parties de l'arbre ont changé. Vous pouvez mapper que #n de ligne de fichier 1 (et donc le noeud n ° x dans le premier arbre) et #m de ligne de fichier 2 (et donc noeud #Y du second arbre) signifie qu'une partie de chaque arbre est identique ou différent.

Pour toute solution vous êtes va devoir établir une « forme canonique » de votre arbre, qui pourrait laisser tomber tous les espaces ignorable, les attributs d'affichage, noeuds en option, etc., à partir du processus de comparaison. Cela peut vouloir dire aussi faire une première largeur par rapport à la profondeur première traversée de l'arbre (s).

Answer 3

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

ce peut-être surpuissant ou ne convient pas du tout ce que vous avez besoin:

http://networkx.lanl.gov/

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