Modules de traversée de hiérarchie et de comparaison pour Python?

Question

Je fais face à beaucoup de hiérarchies dans mon développement au jour le jour. Systèmes de fichiers, nœuds DAG imbriqués dans Autodesk Maya, etc.

Je me demande s'il existe de bons modules pour Python spécialement conçus pour parcourir et comparer des hiérarchies d'objets. Un intérêt particulier serait de faire des comparaisons «floues» entre deux presque hiérarchies identiques. Certaines des raisons pour cela seraient de faire correspondre deux hiérarchies de nœuds dans Maya à partir de deux caractères différents afin de transférer l'animation de l'un à l'autre. En fonction de ce que j'ai lu, j'aurais probablement besoin de quelque chose avec un seuil de nom (que je pourrais construire moi-même) pour comparer la proximité de deux noms de nœuds entre eux. J'aurais alors besoin d'un moyen d'ignorer éventuellement l'ordre dans lequel les nœuds enfants apparaissent dans la hiérarchie. Enfin, je dois traiter un seuil de profondeur, dans les cas où un nœud peut avoir été légèrement déplacé vers le haut ou le 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 possède suffisamment de 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 c'est tout ce dont j'ai besoin. Et j'ai trouvé qu'il est difficile d'en faire un module réutilisable parce que (a) il y a si peu ici et (b) chaque application ajoute ou change autant de code.

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

Answer 2

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

ces 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/

Answer 3

Je recommande de creuser autour de xmldifff http://www.logilab.org/859 et de voir comment ils comparent les nœuds et manipulent les arbres parallèles. Ou, essayez d'écrire un générateur [récursif] qui génère chaque nœud [significatif] dans un arbre, disons f(t), puis utilisez itertools.izip(f(t1),f(t2)) pour collecter des paires de nœuds à des fins de comparaison.

La plupart des structures hiérarchiques que je traite ont plus d'un «axe», comme les éléments et les attributs en XML, et certains nœuds sont plus importants que d'autres. Pour une solution plus bizarre, sérialisez les deux arbres en fichiers texte, faites une note de référence indiquant que la ligne #n provient du noeud #x dans une arborescence. Faites cela aux deux arbres, alimentez les fichiers en diff, et scannez les résultats pour voir quelles parties de l'arbre ont changé. Vous pouvez mapper cette ligne #n du fichier 1 (et donc le noeud #x dans le premier arbre) et la ligne #m du fichier 2 (et donc le noeud #y du second arbre) signifie qu'une partie de chaque arbre est la même ou différent. Pour toute solution, vous devrez établir une "forme canonique" de votre arbre, qui pourrait supprimer tous les espaces ignorables, les attributs d'affichage, les nœuds optionnels, etc., du processus de comparaison. Cela pourrait aussi signifier faire une première traversée en profondeur par rapport à la première traversée de l'arbre (s).