Модули обхода иерархии и сравнения для Python?

Question

В своей повседневной разработке я имею дело со множеством иерархий.Файловые системы, вложенные узлы DAG в Autodesk Maya и т.д.

Мне интересно, есть ли какие-нибудь хорошие модули для Python, специально разработанные для обхода и сравнения иерархий объектов?

Особый интерес представляли бы способы проведения "нечетких" сравнений между двумя почти идентичные иерархии.Некоторые из причин для этого могут заключаться в сопоставлении двух иерархий узлов в Maya из двух разных символов, чтобы перенести анимацию с одного на другой.

Основываясь на том, что я читал, мне, вероятно, понадобилось бы что-то с пороговым значением имени (которое я мог бы создать сам) для сравнения того, насколько близки имена двух узлов друг к другу.Затем мне понадобился бы способ необязательного игнорирования порядка отображения дочерних узлов в иерархии.Наконец, мне нужно было бы иметь дело с порогом глубины в тех случаях, когда узел, возможно, был немного перемещен вверх или вниз по иерархии.

Answer 1

Я не уверен, что вижу необходимость в полноценном модуле - иерархии - это шаблон проектирования, и каждая иерархия обладает достаточным количеством уникальных функций, которые трудно обобщить.

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

Я нахожу, что это все, что мне нужно.И я обнаружил, что из этого трудно создать повторно используемый модуль, потому что (а) здесь так мало информации и (б) каждое приложение добавляет или изменяет так много кода.

Кроме того, я нахожу, что наиболее часто используемая иерархия - это файловая система, для которой у меня есть os модуль.Вторая наиболее часто используемая иерархия - это XML-сообщения, для которых у меня есть ElementTree (обычно через lxml).После этих двух я использую вышеупомянутые структуры в качестве шаблонов для своих классов, а не как буквальный повторно используемый модуль.

Answer 2

Я рекомендую покопаться в xmldifff http://www.logilab.org/859 и видеть, как они сравнивают узлы и обрабатывают параллельные деревья.Или попробуйте написать [рекурсивный] генератор, который выдает каждый [значимый] узел в дереве, скажем f(t), затем используйте itertools.izip(f(t1),f(t2)) собрать вместе пары узлов для сравнения.

Большинство иерархических структур, с которыми я имею дело, имеют более одной "оси", как элементы и атрибуты в XML, и некоторые узлы более значимы, чем другие.

Для более странного решения сериализуйте два дерева в текстовые файлы, сделайте ссылочное примечание, что строка # n исходит из узла # x в дереве.Проделайте это с обоими деревьями, передайте файлы в diff и просканируйте результаты, чтобы заметить, какие части дерева изменились.Вы можете сопоставить, что строка # n из файла 1 (и, следовательно, узел # x в первом дереве) и строка # m из файла 2 (и, следовательно, узел # y второго дерева) означают, что какая-то часть каждого дерева одинакова или отличается.

Для любого решения вам придется установить "каноническую форму" вашего дерева, такую, которая могла бы исключить все игнорируемые пробелы, атрибуты отображения, необязательные узлы и т.д. Из процесса сравнения.Это также может означать , что сначала нужно сделать шаг вширь по сравнениюпервый обход дерева (деревьев) на глубину.

Answer 3

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

возможно, они излишни или вообще не подходят для того, что вам нужно:

http://networkx.lanl.gov/

http://www.osl.iu.edu /~dgregor/bgl-питон/