Python의 계층 트래버스 및 비교 모듈?

Question

나는 일상적인 개발에서 많은 계층 구조를 다룹니다. Autodesk Maya 등의 파일 시스템, 중첩 된 DAG 노드 등

나는 객체의 계층을 가로 지르고 비교하도록 특별히 설계된 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

나는 이것이 내가 필요한 전부라는 것을 알았습니다. 그리고 (a) 여기에 너무 적고 (b) 각 응용 프로그램이 너무 많은 코드를 추가하거나 변경하기 때문에 재사용 가능한 모듈을 만드는 것이 어렵다는 것을 알았습니다.

또한 가장 일반적으로 사용되는 계층 구조는 파일 시스템이라는 것을 알았습니다. os 기준 치수. 두 번째로 가장 일반적으로 사용되는 계층은 XML 메시지입니다. 여기에는 ElementTree (일반적으로 LXML을 통해)가 있습니다. 그 두 가지 후에는 위의 구조를 문자 그대로 재사용 가능한 모듈이 아닌 내 클래스의 템플릿으로 사용합니다.

Answer 2

xmldifff 주위를 파는 것이 좋습니다 http://www.logilab.org/859 그리고 그들이 노드를 비교하고 평행 한 나무를 다루는 방법을보고 있습니다. 또는 트리에 각각의 [중요한] 노드를 생산하는 [재귀] 생성기를 작성해보십시오. f(t), 그런 다음 사용하십시오 itertools.izip(f(t1),f(t2)) 비교를 위해 노드 쌍을 함께 수집합니다.

내가 다루는 대부분의 계층 구조는 XML의 요소 및 속성과 같이 하나 이상의 "축"를 가지고 있으며 일부 노드는 다른 노드보다 더 중요합니다.

보다 기괴한 솔루션의 경우 두 트리를 텍스트 파일로 직렬화하고 Line #N은 트리의 노드 #x에서 나옵니다. 두 나무 모두에게 파일을 공급하고 결과를 스캔하여 나무의 어떤 부분이 바뀌 었는지 확인하십시오. 파일 1 (그리고 첫 번째 트리의 노드 #x)에서 해당 줄 #N을 매핑 할 수 있고 파일 2에서 줄 #M (두 번째 트리의 노드 #y)이 각 트리의 일부 부분이 동일하거나 동일하거나 다른.

모든 솔루션의 경우 트리의 "표준 형태"를 설정해야합니다. 비교 프로세스에서 무지한 공백, 디스플레이 속성, 선택적 노드 등을 모두 떨어 뜨릴 수 있습니다. 또한 나무의 폭이 먼저 vs. 깊이의 첫 번째 순회를하는 것을 의미 할 수도 있습니다.

Answer 3

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

이것들은 아마도 당신이 필요로하는 것에 대해 과잉 또는 전혀 적합하지 않을 수 있습니다.

http://networkx.lanl.gov/

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