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.
47 def __init__(self, parents=[], data=None):
48 list.__init__(self, parents)
51 def __cmp__(self, other):
52 return -cmp(self.data, other.data)
53 def __eq__(self, other):
54 return self.__cmp__(other) == 0
55 def __ne__(self, other):
56 return self.__cmp__(other) != 0
57 def __lt__(self, other):
58 return self.__cmp__(other) < 0
59 def __gt__(self, other):
60 return self.__cmp__(other) > 0
61 def __le__(self, other):
62 return self.__cmp__(other) <= 0
63 def __ge__(self, other):
64 return self.__cmp__(other) >= 0
71 def ancestors(self, depth_first=False):
72 """Generate all ancestors.
74 Will only yield each ancestor once, even in the case of
75 diamond inheritance, etc.
77 Breadth first by default.
87 if depth_first == True:
88 for parent in reversed(node):
89 stack.insert(0, parent)
93 """Return the shortest list of parents connecting `self` to
99 paths = dict((id(n), [n]) for n in stack)
100 while len(stack) > 0:
102 n_path = paths[id(n)]
104 if id(parent) in paths:
106 p_path = list(n_path)
107 p_path.append(parent)
108 if id(parent) == id(node):
111 paths[id(parent)] = p_path
113 class _GraphRowEntry (list):
114 """A node in the graph with outstanding children.
116 `columns` is a list of the indexes of outstanding columns which
117 will eventually attach to those children.
119 def __init__(self, node, columns=[]):
120 list.__init__(self, columns)
123 class GraphRow (list):
124 """A graph row generator.
126 Contains a list of :class:`_GraphRowEntry`\s (added with
127 :meth:`insert`), and generates the current line with
128 :meth:`__str__`. You should generate a graph with repeated
136 The string rendering can be cusomized by changing `g.chars`.
137 Control over the branch columns:
139 ================= ===========================================
140 `node: ...` the active (most recently inserted) node
141 `split/join: ...` branching/merging runs from the active node
142 `run: connected` connect a branch to its eventual node
143 `run: blank` place-holder for extinct runs
144 ================= ===========================================
146 Branch columns are seperated by separator columns:
148 ================= =======================================================
149 `sep: split/join` separate split/join branch columns from the active node
150 `sep: default` separate all remaining branch columns
151 ================= =======================================================
153 For the split/join branch columns, "born" and "died" are defined
154 from the point of view of `GraphRow`. Because trees are printed
155 tip-to-root (:meth:`Graph.topological_sort`), "born" runs are
156 determined by the active node's parents (which have not yet been
157 printed), and "dead" runs by its children (which have been
165 self._next_old_dead = []
167 'node: both tip and root': 'b',
170 'node: regular': '*',
171 'split/join: born and died left of active': '>',
172 'split/join: born and died right of active': '<',
173 'split/join: born left of active': '/',
174 'split/join: born right of active': '\\',
175 'split/join: died left of active': '\\',
176 'split/join: died right of active': '/',
178 'run: connected': '|',
179 'sep: split/join': '-',
182 def insert(self, node):
183 """Add a new node to the graph.
185 Nodes should be inserted in tip-to-root topological order
186 (i.e. node must be inserted before any of its parents).
189 self._last_width = self._width
190 self._old_dead = self._next_old_dead
193 if len(self) > 0 and len(self[-1].node) == 0:
194 # remove last entry's active column if it has no parents
195 self[-1].pop(0) # (it' already in _old_dead via _next_old_dead)
196 self._children = [(i,e) for i,e in enumerate(self) if node in e.node]
197 for i,e in self._children:
198 self._dead.append(e.pop(0)) # TODO: sharing branches vs. current 1 per child
199 exhausted = [] # _GraphRowEntry\s with no futher parents
206 remaining = max(len(node), 1)
207 slots = sorted(self._old_dead + self._dead)
208 self._born.extend(slots[:remaining])
209 remaining -= len(slots)
210 self._born.extend(range(self._last_width, self._last_width+remaining))
211 self._active = self._born[0]
212 self.append(_GraphRowEntry(node, columns=self._born))
213 self._width = max([e[-1] for e in self])+1
214 self._next_old_dead = [i for i in slots[len(self._born):] if i < self._width]
216 self._next_old_dead.insert(0, self._active)
219 """Render the current line of the graph as a string.
221 left_connects = [self._born[0]]
222 right_connects = [self._born[-1]]
223 if len(self._dead) > 0:
224 left_connects.append(self._dead[0])
225 right_connects.append(self._dead[-1])
226 left_connect = min(left_connects)
227 right_connect = max(right_connects)
229 for i in range(max(self._width, self._last_width)):
230 if i == self._active:
231 if len(self._node) == 0:
232 if len(self._children) == 0:
233 char = self.chars['node: both tip and root']
235 char = self.chars['node: root']
236 elif len(self._children) == 0:
237 char = self.chars['node: tip']
239 char = self.chars['node: regular']
240 elif i in self._born:
244 'split/join: born and died left of active']
247 'split/join: born and died right of active']
250 char = self.chars['split/join: born left of active']
252 char = self.chars['split/join: born right of active']
253 elif i in self._dead:
255 char = self.chars['split/join: died left of active']
257 char = self.chars['split/join: died right of active']
258 elif i in self._old_dead:
259 char = self.chars['run: blank']
261 char = self.chars['run: connected']
262 if i < left_connect or i >= right_connect:
263 sep = self.chars['sep: default']
265 sep = self.chars['sep: split/join']
266 if char == self.chars['run: blank']:
267 char = self.chars['sep: split/join']
268 string.extend([char, sep])
269 return ''.join(string)[:-1] # [-1] strips final sep
272 """A directed, acyclic graph structure.
274 Contains methods for sorting and printing graphs.
279 >>> class Nodes (object): pass
281 >>> for char in ['a','b','c','d','e','f','g','h','i']:
282 ... setattr(n, char, Node(data=char))
286 >>> n.e.extend([n.b, n.c, n.d])
290 >>> n.i.extend([n.f, n.g, n.h])
291 >>> g = Graph([n.a,n.b,n.c,n.d,n.e,n.f,n.g,n.h,n.i])
292 >>> g.topological_sort()
293 >>> print [node for node in g]
294 [i, h, g, f, e, d, c, b, a]
295 >>> print g.ascii_graph()
306 >>> for char in ['a','b','c','d','e','f','g','h']:
307 ... setattr(n, char, Node(data=char))
312 >>> n.f.extend([n.b, n.d])
313 >>> n.g.extend([n.e, n.f])
314 >>> n.h.extend([n.c, n.g])
315 >>> g = Graph([n.a,n.b,n.c,n.d,n.e,n.f,n.g,n.h])
316 >>> print g.ascii_graph()
326 >>> for char in ['a','b','c','d','e','f','g','h','i']:
327 ... setattr(n, char, Node(data=char))
328 >>> for char in ['a', 'b','c','d','e','f','g','h']:
329 ... nx = getattr(n, char)
331 >>> g = Graph([n.a,n.b,n.c,n.d,n.e,n.f,n.g,n.h,n.i])
332 >>> print g.ascii_graph()
343 >>> for char in ['a','b','c','d','e','f','g','h','i']:
344 ... setattr(n, char, Node(data=char))
345 >>> for char in ['b','c','d','e','f','g','h','i']:
346 ... nx = getattr(n, char)
348 >>> g = Graph([n.a,n.b,n.c,n.d,n.e,n.f,n.g,n.h,n.i])
349 >>> print g.ascii_graph()
360 >>> for char in ['a','b','c','d','e','f','g','h','i']:
361 ... setattr(n, char, Node(data=char))
363 >>> n.e.extend([n.a, n.c])
364 >>> n.f.extend([n.c, n.d, n.e])
365 >>> n.g.extend([n.b, n.e, n.f])
366 >>> n.h.extend([n.a, n.c, n.d, n.g])
367 >>> n.i.extend([n.a, n.b, n.c, n.g])
368 >>> g = Graph([n.a,n.b,n.c,n.d,n.e,n.f,n.g,n.h,n.i])
369 >>> print g.ascii_graph()
373 *-|-|-|-|-|-|-|-|-\-\ f
374 *-|-|-|-< | | | | | | e
375 | | | | | *-|-|-|-/ | d
376 r-/-|-|-|-|-/-|-|---/ c
380 Ok, enough pretty graphs ;). Here's an example of cycle
383 >>> for char in ['a','b','c','d']:
384 ... setattr(n, char, Node(data=char))
387 >>> n.d.extend([n.b, n.c])
389 >>> g = Graph([n.a,n.b,n.c,n.d])
390 >>> g.check_for_cycles()
391 Traceback (most recent call last):
393 CyclicGraphError: cycle detected:
399 def topological_sort(self):
400 """Algorithm from git's commit.c `sort_in_topological_order`_.
402 Ordering is tip-to-root.
404 In situations where topological sorting is ambiguous, the
405 nodes are sorted using the inverse (since we use tip-to-root
406 ordering) of their comparison functions (__cmp__, __lt__,
409 .. _sort_in_topological_order:
410 http://git.kernel.org/?p=git/git.git;a=blob;f=commit.c;h=731191e63bd39a89a8ea4ed0390c49d5605cdbed;hb=HEAD#l425
416 parent._outcount += 1
417 tips = sorted([node for node in self if node._outcount == 0])
423 parent._outcount -= 1
424 if parent._outcount == 0:
425 bisect.insort(tips, parent)
428 final_len = len(self)
429 if final_len != orig_len:
430 raise CyclicGraphError(
431 '%d of %d elements not reachable from tips'
432 % (orig_len - final_len, orig_len))
434 def check_for_cycles(self):
435 """Check for cyclic references.
438 if node in node.ancestors():
439 path = node.path(node)
440 raise CyclicGraphError(
441 'cycle detected:\n %s'
442 % '\n '.join([repr(node)]+[repr(node) for node in path]))
444 def graph_rows(self, graph_row=None):
445 """Generate a sequence of (`graph_row`, `node`) tuples.
447 Preforms :meth:`topological_sort` internally.
449 If `graph_row` is `None`, a new instance of :class:`GraphRow`
452 if graph_row == None:
453 graph_row = GraphRow()
454 self.topological_sort()
456 graph_row.insert(node)
457 yield (graph_row, node)
459 def ascii_graph(self, string_fn=str):
460 """Print an ascii graph on the left with `string_fn(node)` on
463 See the class docstring for example output.
466 for row,node in self.graph_rows():
467 graph.append('%s %s' % (str(row), string_fn(node)))
468 return '\n'.join(graph)