3 """Define :class:`Graph`, a directed, acyclic graph structure.
4 :class:`Graph`\s are composed of :class:`Node`\s, also defined by this
10 class CyclicGraphError (ValueError):
14 """A node/element in a graph.
16 Contains a list of the node's parents, and stores the node's
22 >>> a = Node(data='a')
23 >>> b = Node(parents=[a], data='b')
24 >>> c = Node(parents=[a], data='c')
25 >>> d = Node(parents=[b, c], data='d')
29 We can list all of a node's ancestors.
31 >>> print [node for node in d.ancestors()]
33 >>> print [node for node in d.ancestors(depth_first=True)]
36 Ancestors works with cycles.
39 >>> print [node for node in d.ancestors()]
42 We can find the cycle path.
44 >>> print d.parent_path(d)
47 After a run through :meth:`Graph.set_children`, we can also
50 >>> g = Graph([a, b, c, d])
57 >>> print [node for node in a.descendents(depth_first=True)]
60 def __init__(self, parents=[], data=None):
61 list.__init__(self, parents)
65 def __cmp__(self, other):
66 return -cmp(self.data, other.data)
67 def __eq__(self, other):
68 return self.__cmp__(other) == 0
69 def __ne__(self, other):
70 return self.__cmp__(other) != 0
71 def __lt__(self, other):
72 return self.__cmp__(other) < 0
73 def __gt__(self, other):
74 return self.__cmp__(other) > 0
75 def __le__(self, other):
76 return self.__cmp__(other) <= 0
77 def __ge__(self, other):
78 return self.__cmp__(other) >= 0
85 def traverse(self, next, depth_first=False):
86 """Iterate through all nodes returned by `next(node)`.
88 Will only yield each traversed node once, even in the case of
89 diamond inheritance, etc.
91 Breadth first by default. Set `depth_first==True` for a
94 stack = list(next(self))
102 if depth_first == True:
103 for target in reversed(next(node)):
104 stack.insert(0, target)
106 stack.extend(next(node))
108 def ancestors(self, depth_first=False):
109 """Generate all ancestors.
111 This is a small wrapper around :meth:`traverse`.
113 next = lambda node : node # list node's parents
114 for node in self.traverse(next=next, depth_first=depth_first):
117 def descendents(self, depth_first=False):
118 """Generate all decendents.
120 This is a small wrapper around :meth:`traverse`.
122 next = lambda node : node.children
123 for node in self.traverse(next=next, depth_first=depth_first):
126 def path(self, next, node):
127 """Return the shortest list of nodes connecting `self` to
128 `node` via `next(node)`.
132 stack = list(next(self))
133 paths = dict((id(n), [n]) for n in stack)
134 while len(stack) > 0:
136 n_path = paths[id(n)]
137 for target in next(n):
138 if id(target) in paths:
140 t_path = list(n_path)
141 t_path.append(target)
142 if id(target) == id(node):
145 paths[id(target)] = t_path
147 def parent_path(self, node):
148 """Return the shortest list of nodes connecting `self` to
151 This is a small wrapper around :meth:`path`.
153 next = lambda node : node # list node's parents
154 return self.path(next, node)
156 def child_path(self, node):
157 """Return the shortest list of nodes connecting `self` to
160 This is a small wrapper around :meth:`path`.
162 next = lambda node : node.children
163 return self.path(next, node)
166 class GraphRow (object):
167 """Represent the state of a single row in a graph.
169 Generated by :class:`GraphRowGenerator`, printed with
170 :class:`GraphRowPrinter`.
172 :attr:`node` is the active node and :attr:`active` is its branch
173 column index. :attr:`width` is the number of current branch
176 :attr:`born`, :attr:`dead`, and :attr:`inherited` are lists of
177 `(branch_column_index, target_node)` pairs. `dead` lists nodes
178 from previous rows whose branches complete on this row,
179 `inherited` lists nodes from previous rows whose branches continue
180 through this row, and `born` list nodes whose branches start on
183 def __init__(self, node, active=-1, dead=None, inherited=None, born=None,
190 if inherited == None:
192 self.inherited = inherited
196 self.tip_to_root = tip_to_root
198 class GraphRowPrinter (object):
199 """Customizable printing for :class:`GraphRow`.
201 The string rendering can be customized by changing :attr:`chars`.
202 Control over the branch columns:
204 ================= ===========================================
205 `node: ...` the active (most recently inserted) node
206 `split/join: ...` branching/merging runs from the active node
207 `run: connected` connect a branch to its eventual node
208 `run: blank` place-holder for extinct runs
209 ================= ===========================================
211 Branch columns are seperated by separator columns:
213 ================= =======================================================
214 `sep: split/join` separate split/join branch columns from the active node
215 `sep: default` separate all remaining branch columns
216 ================= =======================================================
218 def __init__(self, chars=None):
221 'node: both tip and root': 'b',
224 'node: regular': '*',
225 'split/join: born and died left of active': '>',
226 'split/join: born and died right of active': '<',
227 'split/join: born left of active': '/',
228 'split/join: born right of active': '\\',
229 'split/join: died left of active': '\\',
230 'split/join: died right of active': '/',
232 'run: connected': '|',
233 'sep: split/join': '-',
237 def __call__(self, graph_row):
238 """Render the :class:`GraphRow` instance `graph_row` as a
241 dead = [i for i,node in graph_row.dead]
242 inherited = [i for i,node in graph_row.inherited]
243 born = [i for i,node in graph_row.born]
244 right_connect = max(graph_row.active,
245 max(born+[-1]), # +[-1] protects against empty born
247 left_connect = min(graph_row.active,
248 min(born+[right_connect]),
249 min(dead+[right_connect]))
250 max_col = max(right_connect, max(inherited+[-1]))
252 for i in range(max_col + 1):
253 # Get char, the node or branch column character.
254 if i == graph_row.active:
257 char = self.chars['node: both tip and root']
258 elif graph_row.tip_to_root == True:
259 # The dead are children
260 char = self.chars['node: root']
261 else: # The dead are parents
262 char = self.chars['node: tip']
264 if graph_row.tip_to_root == True:
265 # The born are parents
266 char = self.chars['node: tip']
267 else: # The born are children
268 char = self.chars['node: root']
270 char = self.chars['node: regular']
272 if i in dead: # born and died
273 if i < graph_row.active:
275 'split/join: born and died left of active']
278 'split/join: born and died right of active']
280 if i < graph_row.active:
281 char = self.chars['split/join: born left of active']
283 char = self.chars['split/join: born right of active']
284 elif i in dead: # just died
285 if i < graph_row.active:
286 char = self.chars['split/join: died left of active']
288 char = self.chars['split/join: died right of active']
290 char = self.chars['run: connected']
292 char = self.chars['run: blank']
293 # Get sep, the separation character.
294 if i < left_connect or i >= right_connect:
295 sep = self.chars['sep: default']
297 sep = self.chars['sep: split/join']
298 if char == self.chars['run: blank']:
299 char = self.chars['sep: split/join']
300 string.extend([char, sep])
301 return ''.join(string)[:-1] # [-1] strips final sep
303 class GraphRowGenerator (list):
304 """A :class:`GraphRow` generator.
306 Contains a list of :class:`GraphRow`\s (added with
307 :meth:`insert`(:class:`hooke.util.graph.Node`)). You should
308 generate a graph with repeated calls::
311 g = GraphRowGenerator(tip_to_root=tip_to_root)
312 p = GraphRowPrinter(tip_to_root=tip_to_root)
317 For the split/join branch columns, "born" and "dead" are defined
318 from the point of view of `GraphRow`. For root-to-tip ordering
319 (`tip_to_root==False`, the default), "born" runs are determined
320 by the active node's children (which have yet to be printed) and
321 "dead" runs by its parents (which have been printed). If
322 `tip_to_root==True`, swap "children" and "parents" in the above
325 def __init__(self, tip_to_root=False):
327 self.tip_to_root = tip_to_root
328 def insert(self, node):
329 """Add a new node to the graph.
331 If `tip_to_root==True`, nodes should be inserted in
332 tip-to-root topological order (i.e. node must be inserted
333 before any of its parents).
335 If `tip_to_root==False`, nodes must be inserted before any
339 previous = GraphRow(node=None, active=-1)
342 current = GraphRow(node=node, active=-1, tip_to_root=self.tip_to_root)
343 if self.tip_to_root == True: # children die, parents born
344 dead_nodes = list(current.node.children)
345 born_nodes = list(current.node)
346 else: # root-to-tip: parents die, children born
347 dead_nodes = list(current.node)
348 born_nodes = list(current.node.children)
349 # Mark the dead and inherited branch columns
350 for i,node in previous.inherited + previous.born:
351 if node in dead_nodes or node == current.node:
352 current.dead.append((i, node))
354 current.inherited.append((i, node))
355 # Place born and active branch columns
356 num_born = max(len(born_nodes), 1) # 1 to ensure slot for active node
357 remaining = num_born # number of nodes left to place
358 used_slots = [i for i,n in current.inherited]
359 old_max = max(used_slots+[-1]) # +[-1] in case used_slots is empty
360 slots = sorted([i for i in range(old_max+1) if i not in used_slots])
361 remaining -= len(slots)
362 slots.extend(range(old_max+1, old_max+1+remaining))
363 current.active = slots[0]
364 current.born = zip(slots, born_nodes)
365 # TODO: sharing branches vs. current 1 per child
370 """A directed, acyclic graph structure.
372 Contains methods for sorting and printing graphs.
377 >>> class Nodes (object): pass
379 >>> for char in ['a','b','c','d','e','f','g','h','i']:
380 ... setattr(n, char, Node(data=char))
384 >>> n.e.extend([n.b, n.c, n.d])
388 >>> n.i.extend([n.f, n.g, n.h])
389 >>> g = Graph([n.a,n.b,n.c,n.d,n.e,n.f,n.g,n.h,n.i])
390 >>> g.topological_sort(tip_to_root=True)
391 >>> print [node for node in g]
392 [i, h, g, f, e, d, c, b, a]
393 >>> print g.ascii_graph()
403 >>> print g.ascii_graph(tip_to_root=True)
414 >>> for char in ['a','b','c','d','e','f','g','h']:
415 ... setattr(n, char, Node(data=char))
420 >>> n.f.extend([n.b, n.d])
421 >>> n.g.extend([n.e, n.f])
422 >>> n.h.extend([n.c, n.g])
423 >>> g = Graph([n.a,n.b,n.c,n.d,n.e,n.f,n.g,n.h])
424 >>> print g.ascii_graph(tip_to_root=True)
434 >>> for char in ['a','b','c','d','e','f','g','h','i']:
435 ... setattr(n, char, Node(data=char))
436 >>> for char in ['a', 'b','c','d','e','f','g','h']:
437 ... nx = getattr(n, char)
439 >>> g = Graph([n.a,n.b,n.c,n.d,n.e,n.f,n.g,n.h,n.i])
440 >>> print g.ascii_graph(tip_to_root=True)
451 >>> for char in ['a','b','c','d','e','f','g','h','i']:
452 ... setattr(n, char, Node(data=char))
453 >>> for char in ['b','c','d','e','f','g','h','i']:
454 ... nx = getattr(n, char)
456 >>> g = Graph([n.a,n.b,n.c,n.d,n.e,n.f,n.g,n.h,n.i])
457 >>> print g.ascii_graph(tip_to_root=True)
468 >>> for char in ['a','b','c','d','e','f','g','h','i']:
469 ... setattr(n, char, Node(data=char))
471 >>> n.e.extend([n.a, n.c])
472 >>> n.f.extend([n.c, n.d, n.e])
473 >>> n.g.extend([n.b, n.e, n.f])
474 >>> n.h.extend([n.a, n.c, n.d, n.g])
475 >>> n.i.extend([n.a, n.b, n.c, n.g])
476 >>> g = Graph([n.a,n.b,n.c,n.d,n.e,n.f,n.g,n.h,n.i])
477 >>> print g.ascii_graph(tip_to_root=True)
481 | | | | | | | | *-\-\ f
482 | | | | | | | *-|-|-< e
483 | | | | | | *-|-|-/ | d
484 | | r-|-|-/-|-|-/---/ c
488 Ok, enough pretty graphs ;). Here's an example of cycle
491 >>> for char in ['a','b','c','d']:
492 ... setattr(n, char, Node(data=char))
495 >>> n.d.extend([n.b, n.c])
497 >>> g = Graph([n.a,n.b,n.c,n.d])
498 >>> g.check_for_cycles()
499 Traceback (most recent call last):
501 CyclicGraphError: cycle detected:
507 def set_children(self):
508 """Fill out each node's :attr:`Node.children` list.
512 if node not in parent.children:
513 parent.children.append(node)
515 def topological_sort(self, tip_to_root=False):
516 """Algorithm from git's commit.c `sort_in_topological_order`_.
518 Default ordering is root-to-tip. Set `tip_to_root=True` for
521 In situations where topological sorting is ambiguous, the
522 nodes are sorted using the node comparison functions (__cmp__,
523 __lt__, ...). If `tip_to_root==True`, the inverse
524 comparison functions are used.
526 .. _sort_in_topological_order:
527 http://git.kernel.org/?p=git/git.git;a=blob;f=commit.c;h=731191e63bd39a89a8ea4ed0390c49d5605cdbed;hb=HEAD#l425
529 # sort tip-to-root first, then reverse if neccessary
534 parent._outcount += 1
535 tips = sorted([node for node in self if node._outcount == 0])
541 parent._outcount -= 1
542 if parent._outcount == 0:
543 bisect.insort(tips, parent)
546 final_len = len(self)
547 if final_len != orig_len:
548 raise CyclicGraphError(
549 '%d of %d elements not reachable from tips'
550 % (orig_len - final_len, orig_len))
551 if tip_to_root == False:
554 def check_for_cycles(self):
555 """Check for cyclic references.
558 if node in node.ancestors():
559 path = node.parent_path(node)
560 raise CyclicGraphError(
561 'cycle detected:\n %s'
562 % '\n '.join([repr(node)]+[repr(node) for node in path]))
564 def graph_rows(self, tip_to_root=False):
565 """Generate a sequence of (`graph_row`, `node`) tuples.
567 Preforms :meth:`set_children` and :meth:`topological_sort`
570 graph_row_generator = GraphRowGenerator(tip_to_root=tip_to_root)
572 self.topological_sort(tip_to_root=tip_to_root)
574 graph_row_generator.insert(node)
575 yield (graph_row_generator[-1], node)
577 def ascii_graph(self, graph_row_printer=None, string_fn=str,
579 """Print an ascii graph on the left with `string_fn(node)` on
580 the right. If `graph_row_printer` is `None`, a default
581 instance of :class:`GraphRowPrinter` will be used.
583 See the class docstring for example output.
585 if graph_row_printer == None:
586 graph_row_printer = GraphRowPrinter()
588 for row,node in self.graph_rows(tip_to_root=tip_to_root):
589 graph.append('%s %s' % (graph_row_printer(row), string_fn(node)))
590 return '\n'.join(graph)