Hướng dẫn python collapsible tree - cây sập trăn

Đoạn mã mã nhanh và bẩn này dường như hoạt động trên cây tối thiểu của bạn, nhưng tôi sẽ cần thêm dữ liệu mẫu để kiểm tra nó với những cây phức tạp hơn:dirty code snippet seems to work on your minimal tree, but I would need more sample data to check it with more complex trees:

#! /usr/bin/python3

class Tree:
    def __init__ (self, tokens):
        self.children = []
        while tokens:
            self.children.append ( (tokens [1], float (tokens [0] ) ) )
            tokens = tokens [2:]

    def __repr__ (self):
        return '<{}>'.format (self.children)

    def pprint (self, indent = 0):
        prefix = '  ' * indent
        for child, dist in self.children:
            if isinstance (child, Tree):
                print (prefix, dist)
                child.pprint (indent + 1)
            else:
                print (prefix, child, dist)

    def collapse (self, limit):
        self.children = [ (child.collapse (limit) [0], dist)
            if isinstance (child, Tree)
            else (child, dist) for child, dist in self.children]
        avg = sum (dist for _, dist in self.children) / len (self.children)
        if avg > limit:
            return (self, 0)
        else:
            if any (isinstance (child, Tree) for child in self.children):
                print ('Would like to collapse, but cannot, as at least one child is a tree.')
                return (self, 0)
            return (''.join (child for child, _ in self.children), 0)


def parse (tree):
    stack = []
    buff = ''
    while True:
        c = tree [0]
        if c == ';': break
        tree = tree [1:]
        if c == '(':
            stack.insert (0, '(')
            continue
        if c == ')':
            if buff: stack.insert (0, buff)
            buff = ''
            popped = ''
            tokens = []
            while True:
                token = stack [0]
                stack = stack [1:]
                if token == '(': break
                tokens.append (token)
            stack.insert (0, Tree (tokens) )
            continue
        if c in ':,':
            if buff: stack.insert (0, buff)
            buff = ''
            continue
        buff += c
    if buff: stack.insert (0, buff)
    return Tree (stack)

t = parse ('(A:0.556705,(B:0.251059,C:0.251059):0.305646):0.556705;')
t.pprint ()
t.collapse (.3)
print ()
t.pprint ()

Cây không được kiểm soát là:

 0.556705
   0.305646
     C 0.251059
     B 0.251059
   A 0.556705

Cây bị sập bởi .3 là:

 0.556705
   CB 0.305646
   A 0.556705

Cây bị sập bằng 1.0 là:

CBA 0.556705

Cây bị sập bởi 0,1 là:

 0.556705
   0.305646
     C 0.251059
     B 0.251059
   A 0.556705

Ở đây một phiên bản sạch hơn của mã (tạo ra đầu ra ký hiệu Nerwick):

NOTA Bene: Cây đầu vào phải được dấu ngoặc đơn.: The input tree must be parenthesized.

#! /usr/bin/python3

class Tree:
    def __init__ (self, weight, children):
        self.weight = weight
        self.children = children [:]

    def distances (self, curDistance = .0, acc = None):
        if acc is None: acc = []
        for child in self.children:
            child.distances (self.weight + curDistance, acc)
        return acc

    def collapse (self, limit):
        self.children = [child.collapse (limit) for child in self.children]
        distances = self.distances (-self.weight)
        avg = sum (distances) / len (distances)
        if avg > limit: return self
        return Node (self.weight, ''.join (self.descendants () ) )

    def descendants (self):
        descendants = []
        for child in self.children:
            descendants.extend (child.descendants () )
        return descendants

    def __repr__ (self):
        return '({}):{}'.format (','.join (str (child) for child in self.children), self.weight)

class Node:
    def __init__ (self, weight, name):
        self.weight = weight
        self.name = name

    def distances (self, curDistance, acc):
        acc.append (curDistance + self.weight)

    def collapse (self, limit):
        return self

    def descendants (self):
        return [self.name]

    def __repr__ (self):
        return '{}:{}'.format (self.name, self.weight)

class Stack (list):
    def pop (self):
        e = self [0]
        del self [0]
        return e

    def push (self, e):
        self.insert (0, e)

def parse (tree):
    buff = ''
    stack = Stack ()
    while True:
        c = tree [0]
        if c == ';': break
        tree = tree [1:]

        if c == '(':
            stack.push (c)
            continue

        if c in ':,':
            if buff: stack.push (buff)
            buff = ''
            continue

        if c == ')':
            if buff: stack.push (buff)
            buff = ''
            popped = ''
            children = []
            while True:
                weight = stack.pop ()
                if weight == '(': break
                weight = float (weight)
                child = stack.pop ()
                if isinstance (child, Tree):
                    child.weight = weight
                else:
                    child = Node (weight, child)
                children.append (child)
            stack.push (Tree (0, children) )
            continue

        buff += c

    return stack.pop ()

t = parse ('((A:0.9,(B:0.2,C:0.3):0.3,(E:0.05,F:0.08):0.1):0.6);')
print ('Input tree is {}'.format (t) )
for limit in range (1, 6):
    limit = limit / 10
    print ('Collapsed by {} is {}'.format (limit, t.collapse (limit) ) )

Đầu ra là (với đầu vào đã sửa đổi):

Input tree is (((F:0.08,E:0.05):0.1,(C:0.3,B:0.2):0.3,A:0.9):0.6):0
Collapsed by 0.1 is ((FE:0.1,(C:0.3,B:0.2):0.3,A:0.9):0.6):0
Collapsed by 0.2 is ((FE:0.1,(C:0.3,B:0.2):0.3,A:0.9):0.6):0
Collapsed by 0.3 is ((FE:0.1,CB:0.3,A:0.9):0.6):0
Collapsed by 0.4 is ((FE:0.1,CB:0.3,A:0.9):0.6):0
Collapsed by 0.5 is (FECBA:0.6):0