اجتياز والمقارنة وحدات التسلسل الهرمي لبيثون؟

Question

وأنا أتعامل مع الكثير من التسلسل الهرمي في بلدي اليوم للتنمية اليوم. أنظمة الملفات، والعقد DAG المتداخلة في أوتوديسك مايا، الخ.

وأنا أتساءل، هل هناك أي وحدات جيدة لبيثون المصممة خصيصا لاجتياز ومقارنة التسلسل الهرمي للكائنات؟

وذات أهمية خاصة سيكون الطرق للقيام مقارنات "غامض" بين اثنين <م> تقريبا الهرمية متطابقة. أن بعض الأسباب للقيام بذلك يكون للمطابقة اثنين التسلسلات الهرمية عقدة في مايا من حرفين مختلفة لنقل الحركة من واحدة إلى أخرى.

وبناء على ما كنت القراءة، ربما كنت بحاجة الى شيء مع عتبة اسم (التي يمكن أن أبني لنفسي) لمقارنة مدى قرب اسمين العقدة هي لبعضها البعض. فما استقاموا لكم فاستقيموا ثم بحاجة إلى وسيلة لاختياريا تجاهل الترتيب الذي عقد الطفل تظهر في التسلسل الهرمي. وأخيرا، كنت بحاجة للتعامل مع عتبة العمق، في الحالات التي يكون فيها عقدة قد تم نقل قليلا أعلى أو لأسفل التسلسل الهرمي.

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 خط يأتي من # ضعف عقدة في شجرة. القيام بذلك على كل من الأشجار، وإطعام الملفات إلى فرق، وفحص النتائج لاحظت أي أجزاء من شجرة قد تغيرت. يمكنك تعيين أن # N خط من ملف 1 (وبالتالي عقدة # ضعف في أول شجرة) و# د الخط من ملف 2 (وبالتالي #Y عقدة من شجرة الثانية) يعني أن جزء من كل شجرة هو نفسه أو مختلفة.

لأي الحل ستكون لدينا لإنشاء "النموذج المعياري" للشجرة، واحدة قد إسقاط جميع المسافات تجاهله، سمات العرض، العقد اختياري، وما إلى ذلك، من عملية المقارنة. قد يعني أيضا القيام اتساع أولا مقابل عمق اجتياز الأول من شجرة (ق).

Answer 3

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

وهذه ربما مبالغة أو لا تتناسب على الإطلاق لماذا تحتاج:

http://networkx.lanl.gov/

http://www.osl.iu.edu/~dgregor/ BGL-الثعبان /