hooke/util/graph.py

   1 # COPYRIGHT
   2
   3 """Define :class:`Graph`, a directed, acyclic graph structure.
   4 :class:`Graph`\s are composed of :class:`Node`\s, also defined by this
   5 module.
   6 """
   7
   8 import bisect
   9
  10 class CyclicGraphError (ValueError):
  11     pass
  12
  13 class Node (list):
  14     """A node/element in a graph.
  15
  16     Contains a list of the node's parents, and stores the node's
  17     `data`.
  18
  19     Examples
  20     --------
  21
  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')
  26     >>> str(d)
  27     'd'
  28
  29     We can list all of a node's ancestors.
  30
  31     >>> print [node for node in d.ancestors()]
  32     [b, c, a]
  33     >>> print [node for node in d.ancestors(depth_first=True)]
  34     [b, a, c]
  35
  36     Ancestors works with cycles.
  37
  38     >>> a.append(d)
  39     >>> print [node for node in d.ancestors()]
  40     [b, c, a, d]
  41
  42     We can find the cycle path.
  43
  44     >>> print d.path(d)
  45     [b, a, d]
  46     """
  47     def __init__(self, parents=[], data=None):
  48         list.__init__(self, parents)
  49         self.data = data
  50
  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
  65
  66     def __str__(self):
  67         return str(self.data)
  68     def __repr__(self):
  69         return self.__str__()
  70
  71     def ancestors(self, depth_first=False):
  72         """Generate all ancestors.
  73
  74         Will only yield each ancestor once, even in the case of
  75         diamond inheritance, etc.
  76
  77         Breadth first by default.
  78         """
  79         stack = list(self)
  80         popped = []
  81         while len(stack) > 0:
  82             node = stack.pop(0)
  83             if node in popped:
  84                 continue
  85             popped.append(node)
  86             yield node
  87             if depth_first == True:
  88                 for parent in reversed(node):
  89                     stack.insert(0, parent)
  90             else:
  91                 stack.extend(node)
  92     def path(self, node):
  93         """Return the shortest list of parents connecting `self` to
  94         `node`.
  95         """
  96         if node in self:
  97             return [node]
  98         stack = list(self)
  99         paths = dict((id(n), [n]) for n in stack)
 100         while len(stack) > 0:
 101             n = stack.pop(0)
 102             n_path = paths[id(n)]
 103             for parent in n:
 104                 if id(parent) in paths:
 105                     continue
 106                 p_path = list(n_path)
 107                 p_path.append(parent)
 108                 if id(parent) == id(node):
 109                     return p_path
 110                 stack.append(parent)
 111                 paths[id(parent)] = p_path
 112
 113 class _GraphRowEntry (list):
 114     """A node in the graph with outstanding children.
 115
 116     `columns` is a list of the indexes of outstanding columns which
 117     will eventually attach to those children.
 118     """
 119     def __init__(self, node, columns=[]):
 120         list.__init__(self, columns)
 121         self.node = node
 122
 123 class GraphRow (list):
 124     """A graph row generator.
 125
 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
 129     calls::
 130
 131         g = GraphRow()
 132         for node in nodes:
 133             g.insert(node)
 134             print str(g)
 135
 136     The string rendering can be cusomized by changing `g.chars`.
 137     Control over the branch columns:
 138
 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     ================= ===========================================
 145
 146     Branch columns are seperated by separator columns:
 147
 148     ================= =======================================================
 149     `sep: split/join` separate split/join branch columns from the active node
 150     `sep: default`    separate all remaining branch columns
 151     ================= =======================================================
 152
 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
 158     printed).
 159     """
 160     def __init__(self):
 161         list.__init__(self)
 162         self._width = 0
 163         self._last_width = 0
 164         self._old_dead = []
 165         self._next_old_dead = []
 166         self.chars = {
 167             'node: both tip and root': 'b',
 168             'node: root': 'r',
 169             'node: tip': 't',
 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': '/',
 177             'run: blank': ' ',
 178             'run: connected': '|',
 179             'sep: split/join': '-',
 180             'sep: default': ' ',
 181             }
 182     def insert(self, node):
 183         """Add a new node to the graph.
 184
 185         Nodes should be inserted in tip-to-root topological order
 186         (i.e. node must be inserted before any of its parents).
 187         """
 188         self._node = node
 189         self._last_width = self._width
 190         self._old_dead = self._next_old_dead
 191         self._born = []
 192         self._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
 200         for e in self:
 201             if len(e) == 0:
 202                 exhausted.append(e)
 203         for e in exhausted:
 204             self.remove(e)
 205         self._dead.sort()
 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]
 215         if len(node) == 0:
 216             self._next_old_dead.insert(0, self._active)
 217
 218     def __str__(self):
 219         """Render the current line of the graph as a string.
 220         """
 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)
 228         string = []
 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']
 234                     else:
 235                         char = self.chars['node: root']
 236                 elif len(self._children) == 0:
 237                     char = self.chars['node: tip']
 238                 else:
 239                     char = self.chars['node: regular']
 240             elif i in self._born:
 241                 if i in self._dead:
 242                     if i < self._active:
 243                         char = self.chars[
 244                             'split/join: born and died left of active']
 245                     else:
 246                         char = self.chars[
 247                             'split/join: born and died right of active']
 248                 else:
 249                     if i < self._active:
 250                         char = self.chars['split/join: born left of active']
 251                     else:
 252                         char = self.chars['split/join: born right of active']
 253             elif i in self._dead:
 254                 if i < self._active:
 255                     char = self.chars['split/join: died left of active']
 256                 else:
 257                     char = self.chars['split/join: died right of active']
 258             elif i in self._old_dead:
 259                 char = self.chars['run: blank']
 260             else:
 261                 char = self.chars['run: connected']
 262             if i < left_connect or i >= right_connect:
 263                 sep = self.chars['sep: default']
 264             else:
 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
 270
 271 class Graph (list):
 272     """A directed, acyclic graph structure.
 273
 274     Contains methods for sorting and printing graphs.
 275
 276     Examples
 277     --------
 278
 279     >>> class Nodes (object): pass
 280     >>> n = Nodes()
 281     >>> for char in ['a','b','c','d','e','f','g','h','i']:
 282     ...     setattr(n, char, Node(data=char))
 283     >>> n.b.append(n.a)
 284     >>> n.c.append(n.a)
 285     >>> n.d.append(n.a)
 286     >>> n.e.extend([n.b, n.c, n.d])
 287     >>> n.f.append(n.e)
 288     >>> n.g.append(n.e)
 289     >>> n.h.append(n.e)
 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()
 296     t-\-\ i
 297     * | | h
 298     | * | g
 299     | | * f
 300     *-<-< e
 301     * | | d
 302     | * | c
 303     | | * b
 304     r-/-/ a
 305
 306     >>> for char in ['a','b','c','d','e','f','g','h']:
 307     ...     setattr(n, char, Node(data=char))
 308     >>> n.b.append(n.a)
 309     >>> n.c.append(n.b)
 310     >>> n.d.append(n.a)
 311     >>> n.e.append(n.d)
 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()
 317     t-\ h
 318     *-|-\ g
 319     *-|-|-\ f
 320     | | * | e
 321     *-|-/ | d
 322     | *   | c
 323     | *---/ b
 324     r-/ a
 325
 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)
 330     ...     n.i.append(nx)
 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()
 333     t-\-\-\-\-\-\-\ i
 334     r | | | | | | | h
 335     r-/ | | | | | | g
 336     r---/ | | | | | f
 337     r-----/ | | | | e
 338     r-------/ | | | d
 339     r---------/ | | c
 340     r-----------/ | b
 341     r-------------/ a
 342
 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)
 347     ...     nx.append(n.a)
 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()
 350     t i
 351     | t h
 352     | | t g
 353     | | | t f
 354     | | | | t e
 355     | | | | | t d
 356     | | | | | | t c
 357     | | | | | | | t b
 358     r-/-/-/-/-/-/-/ a
 359
 360     >>> for char in ['a','b','c','d','e','f','g','h','i']:
 361     ...     setattr(n, char, Node(data=char))
 362     >>> n.d.append(n.a)
 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()
 370     t-\-\-\ i
 371     | | | | t-\-\-\ h
 372     *-|-|-|-<-|-|-|-\ g
 373     *-|-|-|-|-|-|-|-|-\-\ f
 374     *-|-|-|-< | | | | | | e
 375     | | | | | *-|-|-|-/ | d
 376     r-/-|-|-|-|-/-|-|---/ c
 377     r---/-|-|-|---|-/ b
 378     r-----/-/-/---/ a
 379
 380     Ok, enough pretty graphs ;).  Here's an example of cycle
 381     detection.
 382
 383     >>> for char in ['a','b','c','d']:
 384     ...     setattr(n, char, Node(data=char))
 385     >>> n.b.append(n.a)
 386     >>> n.c.append(n.a)
 387     >>> n.d.extend([n.b, n.c])
 388     >>> n.a.append(n.d)
 389     >>> g = Graph([n.a,n.b,n.c,n.d])
 390     >>> g.check_for_cycles()
 391     Traceback (most recent call last):
 392       ...
 393     CyclicGraphError: cycle detected:
 394       a
 395       d
 396       b
 397       a
 398     """
 399     def topological_sort(self):
 400         """Algorithm from git's commit.c `sort_in_topological_order`_.
 401
 402         Ordering is tip-to-root.
 403
 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__,
 407         ...).
 408
 409         .. _sort_in_topological_order:
 410           http://git.kernel.org/?p=git/git.git;a=blob;f=commit.c;h=731191e63bd39a89a8ea4ed0390c49d5605cdbed;hb=HEAD#l425
 411         """
 412         for node in self:
 413             node._outcount = 0
 414         for node in self:
 415             for parent in node:
 416                 parent._outcount += 1
 417         tips = sorted([node for node in self if node._outcount == 0])
 418         orig_len = len(self)
 419         del self[:]
 420         while len(tips) > 0:
 421             node = tips.pop(0)
 422             for parent in node:
 423                 parent._outcount -= 1
 424                 if parent._outcount == 0:
 425                     bisect.insort(tips, parent)
 426             node._outcount = -1
 427             self.append(node)
 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))
 433
 434     def check_for_cycles(self):
 435         """Check for cyclic references.
 436         """
 437         for node in self:
 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]))
 443
 444     def graph_rows(self, graph_row=None):
 445         """Generate a sequence of (`graph_row`, `node`) tuples.
 446
 447         Preforms :meth:`topological_sort` internally.
 448
 449         If `graph_row` is `None`, a new instance of :class:`GraphRow`
 450         is used.
 451         """
 452         if graph_row == None:
 453             graph_row = GraphRow()
 454         self.topological_sort()
 455         for node in self:
 456             graph_row.insert(node)
 457             yield (graph_row, node)
 458
 459     def ascii_graph(self, string_fn=str):
 460         """Print an ascii graph on the left with `string_fn(node)` on
 461         the right.
 462
 463         See the class docstring for example output.
 464         """
 465         graph = []
 466         for row,node in self.graph_rows():
 467             graph.append('%s %s' % (str(row), string_fn(node)))
 468         return '\n'.join(graph)