model: compute DIF topological ordering

1 files changed, 63 insertions, 0 deletions

diff --git a/rumba/model.py b/rumba/model.py
index 2337d19..f48b0dd 100644
--- a/rumba/model.py
+++ b/rumba/model.py
@@ -269,6 +269,69 @@ class Experiment:
     def del_node(self, node):
         self.nodes.remove(node)
 
+    # Examine the nodes, DIFs, registrations and compute the registration
+    # and enrollment order, etc.
+    def generate(self):
+
+        ###### Compute registration/enrollment order for DIFs #######
+
+        # Compute DIFs dependency graph, as both adjacency and incidence list.
+        difsdeps_adj = dict()
+        difsdeps_inc = dict()
+
+        for node in self.nodes:
+            for upper in node.dif_registrations:
+                for lower in node.dif_registrations[upper]:
+                    if upper not in difsdeps_inc:
+                        difsdeps_inc[upper] = set()
+                    if lower not in difsdeps_inc:
+                        difsdeps_inc[lower] = set()
+                    if upper not in difsdeps_adj:
+                        difsdeps_adj[upper] = set()
+                    if lower not in difsdeps_adj:
+                        difsdeps_adj[lower] = set()
+                    difsdeps_inc[upper].add(lower)
+                    difsdeps_adj[lower].add(upper)
+
+        # Kahn's algorithm below only needs per-node count of
+        # incident edges, so we compute these counts from the
+        # incidence list and drop the latter.
+        difsdeps_inc_cnt = dict()
+        for dif in difsdeps_inc:
+            difsdeps_inc_cnt[dif] = len(difsdeps_inc[dif])
+        del difsdeps_inc
+
+        #print(difsdeps_adj)
+        #print(difsdeps_inc_cnt)
+
+        # Run Kahn's algorithm to compute topological ordering on the DIFs graph.
+        frontier = set()
+        self.dif_ordering = []
+        for dif in difsdeps_inc_cnt:
+            if difsdeps_inc_cnt[dif] == 0:
+                frontier.add(dif)
+
+        while len(frontier):
+            cur = frontier.pop()
+            self.dif_ordering.append(cur)
+            for nxt in difsdeps_adj[cur]:
+                difsdeps_inc_cnt[nxt] -= 1
+                if difsdeps_inc_cnt[nxt] == 0:
+                    frontier.add(nxt)
+            difsdeps_adj[cur] = set()
+
+        circular_set = [dif for dif in difsdeps_inc_cnt if difsdeps_inc_cnt[dif] != 0]
+        if len(circular_set):
+            raise Exception("Fatal error: The specified DIFs topology has one or more"\
+                  "circular dependencies, involving the following"\
+                  " DIFs: %s" % circular_set)
+
+        del difsdeps_inc_cnt
+        del difsdeps_adj
+        del circular_set
+
+        print(self.dif_ordering)
+
     # Realize the experiment, using a testbed-specific setup
     def swap_in(self):
         self.testbed.create_experiment(self.nodes, self.get_links())