Changeset 679 for mds-and-trees


Ignore:
Timestamp:
08/27/17 19:48:02 (3 years ago)
Author:
konrad
Message:

compute_adepth no longer uses recursion (so it should work better overall with the same results)

File:
1 edited

Legend:

Unmodified
Added
Removed
  • mds-and-trees/tree-genealogy.py

    r678 r679  
    359359    def calculate_measures(self):
    360360        print("Calculating measures...")
     361        self.compute_depth()
    361362        self.compute_adepth()
    362         self.compute_depth()
    363363        self.compute_children()
    364364        self.compute_kind()
     
    534534        self.props["adepth"] = [0 for x in range(len(self.tree.children))]
    535535
    536         def compute_local_adepth(node):
    537             my_adepth = 0
    538             for c in self.tree.children[node]:
    539                 my_adepth = max(my_adepth, compute_local_adepth(c)+1)
    540             self.props["adepth"][node] = my_adepth
    541             return my_adepth
    542 
    543         compute_local_adepth(0)
     536        # order by maximum depth of the parent guarantees that co child is evaluated before its parent
     537        visiting_order = [i for i in range(0, len(self.tree.parents))]
     538        visiting_order = sorted(visiting_order, key=lambda q:
     539                            0 if q == 0 else max([self.props["depth"][d] for d in self.tree.parents[q]]))[::-1]
     540
     541        for node in visiting_order:
     542            children = self.tree.children[node]
     543            if len(children) != 0:
     544                # 0 by default
     545                self.props["adepth"][node] = max([self.props["adepth"][child] for child in children])+1
    544546        self.normalize_prop('adepth')
    545547
Note: See TracChangeset for help on using the changeset viewer.