hooke/util/graph.py

   1 # COPYRIGHT
   2
   3 """Define :class:`Graph`, a directed, acyclic graph structure.
   4 """
   5
   6 import bisect
   7
   8 class CyclicGraphError (ValueError):
   9     pass
  10
  11 class Node (list):
  12     """A node/element in a graph.
  13
  14     Contains a list of the node's parents, and stores the node's
  15     `data`.
  16
  17     Examples
  18     --------
  19
  20     >>> a = Node(data='a')
  21     >>> b = Node(parents=[a], data='b')
  22     >>> c = Node(parents=[a], data='c')
  23     >>> d = Node(parents=[b, c], data='d')
  24     >>> str(d)
  25     'd'
  26
  27     We can list all of a node's ancestors.
  28
  29     >>> print [node for node in d.ancestors()]
  30     [b, c, a]
  31     >>> print [node for node in d.ancestors(depth_first=True)]
  32     [b, a, c]
  33
  34     Ancestors works with cycles.
  35
  36     >>> a.append(d)
  37     >>> print [node for node in d.ancestors()]
  38     [b, c, a, d]
  39
  40     We can find the cycle path.
  41
  42     >>> print d.path(d)
  43     [b, a, d]
  44     """
  45     def __init__(self, parents=[], data=None):
  46         list.__init__(self, parents)
  47         self.data = data
  48
  49     def __cmp__(self, other):
  50         return -cmp(self.data, other.data)
  51     def __eq__(self, other):
  52         return self.__cmp__(other) == 0
  53     def __ne__(self, other):
  54         return self.__cmp__(other) != 0
  55     def __lt__(self, other):
  56         return self.__cmp__(other) < 0
  57     def __gt__(self, other):
  58         return self.__cmp__(other) > 0
  59     def __le__(self, other):
  60         return self.__cmp__(other) <= 0
  61     def __ge__(self, other):
  62         return self.__cmp__(other) >= 0
  63
  64     def __str__(self):
  65         return str(self.data)
  66     def __repr__(self):
  67         return self.__str__()
  68
  69     def ancestors(self, depth_first=False):
  70         """Generate all ancestors.
  71
  72         Will only yield each ancestor once, even in the case of
  73         diamond inheritance, etc.
  74
  75         Breadth first by default.
  76         """
  77         stack = list(self)
  78         popped = []
  79         while len(stack) > 0:
  80             node = stack.pop(0)
  81             if node in popped:
  82                 continue
  83             popped.append(node)
  84             yield node
  85             if depth_first == True:
  86                 for parent in reversed(node):
  87                     stack.insert(0, parent)
  88             else:
  89                 stack.extend(node)
  90     def path(self, node):
  91         """Return the shortest list of parents connecting `self` to
  92         `node`.
  93         """
  94         if node in self:
  95             return [node]
  96         stack = list(self)
  97         paths = dict((id(n), [n]) for n in stack)
  98         while len(stack) > 0:
  99             n = stack.pop(0)
 100             n_path = paths[id(n)]
 101             for parent in n:
 102                 if id(parent) in paths:
 103                     continue
 104                 p_path = list(n_path)
 105                 p_path.append(parent)
 106                 if id(parent) == id(node):
 107                     return p_path
 108                 stack.append(parent)
 109                 paths[id(parent)] = p_path
 110
 111 class _GraphRowEntry (list):
 112     """A node in the graph with outstanding children.
 113
 114     `columns` is a list of the indexes of outstanding columns which
 115     will eventually attach to those children.
 116     """
 117     def __init__(self, node, columns=[]):
 118         list.__init__(self, columns)
 119         self.node = node
 120
 121 class GraphRow (list):
 122     """A graph row generator.
 123
 124     Contains a list of :class:`_GraphRowEntry`\s (added with
 125     :meth:`insert`), and generates the current line with
 126     :meth:`__str__`.  You should generate a graph with repeated
 127     calls::
 128
 129         g = GraphRow()
 130         for node in nodes:
 131             g.insert(node)
 132             print str(g)
 133
 134     The string rendering can be cusomized by changing `g.chars`.
 135     Control over the branch columns:
 136
 137     ================= ===========================================
 138     `node: ...`       the active (most recently inserted) node
 139     `split/join: ...` branching/merging runs from the active node
 140     `run: connected`  connect a branch to its eventual node
 141     `run: blank`      place-holder for extinct runs
 142     ================= ===========================================
 143
 144     Branch columns are seperated by separator columns:
 145
 146     ================= =======================================================
 147     `sep: split/join` separate split/join branch columns from the active node
 148     `sep: default`    separate all remaining branch columns
 149     ================= =======================================================
 150
 151     For the split/join branch columns, "born" and "died" are defined
 152     from the point of view of `GraphRow`.  Because trees are printed
 153     tip-to-root (:meth:`Graph.topological_sort`), "born" runs are
 154     determined by the active node's parents (which have not yet been
 155     printed), and "dead" runs by its children (which have been
 156     printed).
 157     """
 158     def __init__(self):
 159         list.__init__(self)
 160         self._width = 0
 161         self._last_width = 0
 162         self._old_dead = []
 163         self._next_old_dead = []
 164         self.chars = {
 165             'node: both tip and root': 'b',
 166             'node: root': 'r',
 167             'node: tip': 't',
 168             'node: regular': '*',
 169             'split/join: born and died left of active': '>',
 170             'split/join: born and died right of active': '<',
 171             'split/join: born left of active': '/',
 172             'split/join: born right of active': '\\',
 173             'split/join: died left of active': '\\',
 174             'split/join: died right of active': '/',
 175             'run: blank': ' ',
 176             'run: connected': '|',
 177             'sep: split/join': '-',
 178             'sep: default': ' ',
 179             }
 180     def insert(self, node):
 181         """Add a new node to the graph.
 182
 183         Nodes should be inserted in tip-to-root topological order
 184         (i.e. node must be inserted before any of its parents).
 185         """
 186         self._node = node
 187         self._last_width = self._width
 188         self._old_dead = self._next_old_dead
 189         self._born = []
 190         self._dead = []
 191         if len(self) > 0 and len(self[-1].node) == 0:
 192             # remove last entry's active column if it has no parents
 193             self[-1].pop(0) # (it' already in _old_dead via _next_old_dead)
 194         self._children = [(i,e) for i,e in enumerate(self) if node in e.node]
 195         for i,e in self._children:
 196             self._dead.append(e.pop(0)) # TODO: sharing branches vs. current 1 per child
 197         exhausted = [] # _GraphRowEntry\s with no futher parents
 198         for e in self:
 199             if len(e) == 0:
 200                 exhausted.append(e)
 201         for e in exhausted:
 202             self.remove(e)
 203         self._dead.sort()
 204         remaining = max(len(node), 1)
 205         slots = sorted(self._old_dead + self._dead)
 206         self._born.extend(slots[:remaining])
 207         remaining -= len(slots)
 208         self._born.extend(range(self._last_width, self._last_width+remaining))
 209         self._active = self._born[0]
 210         self.append(_GraphRowEntry(node, columns=self._born))
 211         self._width = max([e[-1] for e in self])+1
 212         self._next_old_dead = [i for i in slots[len(self._born):] if i < self._width]
 213         if len(node) == 0:
 214             self._next_old_dead.insert(0, self._active)
 215
 216     def __str__(self):
 217         """Render the current line of the graph as a string.
 218         """
 219         left_connects = [self._born[0]]
 220         right_connects = [self._born[-1]]
 221         if len(self._dead) > 0:
 222             left_connects.append(self._dead[0])
 223             right_connects.append(self._dead[-1])
 224         left_connect = min(left_connects)
 225         right_connect = max(right_connects)
 226         string = []
 227         for i in range(max(self._width, self._last_width)):
 228             if i == self._active:
 229                 if len(self._node) == 0:
 230                     if len(self._children) == 0:
 231                         char = self.chars['node: both tip and root']
 232                     else:
 233                         char = self.chars['node: root']
 234                 elif len(self._children) == 0:
 235                     char = self.chars['node: tip']
 236                 else:
 237                     char = self.chars['node: regular']
 238             elif i in self._born:
 239                 if i in self._dead:
 240                     if i < self._active:
 241                         char = self.chars[
 242                             'split/join: born and died left of active']
 243                     else:
 244                         char = self.chars[
 245                             'split/join: born and died right of active']
 246                 else:
 247                     if i < self._active:
 248                         char = self.chars['split/join: born left of active']
 249                     else:
 250                         char = self.chars['split/join: born right of active']
 251             elif i in self._dead:
 252                 if i < self._active:
 253                     char = self.chars['split/join: died left of active']
 254                 else:
 255                     char = self.chars['split/join: died right of active']
 256             elif i in self._old_dead:
 257                 char = self.chars['run: blank']
 258             else:
 259                 char = self.chars['run: connected']
 260             if i < left_connect or i >= right_connect:
 261                 sep = self.chars['sep: default']
 262             else:
 263                 sep = self.chars['sep: split/join']
 264                 if char == self.chars['run: blank']:
 265                     char = self.chars['sep: split/join']
 266             string.extend([char, sep])
 267         return ''.join(string)[:-1] # [-1] strips final sep
 268
 269 class Graph (list):
 270     """A directed, acyclic graph structure.
 271
 272     Contains methods for sorting and printing graphs.
 273
 274     Examples
 275     --------
 276
 277     >>> class Nodes (object): pass
 278     >>> n = Nodes()
 279     >>> for char in ['a','b','c','d','e','f','g','h','i']:
 280     ...     setattr(n, char, Node(data=char))
 281     >>> n.b.append(n.a)
 282     >>> n.c.append(n.a)
 283     >>> n.d.append(n.a)
 284     >>> n.e.extend([n.b, n.c, n.d])
 285     >>> n.f.append(n.e)
 286     >>> n.g.append(n.e)
 287     >>> n.h.append(n.e)
 288     >>> n.i.extend([n.f, n.g, n.h])
 289     >>> g = Graph([n.a,n.b,n.c,n.d,n.e,n.f,n.g,n.h,n.i])
 290     >>> g.topological_sort()
 291     >>> print [node for node in g]
 292     [i, h, g, f, e, d, c, b, a]
 293     >>> print g.ascii_graph()
 294     t-\-\ i
 295     * | | h
 296     | * | g
 297     | | * f
 298     *-<-< e
 299     * | | d
 300     | * | c
 301     | | * b
 302     r-/-/ a
 303
 304     >>> for char in ['a','b','c','d','e','f','g','h']:
 305     ...     setattr(n, char, Node(data=char))
 306     >>> n.b.append(n.a)
 307     >>> n.c.append(n.b)
 308     >>> n.d.append(n.a)
 309     >>> n.e.append(n.d)
 310     >>> n.f.extend([n.b, n.d])
 311     >>> n.g.extend([n.e, n.f])
 312     >>> n.h.extend([n.c, n.g])
 313     >>> g = Graph([n.a,n.b,n.c,n.d,n.e,n.f,n.g,n.h])
 314     >>> print g.ascii_graph()
 315     t-\ h
 316     *-|-\ g
 317     *-|-|-\ f
 318     | | * | e
 319     *-|-/ | d
 320     | *   | c
 321     | *---/ b
 322     r-/ a
 323
 324     >>> for char in ['a','b','c','d','e','f','g','h','i']:
 325     ...     setattr(n, char, Node(data=char))
 326     >>> for char in ['a', 'b','c','d','e','f','g','h']:
 327     ...     nx = getattr(n, char)
 328     ...     n.i.append(nx)
 329     >>> g = Graph([n.a,n.b,n.c,n.d,n.e,n.f,n.g,n.h,n.i])
 330     >>> print g.ascii_graph()
 331     t-\-\-\-\-\-\-\ i
 332     r | | | | | | | h
 333     r-/ | | | | | | g
 334     r---/ | | | | | f
 335     r-----/ | | | | e
 336     r-------/ | | | d
 337     r---------/ | | c
 338     r-----------/ | b
 339     r-------------/ a
 340
 341     >>> for char in ['a','b','c','d','e','f','g','h','i']:
 342     ...     setattr(n, char, Node(data=char))
 343     >>> for char in ['b','c','d','e','f','g','h','i']:
 344     ...     nx = getattr(n, char)
 345     ...     nx.append(n.a)
 346     >>> g = Graph([n.a,n.b,n.c,n.d,n.e,n.f,n.g,n.h,n.i])
 347     >>> print g.ascii_graph()
 348     t i
 349     | t h
 350     | | t g
 351     | | | t f
 352     | | | | t e
 353     | | | | | t d
 354     | | | | | | t c
 355     | | | | | | | t b
 356     r-/-/-/-/-/-/-/ a
 357
 358     >>> for char in ['a','b','c','d','e','f','g','h','i']:
 359     ...     setattr(n, char, Node(data=char))
 360     >>> n.d.append(n.a)
 361     >>> n.e.extend([n.a, n.c])
 362     >>> n.f.extend([n.c, n.d, n.e])
 363     >>> n.g.extend([n.b, n.e, n.f])
 364     >>> n.h.extend([n.a, n.c, n.d, n.g])
 365     >>> n.i.extend([n.a, n.b, n.c, n.g])
 366     >>> g = Graph([n.a,n.b,n.c,n.d,n.e,n.f,n.g,n.h,n.i])
 367     >>> print g.ascii_graph()
 368     t-\-\-\ i
 369     | | | | t-\-\-\ h
 370     *-|-|-|-<-|-|-|-\ g
 371     *-|-|-|-|-|-|-|-|-\-\ f
 372     *-|-|-|-< | | | | | | e
 373     | | | | | *-|-|-|-/ | d
 374     r-/-|-|-|-|-/-|-|---/ c
 375     r---/-|-|-|---|-/ b
 376     r-----/-/-/---/ a
 377
 378     Ok, enough pretty graphs ;).  Here's an example of cycle
 379     detection.
 380
 381     >>> for char in ['a','b','c','d']:
 382     ...     setattr(n, char, Node(data=char))
 383     >>> n.b.append(n.a)
 384     >>> n.c.append(n.a)
 385     >>> n.d.extend([n.b, n.c])
 386     >>> n.a.append(n.d)
 387     >>> g = Graph([n.a,n.b,n.c,n.d])
 388     >>> g.check_for_cycles()
 389     Traceback (most recent call last):
 390       ...
 391     CyclicGraphError: cycle detected:
 392       a
 393       d
 394       b
 395       a
 396     """
 397     def topological_sort(self):
 398         """Algorithm from git's commit.c `sort_in_topological_order`_.
 399
 400         Ordering is tip-to-root.
 401
 402         In situations where topological sorting is ambiguous, the
 403         nodes are sorted using the inverse (since we use tip-to-root
 404         ordering) of their comparison functions (__cmp__, __lt__,
 405         ...).
 406
 407         .. _sort_in_topological_order:
 408           http://git.kernel.org/?p=git/git.git;a=blob;f=commit.c;h=731191e63bd39a89a8ea4ed0390c49d5605cdbed;hb=HEAD#l425
 409         """
 410         for node in self:
 411             node._outcount = 0
 412         for node in self:
 413             for parent in node:
 414                 parent._outcount += 1
 415         tips = sorted([node for node in self if node._outcount == 0])
 416         orig_len = len(self)
 417         del self[:]
 418         while len(tips) > 0:
 419             node = tips.pop(0)
 420             for parent in node:
 421                 parent._outcount -= 1
 422                 if parent._outcount == 0:
 423                     bisect.insort(tips, parent)
 424             node._outcount = -1
 425             self.append(node)
 426         final_len = len(self)
 427         if final_len != orig_len:
 428             raise CyclicGraphError(
 429                 '%d of %d elements not reachable from tips'
 430                 % (orig_len - final_len, orig_len))
 431
 432     def check_for_cycles(self):
 433         """Check for cyclic references.
 434         """
 435         for node in self:
 436             if node in node.ancestors():
 437                 path = node.path(node)
 438                 raise CyclicGraphError(
 439                     'cycle detected:\n  %s'
 440                     % '\n  '.join([repr(node)]+[repr(node) for node in path]))
 441
 442     def graph_rows(self, graph_row=None):
 443         """Generate a sequence of (`graph_row`, `node`) tuples.
 444
 445         Preforms :meth:`topological_sort` internally.
 446
 447         If `graph_row` is `None`, a new instance of :class:`GraphRow`
 448         is used.
 449         """
 450         if graph_row == None:
 451             graph_row = GraphRow()
 452         self.topological_sort()
 453         for node in self:
 454             graph_row.insert(node)
 455             yield (graph_row, node)
 456
 457     def ascii_graph(self, string_fn=str):
 458         """Print an ascii graph on the left with `string_fn(node)` on
 459         the right.
 460
 461         See the class docstring for example output.
 462         """
 463         graph = []
 464         for row,node in self.graph_rows():
 465             graph.append('%s %s' % (str(row), string_fn(node)))
 466         return '\n'.join(graph)