aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--rumba/model.py63
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())