hooke/util/graph.py

   1 # Copyright (C) 2010 W. Trevor King <wking@drexel.edu>
   2 #
   3 # This file is part of Hooke.
   4 #
   5 # Hooke is free software: you can redistribute it and/or
   6 # modify it under the terms of the GNU Lesser General Public
   7 # License as published by the Free Software Foundation, either
   8 # version 3 of the License, or (at your option) any later version.
   9 #
  10 # Hooke is distributed in the hope that it will be useful,
  11 # but WITHOUT ANY WARRANTY; without even the implied warranty of
  12 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13 # GNU Lesser General Public License for more details.
  14 #
  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/>.
  18
  19 """Define :class:`Graph`, a directed, acyclic graph structure.
  20 :class:`Graph`\s are composed of :class:`Node`\s, also defined by this
  21 module.
  22 """
  23
  24 import bisect
  25
  26 class CyclicGraphError (ValueError):
  27     pass
  28
  29 class Node (list):
  30     """A node/element in a graph.
  31
  32     Contains a list of the node's parents, and stores the node's
  33     `data`.
  34
  35     Examples
  36     --------
  37
  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')
  42     >>> str(d)
  43     'd'
  44
  45     We can list all of a node's ancestors.
  46
  47     >>> print [node for node in d.ancestors()]
  48     [b, c, a]
  49     >>> print [node for node in d.ancestors(depth_first=True)]
  50     [b, a, c]
  51
  52     Ancestors works with cycles.
  53
  54     >>> a.append(d)
  55     >>> print [node for node in d.ancestors()]
  56     [b, c, a, d]
  57
  58     We can find the cycle path.
  59
  60     >>> print d.parent_path(d)
  61     [b, a, d]
  62
  63     After a run through :meth:`Graph.set_children`, we can also
  64     list children
  65
  66     >>> g = Graph([a, b, c, d])
  67     >>> g.set_children()
  68     >>> print a.children
  69     [b, c]
  70
  71     And descendents.
  72
  73     >>> print [node for node in a.descendents(depth_first=True)]
  74     [b, d, a, c]
  75     """
  76     def __init__(self, parents=[], data=None):
  77         list.__init__(self, parents)
  78         self.data = data
  79         self.children = []
  80
  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
  95
  96     def __str__(self):
  97         return str(self.data)
  98     def __repr__(self):
  99         return self.__str__()
 100
 101     def traverse(self, next, depth_first=False):
 102         """Iterate through all nodes returned by `next(node)`.
 103
 104         Will only yield each traversed node once, even in the case of
 105         diamond inheritance, etc.
 106
 107         Breadth first by default.  Set `depth_first==True` for a
 108         depth first search.
 109         """
 110         stack = list(next(self))
 111         popped = []
 112         while len(stack) > 0:
 113             node = stack.pop(0)
 114             if node in popped:
 115                 continue
 116             popped.append(node)
 117             yield node
 118             if depth_first == True:
 119                 for target in reversed(next(node)):
 120                     stack.insert(0, target)
 121             else:
 122                 stack.extend(next(node))
 123
 124     def ancestors(self, depth_first=False):
 125         """Generate all ancestors.
 126
 127         This is a small wrapper around :meth:`traverse`.
 128         """
 129         next = lambda node : node  # list node's parents
 130         for node in self.traverse(next=next, depth_first=depth_first):
 131             yield node
 132
 133     def descendents(self, depth_first=False):
 134         """Generate all decendents.
 135
 136         This is a small wrapper around :meth:`traverse`.
 137         """
 138         next = lambda node : node.children
 139         for node in self.traverse(next=next, depth_first=depth_first):
 140             yield node
 141
 142     def path(self, next, node):
 143         """Return the shortest list of nodes connecting `self` to
 144         `node` via `next(node)`.
 145         """
 146         if node in self:
 147             return [node]
 148         stack = list(next(self))
 149         paths = dict((id(n), [n]) for n in stack)
 150         while len(stack) > 0:
 151             n = stack.pop(0)
 152             n_path = paths[id(n)]
 153             for target in next(n):
 154                 if id(target) in paths:
 155                     continue
 156                 t_path = list(n_path)
 157                 t_path.append(target)
 158                 if id(target) == id(node):
 159                     return t_path
 160                 stack.append(target)
 161                 paths[id(target)] = t_path
 162
 163     def parent_path(self, node):
 164         """Return the shortest list of nodes connecting `self` to
 165         its parent `node`.
 166
 167         This is a small wrapper around :meth:`path`.
 168         """
 169         next = lambda node : node  # list node's parents
 170         return self.path(next, node)
 171
 172     def child_path(self, node):
 173         """Return the shortest list of nodes connecting `self` to
 174         its child `node`.
 175
 176         This is a small wrapper around :meth:`path`.
 177         """
 178         next = lambda node : node.children
 179         return self.path(next, node)
 180
 181
 182 class GraphRow (object):
 183     """Represent the state of a single row in a graph.
 184
 185     Generated by :class:`GraphRowGenerator`, printed with
 186     :class:`GraphRowPrinter`.
 187
 188     :attr:`node` is the active node and :attr:`active` is its branch
 189     column index.  :attr:`width` is the number of current branch
 190     columns.
 191
 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
 197     this row.
 198     """
 199     def __init__(self, node, active=-1, dead=None, inherited=None, born=None,
 200                  tip_to_root=False):
 201         self.node = node
 202         self.active = active
 203         if dead == None:
 204             dead = []
 205         self.dead = dead
 206         if inherited == None:
 207             inherited = []
 208         self.inherited = inherited
 209         if born == None:
 210             born = []
 211         self.born = born
 212         self.tip_to_root = tip_to_root
 213
 214 class GraphRowPrinter (object):
 215     """Customizable printing for :class:`GraphRow`.
 216
 217     The string rendering can be customized by changing :attr:`chars`.
 218     Control over the branch columns:
 219
 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     ================= ===========================================
 226
 227     Branch columns are seperated by separator columns:
 228
 229     ================= =======================================================
 230     `sep: split/join` separate split/join branch columns from the active node
 231     `sep: default`    separate all remaining branch columns
 232     ================= =======================================================
 233     """
 234     def __init__(self, chars=None):
 235         if chars == None:
 236             chars = {
 237                 'node: both tip and root': 'b',
 238                 'node: root': 'r',
 239                 'node: tip': 't',
 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': '/',
 247                 'run: blank': ' ',
 248                 'run: connected': '|',
 249                 'sep: split/join': '-',
 250                 'sep: default': ' ',
 251                 }
 252         self.chars = chars
 253     def __call__(self, graph_row):
 254         """Render the :class:`GraphRow` instance `graph_row` as a
 255         string.
 256         """
 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
 262                             max(dead+[-1]))
 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]))
 267         string = []
 268         for i in range(max_col + 1):
 269             # Get char, the node or branch column character.
 270             if i == graph_row.active:
 271                 if len(born) == 0:
 272                     if len(dead) == 0:
 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']
 279                 elif len(dead) == 0:
 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']
 285                 else:
 286                     char = self.chars['node: regular']
 287             elif i in born:
 288                 if i in dead: # born and died
 289                     if i < graph_row.active:
 290                         char = self.chars[
 291                             'split/join: born and died left of active']
 292                     else:
 293                         char = self.chars[
 294                             'split/join: born and died right of active']
 295                 else: # just born
 296                     if i < graph_row.active:
 297                         char = self.chars['split/join: born left of active']
 298                     else:
 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']
 303                 else:
 304                     char = self.chars['split/join: died right of active']
 305             elif i in inherited:
 306                 char = self.chars['run: connected']
 307             else:
 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']
 312             else:
 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
 318
 319 class GraphRowGenerator (list):
 320     """A :class:`GraphRow` generator.
 321
 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::
 325
 326         tip_to_root = True
 327         g = GraphRowGenerator(tip_to_root=tip_to_root)
 328         p = GraphRowPrinter(tip_to_root=tip_to_root)
 329         for node in nodes:
 330             g.insert(node)
 331             print p(g[-1])
 332
 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
 339     sentence.
 340     """
 341     def __init__(self, tip_to_root=False):
 342         list.__init__(self)
 343         self.tip_to_root = tip_to_root
 344     def insert(self, node):
 345         """Add a new node to the graph.
 346
 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).
 350
 351         If `tip_to_root==False`, nodes must be inserted before any
 352         of their children.
 353         """
 354         if len(self) == 0:
 355             previous = GraphRow(node=None, active=-1)
 356         else:
 357             previous = self[-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))
 369             else:
 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
 382         self.append(current)
 383
 384
 385 class Graph (list):
 386     """A directed, acyclic graph structure.
 387
 388     Contains methods for sorting and printing graphs.
 389
 390     Examples
 391     --------
 392
 393     >>> class Nodes (object): pass
 394     >>> n = Nodes()
 395     >>> for char in ['a','b','c','d','e','f','g','h','i']:
 396     ...     setattr(n, char, Node(data=char))
 397     >>> n.b.append(n.a)
 398     >>> n.c.append(n.a)
 399     >>> n.d.append(n.a)
 400     >>> n.e.extend([n.b, n.c, n.d])
 401     >>> n.f.append(n.e)
 402     >>> n.g.append(n.e)
 403     >>> n.h.append(n.e)
 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()
 410     r-\-\ a
 411     | | * b
 412     | * | c
 413     * | | d
 414     *-<-< e
 415     | | * f
 416     | * | g
 417     * | | h
 418     t-/-/ i
 419     >>> print g.ascii_graph(tip_to_root=True)
 420     t-\-\ i
 421     | | * h
 422     | * | g
 423     * | | f
 424     *-<-< e
 425     | | * d
 426     | * | c
 427     * | | b
 428     r-/-/ a
 429
 430     >>> for char in ['a','b','c','d','e','f','g','h']:
 431     ...     setattr(n, char, Node(data=char))
 432     >>> n.b.append(n.a)
 433     >>> n.c.append(n.b)
 434     >>> n.d.append(n.a)
 435     >>> n.e.append(n.d)
 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)
 441     t-\ h
 442     | *-\ g
 443     | | *-\ f
 444     | * | | e
 445     | *-|-/ d
 446     * | | c
 447     *-|-/ b
 448     r-/ a
 449
 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)
 454     ...     n.i.append(nx)
 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)
 457     t-\-\-\-\-\-\-\ i
 458     | | | | | | | r h
 459     | | | | | | r g
 460     | | | | | r f
 461     | | | | r e
 462     | | | r d
 463     | | r c
 464     | r b
 465     r a
 466
 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)
 471     ...     nx.append(n.a)
 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)
 474     t i
 475     | t h
 476     | | t g
 477     | | | t f
 478     | | | | t e
 479     | | | | | t d
 480     | | | | | | t c
 481     | | | | | | | t b
 482     r-/-/-/-/-/-/-/ a
 483
 484     >>> for char in ['a','b','c','d','e','f','g','h','i']:
 485     ...     setattr(n, char, Node(data=char))
 486     >>> n.d.append(n.a)
 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)
 494     t-\-\-\ i
 495     | | | | t-\-\-\ h
 496     | | | *-|-|-|-<-\ g
 497     | | | | | | | | *-\-\ f
 498     | | | | | | | *-|-|-< e
 499     | | | | | | *-|-|-/ | d
 500     | | r-|-|-/-|-|-/---/ c
 501     | r---/ |   | | b
 502     r-------/---/-/ a
 503
 504     Ok, enough pretty graphs ;).  Here's an example of cycle
 505     detection.
 506
 507     >>> for char in ['a','b','c','d']:
 508     ...     setattr(n, char, Node(data=char))
 509     >>> n.b.append(n.a)
 510     >>> n.c.append(n.a)
 511     >>> n.d.extend([n.b, n.c])
 512     >>> n.a.append(n.d)
 513     >>> g = Graph([n.a,n.b,n.c,n.d])
 514     >>> g.check_for_cycles()
 515     Traceback (most recent call last):
 516       ...
 517     CyclicGraphError: cycle detected:
 518       a
 519       d
 520       b
 521       a
 522     """
 523     def set_children(self):
 524         """Fill out each node's :attr:`Node.children` list.
 525         """
 526         for node in self:
 527             for parent in node:
 528                 if node not in parent.children:
 529                     parent.children.append(node)
 530
 531     def topological_sort(self, tip_to_root=False):
 532         """Algorithm from git's commit.c `sort_in_topological_order`_.
 533
 534         Default ordering is root-to-tip.  Set `tip_to_root=True` for
 535         tip-to-root.
 536
 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.
 541
 542         .. _sort_in_topological_order:
 543           http://git.kernel.org/?p=git/git.git;a=blob;f=commit.c;h=731191e63bd39a89a8ea4ed0390c49d5605cdbed;hb=HEAD#l425
 544         """
 545         # sort tip-to-root first, then reverse if neccessary
 546         for node in self:
 547             node._outcount = 0
 548         for node in self:
 549             for parent in node:
 550                 parent._outcount += 1
 551         tips = sorted([node for node in self if node._outcount == 0])
 552         orig_len = len(self)
 553         del self[:]
 554         while len(tips) > 0:
 555             node = tips.pop(0)
 556             for parent in node:
 557                 parent._outcount -= 1
 558                 if parent._outcount == 0:
 559                     bisect.insort(tips, parent)
 560             node._outcount = -1
 561             self.append(node)
 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:
 568             self.reverse()
 569
 570     def check_for_cycles(self):
 571         """Check for cyclic references.
 572         """
 573         for node in self:
 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]))
 579
 580     def graph_rows(self, tip_to_root=False):
 581         """Generate a sequence of (`graph_row`, `node`) tuples.
 582
 583         Preforms :meth:`set_children` and :meth:`topological_sort`
 584         internally.
 585         """
 586         graph_row_generator = GraphRowGenerator(tip_to_root=tip_to_root)
 587         self.set_children()
 588         self.topological_sort(tip_to_root=tip_to_root)
 589         for node in self:
 590             graph_row_generator.insert(node)
 591             yield (graph_row_generator[-1], node)
 592
 593     def ascii_graph(self, graph_row_printer=None, string_fn=str,
 594                     tip_to_root=False):
 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.
 598
 599         See the class docstring for example output.
 600         """
 601         if graph_row_printer == None:
 602             graph_row_printer = GraphRowPrinter()
 603         graph = []
 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)