módulos de recorrido y la comparación de jerarquía para Python?

Question

Yo trato con una gran cantidad de jerarquías en mi día a día el desarrollo. Los sistemas de archivos, nodos DAG anidadas en Autodesk Maya, etc.

Me pregunto, ¿hay alguna buena módulos de Python diseñado específicamente para atravesar y comparar las jerarquías de objetos?

De particular interés sería maneras de hacer comparaciones 'difusos' entre dos casi jerarquías idénticos. Algunas de las razones para hacer esto sería para hacer coincidir dos jerarquías de nodo en Maya de dos personajes diferentes con el fin de transferir la animación de uno a otro.

Sobre la base de lo que he estado leyendo, probablemente necesito algo con un umbral de nombre (que podría construir yo mismo) para comparar qué tan cerca dos nombres de nodo son el uno al otro. Entonces iba a necesitar una manera de ignorar, opcionalmente, el orden en que aparecen los nodos secundarios en la jerarquía. Por último, que había necesidad de hacer frente a un umbral de profundidad, en los casos en que un nodo puede haber sido movido ligeramente hacia arriba o hacia abajo en la jerarquía.

Answer 1

No estoy seguro de que veo la necesidad de un módulo completo -. Las jerarquías son un patrón de diseño, y cada jerarquía tiene suficientes características únicas que es difícil generalizar

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

Me parece que esto es todo lo que necesito. Y he encontrado que es difícil hacer un módulo reutilizable de esto porque (a) hay tan poco aquí y (b) cada aplicación agrega o cambia mucho código.

Además, me parece que la jerarquía más comúnmente utilizado es el sistema de archivos, por lo que tengo el os módulo. La segunda jerarquía más comúnmente utilizada es mensajes XML, para el que he elementtree (normalmente a través de lxml). Después de los dos, yo uso las estructuras anteriores como plantillas para mis clases, no como un módulo reutilizable literal.

Answer 2

Yo recomiendo a excavar alrededor xmldifff http://www.logilab.org/859 y ver cómo se comparan los nodos y manejar árboles paralelos. O bien, intentar escribir un generador [recursiva] que produce cada nodo [significativa] en un árbol, por ejemplo f(t), a continuación, utilizar itertools.izip(f(t1),f(t2)) para recoger juntos pares de nodos para la comparación.

La mayoría de las estructuras jerárquicas que hacer frente a tener más de un "eje", como elementos y atributos XML y algunos nodos son más importantes que otros.

Para una solución más extraño, serializar los dos árboles a archivos de texto, hacer una nota referencial esa línea #n proviene de #x nodo en un árbol. Hacer eso a los dos árboles, alimentar a los archivos en diff, y escanear los resultados de notar, que las partes del árbol han cambiado. Puede asignar que #n línea del archivo 1 (y por lo tanto el nodo #x en el primer árbol) y # m de línea de archivo de 2 (y por lo tanto #y nodo del segundo árbol) significa que una parte de cada árbol es el mismo o diferente.

Para cualquier solución tu vas a tener que establecer una "forma canónica" de su árbol, uno que podría caer todos los espacios ignorable, atributos de visualización, los nodos opcionales, etc., desde el proceso de comparación. También podría significar hacer una amplitud primero frente a la profundidad primer recorrido del árbol (s).

Answer 3

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

Estos pueden ser exagerado o no se adapta en absoluto para lo que necesita:

http://networkx.lanl.gov/

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