Changeset 621

Timestamp:

10/10/16 17:18:52 (8 years ago)

Author:

konrad

Message:

Rewritten prepos_children to the iterative form + Turned on some debugging

File:

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

mds-and-trees/tree-genealogy.py

@@ -6 +6 @@
 import math
 import argparse
+import time as ttime
 
 TIME = "" # BIRTHS / GENERATIONAL / REAL
@@ -117 +118 @@
                         quit()
 
-                    if not creature["FromIDs"][0] in nodes:
+                    if not creature["FromIDs"][0] in nodes and firstnode == None:
                         firstnode = creature["FromIDs"][0]
 
@@ -130 +131 @@
             inv_nodes[val] = inv_nodes.get(val, [])
             inv_nodes[val].append(k)
+
+    print(len(nodes))
 
 
@@ -191 +194 @@
 # ------------------------------------
 
-def prepos_children_reccurent(node):
-    global visited
-    for c in inv_nodes[node]:
-
-        # we want to visit the node just once, after all of its parents
-        if not all_parents_visited(c):
-            continue
-        else:
-            visited[c] = True
-
-        cy = 0
-        if TIME == "BIRTHS":
-            if c[0] == "c":
-                cy = int(c[1:])
-            else:
-                cy = int(c)
-        elif TIME == "GENERATIONAL":
-            cy = positions[node][1]+1
-        elif TIME == "REAL":
-            cy = time[c]
-
-        if len(nodes[c]) == 1:
-            dissimilarity = 0
-            if JITTER == True:
-                dissimilarity = random.gauss(0,1)
-            else:
-                dissimilarity = 1
-            positions[c] = [xmin_crowd(positions[node][0]-dissimilarity, positions[node][0]+dissimilarity, cy), cy]
-        else:
-            vsum = sum([v for k, v in nodes[c].items()])
-            cx = sum([positions[k][0]*v/vsum for k, v in nodes[c].items()])
-
-            if JITTER == True:
-                positions[c] = [cx + random.gauss(0, 0.1), cy]
-            else:
-                positions[c] = [cx, cy]
-
-
-        if c in inv_nodes:
-            prepos_children_reccurent(c)
+# def prepos_children_reccurent(node):
+#     global visited
+#     for c in inv_nodes[node]:
+#
+#         # we want to visit the node just once, after all of its parents
+#         if not all_parents_visited(c):
+#             continue
+#         else:
+#             visited[c] = True
+#
+#         cy = 0
+#         if TIME == "BIRTHS":
+#             if c[0] == "c":
+#                 cy = int(c[1:])
+#             else:
+#                 cy = int(c)
+#         elif TIME == "GENERATIONAL":
+#             cy = positions[node][1]+1
+#         elif TIME == "REAL":
+#             cy = time[c]
+#
+#         if len(nodes[c]) == 1:
+#             dissimilarity = 0
+#             if JITTER == True:
+#                 dissimilarity = random.gauss(0,1)
+#             else:
+#                 dissimilarity = 1
+#             positions[c] = [xmin_crowd(positions[node][0]-dissimilarity, positions[node][0]+dissimilarity, cy), cy]
+#         else:
+#             vsum = sum([v for k, v in nodes[c].items()])
+#             cx = sum([positions[k][0]*v/vsum for k, v in nodes[c].items()])
+#
+#             if JITTER == True:
+#                 positions[c] = [cx + random.gauss(0, 0.1), cy]
+#             else:
+#                 positions[c] = [cx, cy]
+#
+#
+#         if c in inv_nodes:
+#             prepos_children_reccurent(c)
 
 def prepos_children():
-    global max_height, max_width, min_width, visited
+    global max_height, max_width, min_width, visited, TIME
+
+    print("firstnode " + firstnode)
 
     if not bool(time):
@@ -241 +246 @@
     positions[firstnode] = [0, 0]
 
-    visited = {}
-    visited[firstnode] = True
-    prepos_children_reccurent(firstnode)
+    #visited = {}
+    #visited[firstnode] = True
+
+
+    nodes_to_visit = [firstnode]
+
+    ccc = 0
+    timet = ttime.time()
+
+    while True:
+
+        ccc += 1
+        if ccc%1000 == 0 :
+            print(str(ccc) + " "  + str(ttime.time()-timet))
+            timet = ttime.time()
+
+        current_node = nodes_to_visit[0]
+
+        if current_node in inv_nodes:
+            for c in inv_nodes[current_node]:
+                # we want to visit the node just once, after all of its parents
+                if c not in nodes_to_visit:
+                    nodes_to_visit.append(c)
+
+                    cy = 0
+                    if TIME == "BIRTHS":
+                        if c[0] == "c":
+                            cy = int(c[1:])
+                        else:
+                            cy = int(c)
+                    elif TIME == "GENERATIONAL":
+                        cy = positions[current_node][1]+1
+                    elif TIME == "REAL":
+                        cy = time[c]
+
+                    if len(nodes[c]) == 1:
+                        dissimilarity = 0
+                        if JITTER == True:
+                            dissimilarity = random.gauss(0,1)
+                        else:
+                            dissimilarity = 1
+                        positions[c] = [xmin_crowd(positions[current_node][0]-dissimilarity, positions[current_node][0]+dissimilarity, cy), cy]
+                    else:
+                        vsum = sum([v for k, v in nodes[c].items()])
+                        cx = sum([positions[k][0]*v/vsum for k, v in nodes[c].items()])
+
+                        if JITTER == True:
+                            positions[c] = [cx + random.gauss(0, 0.1), cy]
+                        else:
+                            positions[c] = [cx, cy]
+
+
+        #if c in inv_nodes:
+        #    prepos_children_reccurent(c)
+
+        nodes_to_visit = nodes_to_visit[1:]
+        # if none left, we can stop
+        if len(nodes_to_visit) == 0:
+            break
+
+
+   # prepos_children_reccurent(firstnode)
 
     for pos in positions:
@@ -388 +452 @@
 min_skeleton_depth = 0
 
-firstnode = ""
+firstnode = None
 nodes = {}
 inv_nodes = {}