diff options
| -rw-r--r-- | rumba/model.py | 63 |
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()) |