1
2 """
3
4 @author: Fabio Erculiani <lxnay@sabayonlinux.org>
5 @contact: lxnay@sabayonlinux.org
6 @copyright: Fabio Erculiani
7 @copyright: Vincenzo Di Massa
8 @copyright:
9 @license: GPL-2
10
11 Entropy Graph implementation.
12 This module implements a Graph object and a topological sorting algorithm
13 based on Tarjan's.
14
15 """
16 from entropy.misc import Lifo
17
19
20 """
21 This class represents an item in the Graph. Inside this class you can find
22 the GraphNode stored content (through the item() method) and links between
23 other GraphNode objects.
24 """
25
27 """
28 GraphNode constructor.
29
30 @param item: the object it is intended to be stored inside this graph
31 node.
32 @type item: any Python object.
33 """
34 object.__init__(self)
35 self.__item = item
36 self.__arches = set()
37
39 """
40 Default string representation.
41 """
42 repr_str = "\n<GraphNode[item:%s][arches:%s]>\n" % (self.item(),
43 [str(x) for x in self.arches()],)
44 return repr_str
45
47 """
48 Return item content, object passed to the constructor.
49
50 @return: GraphNode content
51 @rtype: Python object
52 """
53 return self.__item
54
56 """
57 Our lil' graph item feels very lonely. Let's add an arch object to it.
58 (GraphArchSet).
59 An "arch" object is a topological arch representation.
60
61 @param arch: GraphArchSet instance
62 @type arch: GraphArchSet
63 @raises AttributeError: if arch is not a GraphArchSet instance
64 """
65 if not isinstance(arch, GraphArchSet):
66 raise AttributeError("GraphArchSet item expected")
67 self.__arches.add(arch)
68
70 """
71 Remove an arch object from this GraphNode instance.
72 An "arch" object is a topological arch representation.
73
74 @param arch: GraphArchSet instance
75 @type arch: GraphArchSet
76 @raises AttributeError: if arch is not a GraphArchSet instance
77 """
78 if not isinstance(arch, GraphArchSet):
79 raise AttributeError("GraphArchSet item expected")
80 self.__arches.discard(arch)
81
83 """
84 Return the currently stored list of arch objects.
85 An "arch" object is a topological arch representation.
86
87 @return: list (set) of GraphArchSet objects
88 @rtype: set
89 """
90 return self.__arches
91
93 """
94 Determine whether given GraphArchSet object represents an outgoing arch
95 of this GraphNode object.
96
97 @return: True, if GraphArchSet passed is an outgoing arch.
98 @rtype: bool
99 """
100 return arch.origin() is self
101
103 """
104 Determine whether given GraphArchSet object represents a coming arch
105 of this GraphNode object.
106
107 @return: True, if GraphArchSet passed is a coming arch.
108 @rtype: bool
109 """
110 return self in arch.endpoints()
111
112
114
115 """
116 This class represents a conceptually improved Graph arch
117 (or edge) which connects a starting point "A" to several end-
118 points {B,C,D...}.
119 The starting point is given at GraphArchSet construction time while
120 endpoints can be dynamically removed.
121 """
122
124 """
125 GraphArchSet constructor.
126
127 @param starting_point: a GraphNode instance which represents the
128 starting point of the "arch".
129 @type starting_point: a GraphNode instance
130 """
131 if not isinstance(starting_point, GraphNode):
132 raise AttributeError("GraphNode item expected")
133
134 object.__init__(self)
135 self.__origin = starting_point
136 self.__endpoints = set()
137
139 """
140 Default string representation.
141 """
142 repr_str = "<GraphArchSet[origin:%s][endpoints:%s]>" % (
143 repr(self.origin()), self.endpoints(),)
144 return repr_str
145
147 """
148 Return the origin of this GraphArchSet instance (in other words, the
149 starting_point object passed to the constructor).
150 """
151 return self.__origin
152
154 """
155 Our supercool GraphArchSet can be split infinite times to point to
156 multiple GraphNode objects. This methods adds another end-point to
157 the arch.
158
159 @param endpoint: a GraphNode instance which represents the
160 end-point of the "arch".
161 @type endpoint: a GraphNode instance
162 """
163 if not isinstance(endpoint, GraphNode):
164 raise AttributeError("GraphNode item expected")
165 self.__endpoints.add(endpoint)
166
168 """
169 Our supercool GraphArchSet can be split infinite times to point to
170 multiple GraphNode objects. This method removes an existing end-point
171 from the arch.
172 Beware that, for performance reasons, this method does not check
173 if endpoint object (GraphNode previously added with add_endpoint())
174 is effectively stored inside, so if endpoint does not exist, nothing
175 will happen.
176
177 @param endpoint: a GraphNode instance which represents the
178 end-point of the "arch".
179 @type endpoint: a GraphNode instance
180 """
181 if not isinstance(endpoint, GraphNode):
182 raise AttributeError("GraphNode item expected")
183 self.__endpoints.discard(endpoint)
184
186 """
187 This method returns a frozen copy of the internal end-point list object.
188
189 @return: list (set) of available endpoints
190 @rtype: frozenset
191 """
192 return frozenset(self.__endpoints)
193
194
196
197 """
198 This class implements the topological sorting algorithm presented by
199 R. E. Tarjan in 1972.
200 """
201
203 """
204 TopologicalSorter constructor.
205
206 @param adjacency_map: dict form adjacency map
207 @type adjacency_map: dict
208 """
209 object.__init__(self)
210 self.__adjacency_map = adjacency_map
211 self.__stack = Lifo()
212
214 """
215 Internal method, visits a node ad push to stack.
216 """
217 if node in low:
218 return
219
220 num = len(low)
221 low[node] = num
222 stack_pos = len(self.__stack)
223 self.__stack.push(node)
224
225 for successor in self.__adjacency_map[node]:
226 self.__topological_sort_visit_node(successor, low, result)
227 low[node] = min(low[node], low[successor])
228
229 if num == low[node]:
230 component = tuple()
231 while len(self.__stack) > stack_pos:
232 component += (self.__stack.pop(),)
233 result.append(component)
234 for item in component:
235 low[item] = len(self.__adjacency_map)
236
238 """
239 Find the strongly connected nodes in a adjacency_map using
240 Tarjan's algorithm.
241
242 adjacency_map should be a dictionary mapping node names to
243 lists of successor nodes.
244 """
245 result = []
246 low = {}
247
248 for node in self.__adjacency_map:
249 self.__topological_sort_visit_node(node, low, result)
250
251 return result
252
253
255 """
256 Effectively executes topological sorting on given graph.
257 """
258
259
260 count = dict((node, 0) for node in graph)
261
262 for node in graph:
263 for successor in graph[node]:
264 count[successor] += 1
265
266 ready_stack = Lifo()
267 for node in graph:
268 if count[node] == 0:
269 ready_stack.push(node)
270
271 dep_level = 1
272 result = {}
273 while ready_stack.is_filled():
274
275 node = ready_stack.pop()
276 result[dep_level] = node
277 dep_level += 1
278
279 for successor in graph[node]:
280 count[successor] -= 1
281 if count[successor] == 0:
282 ready_stack.push(successor)
283
284 return result
285
287 """
288 Return stored adjacency map used for sorting.
289
290 @return: stored adjacency map
291 @rtype: dict
292 """
293 return self.__adjacency_map
294
296 """
297 Given an adjacency map, identify strongly connected nodes,
298 then perform a topological sort on them.
299
300 @return: sorted graph representation
301 @rtype: dict
302 """
303
304 self.__stack.clear()
305
306 components = self.__strongly_connected_nodes()
307
308 node_component = {}
309 for component in components:
310 for node in component:
311 node_component[node] = component
312
313 component_graph = {}
314 for node in self.__adjacency_map:
315 node_c = node_component[node]
316 obj = component_graph.setdefault(node_c, [])
317 for successor in self.__adjacency_map[node]:
318 successor_c = node_component[successor]
319 if node_c != successor_c:
320 obj.append(successor_c)
321
322 return self.__topological_sort(component_graph)
323
324
326
327 """
328 This class represents a Graph object. Elements can be added using the
329 add() method and sorted using solve(). This class can also return an
330 adjacency map representing the currently stored elements in graph.
331 A topological sorting algorithm (using Tarjan's) is used to by solve().
332 """
333
335 """
336 Graph representation constructor.
337 """
338 object.__init__(self)
339 self.__graph = {}
340 self.__archs_map = {}
341 self.__graph_map_cache = None
342
344 """
345 Private method, stay away from here.
346 """
347 self.__graph_map_cache = None
348
350 """
351 Return GraphNode instance for added item (through add())
352
353 @param item: Python object to be added to the graph
354 @type item: Python object
355 @return: GraphNode instance bound to item
356 @rtype: entropy.graph.GraphNode
357 @raise KeyError: if item is not in Graph
358 """
359 return self.__graph[item]
360
361 - def add(self, item, dependency_items):
362 """
363 Add arbitrary object to Graph, specifying its dependencies.
364
365 @param item: Python object to be added to the graph
366 @type item: Python object
367 @param dependency_items: list of items which are dependencies of
368 the given item object
369 @type dependency_items; set
370 """
371 self.__invalidate_cache()
372
373 graph_node = self.__graph.setdefault(item, GraphNode(item))
374 arch = self.__archs_map.setdefault(graph_node, GraphArchSet(graph_node))
375 graph_node.add_arch(arch)
376
377 for dep_item in dependency_items:
378 graph_node_dep = self.__graph.setdefault(dep_item,
379 GraphNode(dep_item))
380 arch.add_endpoint(graph_node_dep)
381 graph_node_dep.add_arch(arch)
382
384 """
385 Return an adjacency map given the current items in Graph.
386
387 @return: adjacency map
388 @rtype: dict
389 """
390 if self.__graph_map_cache is not None:
391 return self.__graph_map_cache
392
393 graph_map = {}
394 for node_item in self.__graph.values():
395
396 my_graph_map = set()
397 for arch in node_item.arches():
398 if node_item.is_arch_outgoing(arch):
399 my_graph_map |= arch.endpoints()
400
401 graph_map[node_item] = my_graph_map
402
403 self.__graph_map_cache = graph_map
404 return graph_map
405
407 """
408 This method is equal to solve() but doesn't do any item back-translation
409 and just returns the relation between GraphNode objects that can be
410 manipulated directly by the caller.
411
412 @return: sorted graph representation (returning GraphNode objects)
413 @rtype: dict
414 """
415 adj_map = self.get_adjacency_map()
416 sorter = TopologicalSorter(adj_map)
417 return sorter.sort()
418
420 """
421 Thanks to "R. E. Tarjan" (1972) for the help ;-)
422 Serialize the graph and spit out a dependency order.
423 Data is returned in map form, where key represents the dependency
424 level and value a list of items at that dependency level.
425
426 @return: sorted graph representation
427 @rtype: dict
428 """
429 def trans_vals(node_list):
430 return tuple([x.item() for x in node_list])
431
432 sorted_data = self.solve_nodes()
433 return dict((x, trans_vals(y),) for x, y in sorted_data.items())
434
436 """
437 Return all items stored in the graph in raw form (list) without sorting
438 them.
439
440 @return: list of items added to Graph
441 @rtype: list
442 """
443 return [x.item() for x in self.__graph.values()]
444
445
446 __all__ = ["Graph"]
447