Changeset 681 for mds-and-trees

Timestamp:

08/28/17 18:43:30 (7 years ago)

Author:

konrad

Message:

Improved the compute_depth function so now it works much faster for trees with crossover

File:

• mds-and-trees/tree-genealogy.py (modified) (1 diff)

mds-and-trees/tree-genealogy.py

@@ -519 +519 @@
     def compute_depth(self):
         self.props["depth"] = [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["depth"][0] = 0
+
         while True:
-            for child in self.tree.children[nodes_to_visit[0]]:
-                nodes_to_visit.append(child)
-                self.props["depth"][child] = min([self.props["depth"][d] for d in self.tree.parents[child]])+1
+            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["depth"][child] = self.props["depth"][current_node]+1
             nodes_to_visit = nodes_to_visit[1:]
             if len(nodes_to_visit) == 0: