Changeset 701 for mds-and-trees

Timestamp:

09/20/17 15:29:50 (7 years ago)

Author:

konrad

Message:

Fixed a bug that could occur for trees with a lot of crossover (assigning nodes positions in wrong order)

File:

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

mds-and-trees/tree-genealogy.py

@@ -397 +397 @@
         print("Calculating measures...")
         self.compute_depth()
+        self.compute_maxdepth()
         self.compute_adepth()
         self.compute_children()
@@ -493 +494 @@
         # 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]]))
+        visiting_order = sorted(visiting_order, key=lambda q:\
+                            0 if q == 0 else self.props["maxdepth"][q])
 
         start_time = timelib.time()
@@ -586 +587 @@
         self.normalize_prop('depth')
 
+    def compute_maxdepth(self):
+        self.props["maxdepth"] = [999999999 for x in range(len(self.tree.children))]
+        visited = [0 for x in range(len(self.tree.children))]
+
+        nodes_to_visit = [0]
+        visited[0] = 1
+        self.props["maxdepth"][0] = 0
+        while True:
+            current_node = nodes_to_visit[0]
+
+            for child in self.tree.children[current_node]:
+                if visited[child] == 0:
+                    visited[child] = 1
+                    nodes_to_visit.append(child)
+                    self.props["maxdepth"][child] = self.props["maxdepth"][current_node]+1
+                elif self.props["maxdepth"][child] < self.props["maxdepth"][current_node]+1:
+                    self.props["maxdepth"][child] = self.props["maxdepth"][current_node]+1
+                    if child not in  nodes_to_visit:
+                        nodes_to_visit.append(child)
+
+            nodes_to_visit = nodes_to_visit[1:]
+            if len(nodes_to_visit) == 0:
+                break
+
+        self.normalize_prop('maxdepth')
+
     def compute_adepth(self):
         self.props["adepth"] = [0 for x in range(len(self.tree.children))]
@@ -591 +618 @@
         # 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]
+        visiting_order = sorted(visiting_order, key=lambda q: self.props["maxdepth"][q])[::-1]
 
         for node in visiting_order:
@@ -672 +698 @@
                 if id not in self.ids:
                     return None
+
             return self.ids[id]