1
2
3
4
5
6
7
8
9
10 import copy
11 import rocon_utilities.console as console
12 import concert_msgs.msg as concert_msgs
13
14
15
16
17
18
19
20
22 '''
23 Forms a relationship between the node and the clients it is related with.
24 (node is the branch, clients are the leaves).
25 '''
27 '''
28 Forms an empty branch.
29 @param node
30 @type node.Node
31 '''
32 self.node = node
33 self.client_list = []
34
35 self.minimum_leaves = self.node.min
36 self.maximum_leaves = self.node.max
37 self.leaves = self.client_list
38
41
43 '''
44 We prune by name, which we know is unique (avoids worrying about python references).
45
46 @param leaves
47 @type [concert_msgs.ConcertClient]
48 '''
49 for leaf in leaves:
50 self.leaves[:] = [l for l in self.leaves if l.name != leaf.name]
51
53 '''
54 Computes the difference between the number of leaves and the
55 minimum required number of leaves.
56 '''
57 return len(self.leaves) - self.minimum_leaves
58
60 '''
61 Computes the difference between the maximum allowed number of leaves
62 and the number of leaves.
63 '''
64 if self.maximum_leaves == concert_msgs.LinkNode.UNLIMITED_RESOURCE:
65 return 3
66 else:
67 return self.maximum_leaves - len(self.leaves)
68
70 return console.cyan + self.node.id + console.reset + " : " + console.yellow + "%s" % [client.name for client in self.client_list] + console.reset
71
72
74 '''
75 Checks off implementation node rules and matches them to potential clients fulfilling the
76 required conditions (platform tuple, app, optionally name)
77
78 @param implementation node rules
79 @type [node.Node]
80
81 @param concert_clients: name indexed dictionary of concert client information
82 @type dic(str, concert_msgs.ConcertClient)
83
84 @return list of tuples, each of which is a node and list of clients that satisfy requirements for that node.
85 @rtype CompatibilityTree
86 '''
87 compatibility_tree = CompatibilityTree([])
88 for node in implementation_nodes:
89 compatibility_tree.branches.append(CompatibilityBranch(node))
90 clients = copy.deepcopy(concert_clients.values())
91 for branch in compatibility_tree.branches:
92 branch.client_list.extend([client for client in clients if branch.node.is_compatible(client)])
93 return compatibility_tree
94
95
97 '''
98 Recursive function that checks rule min/max allotments and prunes
99 the compatibility tree. It assumes none are currently fixed, so
100 pruning can happen anywhere.
101
102 @param branches listing compatible node - clients relationships
103 @type [ CompatibilityBranch ]
104 '''
105 pruned_branches = []
106 if verbosity:
107 compatibility_tree.print_branches("Pruning...", " ")
108
109
110
111
112 newly_pruned_branches, remaining_compatibility_tree = prune_resolvable_branches(compatibility_tree, verbosity)
113 pruned_branches.extend(newly_pruned_branches)
114
115 if newly_pruned_branches:
116 if remaining_compatibility_tree is not None:
117 pruned_branches.extend(prune_compatibility_tree(remaining_compatibility_tree, verbosity))
118 return pruned_branches
119
120
121
122
123
124
125
126
127 pruned_compatibility_tree = prune_least_valuable_leaf(compatibility_tree, verbosity)
128 if pruned_compatibility_tree is not None:
129 pruned_branches.extend(prune_compatibility_tree(pruned_compatibility_tree, verbosity))
130 else:
131 pruned_branches.extend(compatibility_tree.branches)
132 return pruned_branches
133
134
136 if verbosity:
137 print("")
138 compatibility_tree.print_branches("Pruning Resolvable Branches", " ")
139 pruned_branches = []
140 remaining_branches = []
141 branches = compatibility_tree.branches
142 removed_leaves = []
143 for branch in branches:
144 if not branch.leaves:
145 if not pruned_branches:
146 pruned_branches.append(copy.deepcopy(branch))
147 else:
148 remaining_branches.append(copy.deepcopy(branch))
149 elif len(branch.leaves) <= branch.minimum_leaves:
150 if not pruned_branches:
151 pruned_branches.append(copy.deepcopy(branch))
152 removed_leaves.extend(branch.leaves)
153 else:
154 remaining_branches.append(copy.deepcopy(branch))
155 else:
156 remaining_branches.append(copy.deepcopy(branch))
157 removed_leaves = list(set(removed_leaves))
158 for branch in remaining_branches:
159 branch.prune_leaves(removed_leaves)
160
161
162 if pruned_branches:
163 if remaining_branches:
164 if verbosity:
165 console.pretty_println(" --> pruning leaves: %s" % ' '.join([leaf.name for leaf in removed_leaves]), console.green)
166 console.pretty_println(" --> pruned automatically resolvable branches: %s\n" % ' '.join([branch.name() for branch in pruned_branches]), console.green)
167 return pruned_branches, CompatibilityTree(branches=remaining_branches)
168 else:
169 return pruned_branches, None
170 else:
171 if verbosity:
172 console.pretty_println(" --> no resolvable branches: \n", console.green)
173 return [], None
174
175
177 '''
178 This should be only called on a tree with branches
179 that have redundancy (i.e. more potential clients than
180 required (specified by node.min).
181
182 Does this by scanning the subtree looking for the least
183 visible leaf (client) not including those with visibility one.
184
185 It also grabs the branches that leaf is on, and there should multiple
186 possible branches, and subsequently chooses to lock it down on
187 the branch with the least redundancy, i.e. pruning it from
188 the rest of the tree.
189
190 This makes sure that there are plenty of possible options to
191 cover the branches that match this leaf but are not chosen.
192
193 @param subtree
194 @type [CompatibilityBranch]
195 '''
196 if verbosity:
197 compatibility_tree.print_branches('Pruning Least Valuable Leaf', ' ')
198 leaf_count = {}
199 leaves = {}
200 for branch in compatibility_tree.branches:
201 for leaf in branch.leaves:
202 if leaf.name not in leaves:
203 leaves[leaf.name] = leaf
204 leaf_count[leaf.name] = leaf_count[leaf.name] + 1 if leaf.name in leaf_count else 1
205
206 for k, v in leaf_count.items():
207 if v == 1:
208 del leaf_count[k]
209 if not leaf_count:
210 if verbosity:
211 console.pretty_println(" --> no pruning left to do, unwinding", console.green)
212
213 return None
214 least_visible_count = min(leaf_count.values())
215 least_visible_leaf_names = [name for name in leaf_count if leaf_count[name] == least_visible_count]
216
217 least_visible_leaf = leaves[least_visible_leaf_names[0]]
218
219 least_visible_branches = []
220 for branch in compatibility_tree.branches:
221 if least_visible_leaf in branch.leaves:
222 least_visible_branches.append(copy.deepcopy(branch))
223
224
225
226
227
228
229
230
231 value = lambda b: b.free_slots() if b.free_slots() < 0 else (1.0/b.redundancy())* min([3, b.free_slots()])
232 most_valuable_branch = None
233 for branch in least_visible_branches:
234 if most_valuable_branch is None or value(branch) > value(most_valuable_branch):
235 most_valuable_branch = branch
236
237 pruned_compatibility_tree = copy.deepcopy(compatibility_tree)
238 for branch in pruned_compatibility_tree.branches:
239 if branch.name() != most_valuable_branch.name():
240 branch.prune_leaves([least_visible_leaf])
241 if verbosity:
242 console.pretty_println(" --> pruning least visible leaf: %s" % least_visible_leaf.name, console.green)
243
244 return pruned_compatibility_tree
245
246
248 console.pretty_println(indent + "%s" % name, console.bold)
249 for branch in branches:
250 print(indent + " %s" % branch)
251
252
254 '''
255 Pretty prints a list of clients (names only)
256
257 @param leaves
258 @type [concert_msgs.ConcertClient]
259 '''
260 console.pretty_println(indent + "%s" % name, console.bold)
261 console.pretty_print(indent + " Clients: ", console.cyan)
262 console.pretty_println("%s " % [leaf.name for leaf in leaves], console.yellow)
263
264
266 ERROR_NONE = 0
267 ERROR_MINIMUM_REQUIREMENT_UNMET = 1
268 ERROR_EXCEEDED_MAXIMUM_REQUIREMENT = 2
269 ERROR_DUPLICATE_LEAVES = 3
270 '''
271 Stores the implementation node - concert client list compatibility
272 tree with algorithms to manipulate it.
273 '''
278
280 return [branch.node for branch in self.branches]
281
287
289 leaves = []
290 self.error_message = ""
291 for branch in self.branches:
292
293 if len(branch.leaves) < branch.minimum_leaves:
294 self.error_mode = CompatibilityTree.ERROR_MINIMUM_REQUIREMENT_UNMET
295 self.error_message = "waiting for clients of type " + branch.name() + " [" + str(len(branch.leaves)) + " < " + str(branch.minimum_leaves) + "]"
296 return False
297 if branch.maximum_leaves != concert_msgs.LinkNode.UNLIMITED_RESOURCE and len(branch.leaves) > branch.maximum_leaves:
298 self.error_mode = CompatibilityTree.ERROR_EXCEEDED_MAXIMUM_REQUIREMENT
299 self.error_message = branch.name() + "exceeded the maximum requirement [" + str(len(branch.leaves)) + " < " + str(branch.minimum_leaves) + "]"
300 return False
301
302 for leaf in branch.leaves:
303 if leaf in leaves:
304 self.error_mode = CompatibilityTree.ERROR_DUPLICATE_LEAVES
305 self.error_message = branch.name() + "more than one occurrence of a leaf [" + str(leaf) + "]"
306 return False
307 else:
308 leaves.append(leaf)
309 return True
310
312 console.pretty_println(indent + "%s" % name, console.bold)
313 for branch in self.branches:
314 print(indent + " %s" % branch)
315
317 '''
318 Just add to the first compatible branch (worry about more intelligent adding later)
319 '''
320 for branch in self.branches:
321 if branch.node.is_compatible(leaf):
322 if branch.maximum_leaves == concert_msgs.LinkNode.UNLIMITED_RESOURCE or len(branch.leaves) < branch.maximum_leaves:
323 branch.leaves.append(leaf)
324 return branch
325 return None
326
328 '''
329 Just remove the first matching leaf name. Assumption is the name is unique of course
330 (guaranteed by the conductor).
331 '''
332 for branch in self.branches:
333 for l in branch.leaves:
334 if leaf.name == l.name:
335 branch.leaves[:] = [l for l in branch.leaves if leaf.name != l.name]
336 break
337