1 # Copyright (C) 2010-2011 W. Trevor King <wking@drexel.edu>
3 # This file is part of Hooke.
5 # Hooke is free software: you can redistribute it and/or modify it
6 # under the terms of the GNU Lesser General Public License as
7 # published by the Free Software Foundation, either version 3 of the
8 # License, or (at your option) any later version.
10 # Hooke is distributed in the hope that it will be useful, but WITHOUT
11 # ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
12 # or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
13 # Public License for more details.
15 # You should have received a copy of the GNU Lesser General Public
16 # License along with Hooke. If not, see
17 # <http://www.gnu.org/licenses/>.
19 """Define :class:`Graph`, a directed, acyclic graph structure.
20 :class:`Graph`\s are composed of :class:`Node`\s, also defined by this
26 class CyclicGraphError (ValueError):
30 """A node/element in a graph.
32 Contains a list of the node's parents, and stores the node's
38 >>> a = Node(data='a')
39 >>> b = Node(parents=[a], data='b')
40 >>> c = Node(parents=[a], data='c')
41 >>> d = Node(parents=[b, c], data='d')
45 We can list all of a node's ancestors.
47 >>> print [node for node in d.ancestors()]
49 >>> print [node for node in d.ancestors(depth_first=True)]
52 Ancestors works with cycles.
55 >>> print [node for node in d.ancestors()]
58 We can find the cycle path.
60 >>> print d.parent_path(d)
63 After a run through :meth:`Graph.set_children`, we can also
66 >>> g = Graph([a, b, c, d])
73 >>> print [node for node in a.descendents(depth_first=True)]
76 def __init__(self, parents=[], data=None):
77 list.__init__(self, parents)
81 def __cmp__(self, other):
82 return -cmp(self.data, other.data)
83 def __eq__(self, other):
84 return self.__cmp__(other) == 0
85 def __ne__(self, other):
86 return self.__cmp__(other) != 0
87 def __lt__(self, other):
88 return self.__cmp__(other) < 0
89 def __gt__(self, other):
90 return self.__cmp__(other) > 0
91 def __le__(self, other):
92 return self.__cmp__(other) <= 0
93 def __ge__(self, other):
94 return self.__cmp__(other) >= 0
101 def traverse(self, next, depth_first=False):
102 """Iterate through all nodes returned by `next(node)`.
104 Will only yield each traversed node once, even in the case of
105 diamond inheritance, etc.
107 Breadth first by default. Set `depth_first==True` for a
110 stack = list(next(self))
112 while len(stack) > 0:
118 if depth_first == True:
119 for target in reversed(next(node)):
120 stack.insert(0, target)
122 stack.extend(next(node))
124 def ancestors(self, depth_first=False):
125 """Generate all ancestors.
127 This is a small wrapper around :meth:`traverse`.
129 next = lambda node : node # list node's parents
130 for node in self.traverse(next=next, depth_first=depth_first):
133 def descendents(self, depth_first=False):
134 """Generate all decendents.
136 This is a small wrapper around :meth:`traverse`.
138 next = lambda node : node.children
139 for node in self.traverse(next=next, depth_first=depth_first):
142 def path(self, next, node):
143 """Return the shortest list of nodes connecting `self` to
144 `node` via `next(node)`.
148 stack = list(next(self))
149 paths = dict((id(n), [n]) for n in stack)
150 while len(stack) > 0:
152 n_path = paths[id(n)]
153 for target in next(n):
154 if id(target) in paths:
156 t_path = list(n_path)
157 t_path.append(target)
158 if id(target) == id(node):
161 paths[id(target)] = t_path
163 def parent_path(self, node):
164 """Return the shortest list of nodes connecting `self` to
167 This is a small wrapper around :meth:`path`.
169 next = lambda node : node # list node's parents
170 return self.path(next, node)
172 def child_path(self, node):
173 """Return the shortest list of nodes connecting `self` to
176 This is a small wrapper around :meth:`path`.
178 next = lambda node : node.children
179 return self.path(next, node)
182 class GraphRow (object):
183 """Represent the state of a single row in a graph.
185 Generated by :class:`GraphRowGenerator`, printed with
186 :class:`GraphRowPrinter`.
188 :attr:`node` is the active node and :attr:`active` is its branch
189 column index. :attr:`width` is the number of current branch
192 :attr:`born`, :attr:`dead`, and :attr:`inherited` are lists of
193 `(branch_column_index, target_node)` pairs. `dead` lists nodes
194 from previous rows whose branches complete on this row,
195 `inherited` lists nodes from previous rows whose branches continue
196 through this row, and `born` list nodes whose branches start on
199 def __init__(self, node, active=-1, dead=None, inherited=None, born=None,
206 if inherited == None:
208 self.inherited = inherited
212 self.tip_to_root = tip_to_root
214 class GraphRowPrinter (object):
215 """Customizable printing for :class:`GraphRow`.
217 The string rendering can be customized by changing :attr:`chars`.
218 Control over the branch columns:
220 ================= ===========================================
221 `node: ...` the active (most recently inserted) node
222 `split/join: ...` branching/merging runs from the active node
223 `run: connected` connect a branch to its eventual node
224 `run: blank` place-holder for extinct runs
225 ================= ===========================================
227 Branch columns are seperated by separator columns:
229 ================= =======================================================
230 `sep: split/join` separate split/join branch columns from the active node
231 `sep: default` separate all remaining branch columns
232 ================= =======================================================
234 def __init__(self, chars=None):
237 'node: both tip and root': 'b',
240 'node: regular': '*',
241 'split/join: born and died left of active': '>',
242 'split/join: born and died right of active': '<',
243 'split/join: born left of active': '/',
244 'split/join: born right of active': '\\',
245 'split/join: died left of active': '\\',
246 'split/join: died right of active': '/',
248 'run: connected': '|',
249 'sep: split/join': '-',
253 def __call__(self, graph_row):
254 """Render the :class:`GraphRow` instance `graph_row` as a
257 dead = [i for i,node in graph_row.dead]
258 inherited = [i for i,node in graph_row.inherited]
259 born = [i for i,node in graph_row.born]
260 right_connect = max(graph_row.active,
261 max(born+[-1]), # +[-1] protects against empty born
263 left_connect = min(graph_row.active,
264 min(born+[right_connect]),
265 min(dead+[right_connect]))
266 max_col = max(right_connect, max(inherited+[-1]))
268 for i in range(max_col + 1):
269 # Get char, the node or branch column character.
270 if i == graph_row.active:
273 char = self.chars['node: both tip and root']
274 elif graph_row.tip_to_root == True:
275 # The dead are children
276 char = self.chars['node: root']
277 else: # The dead are parents
278 char = self.chars['node: tip']
280 if graph_row.tip_to_root == True:
281 # The born are parents
282 char = self.chars['node: tip']
283 else: # The born are children
284 char = self.chars['node: root']
286 char = self.chars['node: regular']
288 if i in dead: # born and died
289 if i < graph_row.active:
291 'split/join: born and died left of active']
294 'split/join: born and died right of active']
296 if i < graph_row.active:
297 char = self.chars['split/join: born left of active']
299 char = self.chars['split/join: born right of active']
300 elif i in dead: # just died
301 if i < graph_row.active:
302 char = self.chars['split/join: died left of active']
304 char = self.chars['split/join: died right of active']
306 char = self.chars['run: connected']
308 char = self.chars['run: blank']
309 # Get sep, the separation character.
310 if i < left_connect or i >= right_connect:
311 sep = self.chars['sep: default']
313 sep = self.chars['sep: split/join']
314 if char == self.chars['run: blank']:
315 char = self.chars['sep: split/join']
316 string.extend([char, sep])
317 return ''.join(string)[:-1] # [-1] strips final sep
319 class GraphRowGenerator (list):
320 """A :class:`GraphRow` generator.
322 Contains a list of :class:`GraphRow`\s (added with
323 :meth:`insert`(:class:`hooke.util.graph.Node`)). You should
324 generate a graph with repeated calls::
327 g = GraphRowGenerator(tip_to_root=tip_to_root)
328 p = GraphRowPrinter(tip_to_root=tip_to_root)
333 For the split/join branch columns, "born" and "dead" are defined
334 from the point of view of `GraphRow`. For root-to-tip ordering
335 (`tip_to_root==False`, the default), "born" runs are determined
336 by the active node's children (which have yet to be printed) and
337 "dead" runs by its parents (which have been printed). If
338 `tip_to_root==True`, swap "children" and "parents" in the above
341 def __init__(self, tip_to_root=False):
343 self.tip_to_root = tip_to_root
344 def insert(self, node):
345 """Add a new node to the graph.
347 If `tip_to_root==True`, nodes should be inserted in
348 tip-to-root topological order (i.e. node must be inserted
349 before any of its parents).
351 If `tip_to_root==False`, nodes must be inserted before any
355 previous = GraphRow(node=None, active=-1)
358 current = GraphRow(node=node, active=-1, tip_to_root=self.tip_to_root)
359 if self.tip_to_root == True: # children die, parents born
360 dead_nodes = list(current.node.children)
361 born_nodes = list(current.node)
362 else: # root-to-tip: parents die, children born
363 dead_nodes = list(current.node)
364 born_nodes = list(current.node.children)
365 # Mark the dead and inherited branch columns
366 for i,node in previous.inherited + previous.born:
367 if node in dead_nodes or node == current.node:
368 current.dead.append((i, node))
370 current.inherited.append((i, node))
371 # Place born and active branch columns
372 num_born = max(len(born_nodes), 1) # 1 to ensure slot for active node
373 remaining = num_born # number of nodes left to place
374 used_slots = [i for i,n in current.inherited]
375 old_max = max(used_slots+[-1]) # +[-1] in case used_slots is empty
376 slots = sorted([i for i in range(old_max+1) if i not in used_slots])
377 remaining -= len(slots)
378 slots.extend(range(old_max+1, old_max+1+remaining))
379 current.active = slots[0]
380 current.born = zip(slots, born_nodes)
381 # TODO: sharing branches vs. current 1 per child
386 """A directed, acyclic graph structure.
388 Contains methods for sorting and printing graphs.
393 >>> class Nodes (object): pass
395 >>> for char in ['a','b','c','d','e','f','g','h','i']:
396 ... setattr(n, char, Node(data=char))
400 >>> n.e.extend([n.b, n.c, n.d])
404 >>> n.i.extend([n.f, n.g, n.h])
405 >>> g = Graph([n.a,n.b,n.c,n.d,n.e,n.f,n.g,n.h,n.i])
406 >>> g.topological_sort(tip_to_root=True)
407 >>> print [node for node in g]
408 [i, h, g, f, e, d, c, b, a]
409 >>> print g.ascii_graph()
419 >>> print g.ascii_graph(tip_to_root=True)
430 >>> for char in ['a','b','c','d','e','f','g','h']:
431 ... setattr(n, char, Node(data=char))
436 >>> n.f.extend([n.b, n.d])
437 >>> n.g.extend([n.e, n.f])
438 >>> n.h.extend([n.c, n.g])
439 >>> g = Graph([n.a,n.b,n.c,n.d,n.e,n.f,n.g,n.h])
440 >>> print g.ascii_graph(tip_to_root=True)
450 >>> for char in ['a','b','c','d','e','f','g','h','i']:
451 ... setattr(n, char, Node(data=char))
452 >>> for char in ['a', 'b','c','d','e','f','g','h']:
453 ... nx = getattr(n, char)
455 >>> g = Graph([n.a,n.b,n.c,n.d,n.e,n.f,n.g,n.h,n.i])
456 >>> print g.ascii_graph(tip_to_root=True)
467 >>> for char in ['a','b','c','d','e','f','g','h','i']:
468 ... setattr(n, char, Node(data=char))
469 >>> for char in ['b','c','d','e','f','g','h','i']:
470 ... nx = getattr(n, char)
472 >>> g = Graph([n.a,n.b,n.c,n.d,n.e,n.f,n.g,n.h,n.i])
473 >>> print g.ascii_graph(tip_to_root=True)
484 >>> for char in ['a','b','c','d','e','f','g','h','i']:
485 ... setattr(n, char, Node(data=char))
487 >>> n.e.extend([n.a, n.c])
488 >>> n.f.extend([n.c, n.d, n.e])
489 >>> n.g.extend([n.b, n.e, n.f])
490 >>> n.h.extend([n.a, n.c, n.d, n.g])
491 >>> n.i.extend([n.a, n.b, n.c, n.g])
492 >>> g = Graph([n.a,n.b,n.c,n.d,n.e,n.f,n.g,n.h,n.i])
493 >>> print g.ascii_graph(tip_to_root=True)
497 | | | | | | | | *-\-\ f
498 | | | | | | | *-|-|-< e
499 | | | | | | *-|-|-/ | d
500 | | r-|-|-/-|-|-/---/ c
504 Ok, enough pretty graphs ;). Here's an example of cycle
507 >>> for char in ['a','b','c','d']:
508 ... setattr(n, char, Node(data=char))
511 >>> n.d.extend([n.b, n.c])
513 >>> g = Graph([n.a,n.b,n.c,n.d])
514 >>> g.check_for_cycles()
515 Traceback (most recent call last):
517 CyclicGraphError: cycle detected:
523 def set_children(self):
524 """Fill out each node's :attr:`Node.children` list.
528 if node not in parent.children:
529 parent.children.append(node)
531 def topological_sort(self, tip_to_root=False):
532 """Algorithm from git's commit.c `sort_in_topological_order`_.
534 Default ordering is root-to-tip. Set `tip_to_root=True` for
537 In situations where topological sorting is ambiguous, the
538 nodes are sorted using the node comparison functions (__cmp__,
539 __lt__, ...). If `tip_to_root==True`, the inverse
540 comparison functions are used.
542 .. _sort_in_topological_order:
543 http://git.kernel.org/?p=git/git.git;a=blob;f=commit.c;h=731191e63bd39a89a8ea4ed0390c49d5605cdbed;hb=HEAD#l425
545 # sort tip-to-root first, then reverse if neccessary
550 parent._outcount += 1
551 tips = sorted([node for node in self if node._outcount == 0])
557 parent._outcount -= 1
558 if parent._outcount == 0:
559 bisect.insort(tips, parent)
562 final_len = len(self)
563 if final_len != orig_len:
564 raise CyclicGraphError(
565 '%d of %d elements not reachable from tips'
566 % (orig_len - final_len, orig_len))
567 if tip_to_root == False:
570 def check_for_cycles(self):
571 """Check for cyclic references.
574 if node in node.ancestors():
575 path = node.parent_path(node)
576 raise CyclicGraphError(
577 'cycle detected:\n %s'
578 % '\n '.join([repr(node)]+[repr(node) for node in path]))
580 def graph_rows(self, tip_to_root=False):
581 """Generate a sequence of (`graph_row`, `node`) tuples.
583 Preforms :meth:`set_children` and :meth:`topological_sort`
586 graph_row_generator = GraphRowGenerator(tip_to_root=tip_to_root)
588 self.topological_sort(tip_to_root=tip_to_root)
590 graph_row_generator.insert(node)
591 yield (graph_row_generator[-1], node)
593 def ascii_graph(self, graph_row_printer=None, string_fn=str,
595 """Print an ascii graph on the left with `string_fn(node)` on
596 the right. If `graph_row_printer` is `None`, a default
597 instance of :class:`GraphRowPrinter` will be used.
599 See the class docstring for example output.
601 if graph_row_printer == None:
602 graph_row_printer = GraphRowPrinter()
604 for row,node in self.graph_rows(tip_to_root=tip_to_root):
605 graph.append('%s %s' % (graph_row_printer(row), string_fn(node)))
606 return '\n'.join(graph)