Changeset 619

Timestamp:

09/23/16 15:06:58 (8 years ago)

Author:

konrad

Message:

Changed spine and skeleton drawing methods from recurrent to iterative ones.

File:

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

mds-and-trees/tree-genealogy.py

@@ -261 +261 @@
 # ------------------------------------
 
-def draw_children_norec():
-    global visited
-    visited = {}
-    visited[firstnode] = True
-
+def draw_children():
     max_depth = 0
     for k, v in depth.items():
@@ -308 +304 @@
             break
 
-def draw_spine_recurrent(node):
-    global visited
-    for c in inv_nodes[node]:
-
-        # we want to draw the node just once
-        if all_parents_visited(c):
-            visited[c] = True
-
-            if depth[c] == depth[node] - 1:
-                if c in inv_nodes:
-                    draw_spine_recurrent(c)
-
-        if depth[c] == depth[node] - 1:
-            line_style = svg_spine_line_style
-            svg_add_line( (w_margin+w_no_margs*(positions[node][0]-min_width)/(max_width-min_width), h_margin+h_no_margs*positions[node][1]/max_height),
-                (w_margin+w_no_margs*(positions[c][0]-min_width)/(max_width-min_width), h_margin+h_no_margs*positions[c][1]/max_height), line_style)
-        #svg_add_dot( (w_margin+w_no_margs*(positions[c][0]-min_width)/(max_width-min_width), h_margin+h_no_margs*positions[c][1]/max_height), svg_spine_dot_style)
-
 def draw_spine():
-    global visited
-    visited = {}
-    visited[firstnode] = True
-
-    draw_spine_recurrent(firstnode)
-    #svg_add_dot( (w_margin+w_no_margs*(positions[firstnode][0]-min_width)/(max_width-min_width), h_margin+h_no_margs*positions[firstnode][1]/max_height), svg_spine_dot_style)
-
-def draw_skeleton_reccurent(node):
-    global visited
-    for c in inv_nodes[node]:
-
-        if all_parents_visited(c):
-            visited[c] = True
-
-            if depth[c] >= min_skeleton_depth: # or depth[c] == max([depth[q] for q in inv_nodes[node]]):
-                if c in inv_nodes:
-                    draw_skeleton_reccurent(c)
-
-        if depth[c] >= min_skeleton_depth: # or depth[c] == max([depth[q] for q in inv_nodes[node]]):
-            #print([depth[q] for q in inv_nodes[node]])
-            line_style = svg_spine_line_style
-            svg_add_line( (w_margin+w_no_margs*(positions[node][0]-min_width)/(max_width-min_width), h_margin+h_no_margs*positions[node][1]/max_height),
-                (w_margin+w_no_margs*(positions[c][0]-min_width)/(max_width-min_width), h_margin+h_no_margs*positions[c][1]/max_height), line_style)
-            #svg_add_dot( (w_margin+w_no_margs*(positions[c][0]-min_width)/(max_width-min_width), h_margin+h_no_margs*positions[c][1]/max_height), svg_spine_dot_style)
+    nodes_to_visit = [firstnode]
+    while True:
+        current_node = nodes_to_visit[0]
+
+        if current_node in inv_nodes:
+            for c in inv_nodes[current_node]: # inv_node => p->c
+                if depth[c] == depth[current_node] - 1:
+                    if not c in nodes_to_visit:
+                        nodes_to_visit.append(c)
+                    line_style = svg_spine_line_style
+                    svg_add_line( (w_margin+w_no_margs*(positions[current_node][0]-min_width)/(max_width-min_width), h_margin+h_no_margs*positions[current_node][1]/max_height),
+                        (w_margin+w_no_margs*(positions[c][0]-min_width)/(max_width-min_width), h_margin+h_no_margs*positions[c][1]/max_height), line_style)
+
+        # we remove the current node from the list
+        nodes_to_visit = nodes_to_visit[1:]
+        # if none left, we can stop
+        if len(nodes_to_visit) == 0:
+            break
 
 def draw_skeleton():
-    global visited
-    visited = {}
-    visited[firstnode] = True
-
-    draw_skeleton_reccurent(firstnode)
-    #svg_add_dot( (w_margin+w_no_margs*(positions[firstnode][0]-min_width)/(max_width-min_width), h_margin+h_no_margs*positions[firstnode][1]/max_height), svg_spine_dot_style)
+    nodes_to_visit = [firstnode]
+    while True:
+        current_node = nodes_to_visit[0]
+
+        if current_node in inv_nodes:
+            for c in inv_nodes[current_node]: # inv_node => p->c
+                if depth[c] >= min_skeleton_depth:
+                    if not c in nodes_to_visit:
+                        nodes_to_visit.append(c)
+                    line_style = svg_spine_line_style
+                    svg_add_line( (w_margin+w_no_margs*(positions[current_node][0]-min_width)/(max_width-min_width), h_margin+h_no_margs*positions[current_node][1]/max_height),
+                        (w_margin+w_no_margs*(positions[c][0]-min_width)/(max_width-min_width), h_margin+h_no_margs*positions[c][1]/max_height), line_style)
+
+        # we remove the current node from the list
+        nodes_to_visit = nodes_to_visit[1:]
+        # if none left, we can stop
+        if len(nodes_to_visit) == 0:
+            break
 
 # ------------------------------------
@@ -491 +475 @@
 
     if args.draw_tree:
-        draw_children_norec()
+        draw_children()
     if args.draw_skeleton:
         draw_skeleton()