Changeset 679 for mds-and-trees

Timestamp:

08/27/17 19:48:02 (7 years ago)

Author:

konrad

Message:

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

File:

• mds-and-trees/tree-genealogy.py (modified) (2 diffs)

mds-and-trees/tree-genealogy.py

@@ -359 +359 @@
     def calculate_measures(self):
         print("Calculating measures...")
+        self.compute_depth()
         self.compute_adepth()
-        self.compute_depth()
         self.compute_children()
         self.compute_kind()
@@ -534 +534 @@
         self.props["adepth"] = [0 for x in range(len(self.tree.children))]
 
-        def compute_local_adepth(node):
-            my_adepth = 0
-            for c in self.tree.children[node]:
-                my_adepth = max(my_adepth, compute_local_adepth(c)+1)
-            self.props["adepth"][node] = my_adepth
-            return my_adepth
-
-        compute_local_adepth(0)
+        # order by maximum depth of the parent guarantees that co child is evaluated before its parent
+        visiting_order = [i for i in range(0, len(self.tree.parents))]
+        visiting_order = sorted(visiting_order, key=lambda q:
+                            0 if q == 0 else max([self.props["depth"][d] for d in self.tree.parents[q]]))[::-1]
+
+        for node in visiting_order:
+            children = self.tree.children[node]
+            if len(children) != 0:
+                # 0 by default
+                self.props["adepth"][node] = max([self.props["adepth"][child] for child in children])+1
         self.normalize_prop('adepth')