pretty printing graphs

[Bengt Richter]

On Mon, 28 Jul 2003 12:13:10 -0500, John Hunter <jdhunter at ace.bsd.uchicago.edu> wrote:

>
>I have a tree structure (directed acyclic graph), where each node can
>represent itself as a multi-line string that is not very wide (eg, 10
>chars per line).  I would like to print the graph like
>
>        C
>   C1        C2
>C1a  C1b   C2a   C2b
>
The outline format is not good? I.e.,

C
  C1
    C1a
    C1b
  C2
    C2a
    C2b

An outline would be simple to print recursively.
[... snip code etc ...]
>
>This does part of the work, printing the child nodes on the same rows,
>but doesn't the hierarchical part very well.  What I would like is
>something like this:
>
>			 1  2  3  0  
>			 1  2  3  4 
>			 1  2  1  5 
>			 1  2  1  1 
>			 4  3  2  2 
>			 4  3  2  7 
>			 2  3  2  3 
>			 2  3  2  9
> 
>	       1  2  3  0        4  3  2  2      
>	       1  2  3  4        4  3  2  7      
>	       1  2  1  5        2  3  2  3      
>	       1  2  1  1        2  3  2  9      
>	       ----------        ----------      
>	       1  1  0  0        0  1  1  0      
>
>
>1  2  1  5    1  2  3  0          2  3  2  3      4  3  2  2      
>1  2  1  1    1  2  3  4          2  3  2  9      4  3  2  7      
>----------    ----------          ----------      ----------      
>1  1  1  0    1  1  1  0          1  1  1  0      1  1  1  0      
>
>
>
How about (I added a name in the first node line for debugging, and boxing):
(code follows output). Not tested much ;-)

[19:04] C:\pywk\clp>python pphunter.py
                                 +----------+
                                 |        n0|
                                 |1  2  3  0|
                                 |1  2  3  4|
                                 |1  2  1  5|
                                 |1  2  1  1|
                                 |4  3  2  2|
                                 |4  3  2  7|
                                 |2  3  2  3|
                                 |2  3  2  9|
                                 +----------+

              +----------+                           +----------+
              |        n1|                           |        n2|
              |1  2  3  0|                           |4  3  2  2|
              |1  2  3  4|                           |4  3  2  7|
              |1  2  1  5|                           |2  3  2  3|
              |1  2  1  1|                           |2  3  2  9|
              |----------|                           |----------|
              |1  1  0  0|                           |0  1  1  0|
              +----------+                           +----------+

     +----------+       +----------+        +----------+       +----------+
     |       n1a|       |       n1b|        |       n2a|       |       n2b|
     |1  2  1  5|       |1  2  3  0|        |2  3  2  3|       |4  3  2  2|
     |1  2  1  1|       |1  2  3  4|        |2  3  2  9|       |4  3  2  7|
     |----------|       |----------|        |----------|       |----------|
     |1  1  1  0|       |1  1  1  0|        |1  1  1  0|       |1  1  1  0|
     +----------+       +----------+        +----------+       +----------+


====< pphunter.py >==============================================
from __future__ import division, generators

def enumerate(seq):
    "Waiting for python 2.3"
    for i in range(len(seq)):
        yield i, seq[i]

class TextBox:
    def __init__(self, text):
        self.text = text
        lines = text.splitlines()
        self.bb = len(lines)+2, max(map(len, lines))+2 # rows,cols bounding box
    def __str__(self):
        return self.text 

class Node:
    PageHeight = 6*11; PageWidth = 78
    def __repr__(self): return '<Node w/ text %r ...>'%self.textBox.text.splitlines()[0]
    def treebb(self):  # tree bb incl this node
        childMaxHeight, childTotWidth = 0, 0
        for child in self.children:
            h, w = child.treebb()
            childMaxHeight = max(childMaxHeight, h)
            childTotWidth += w
        ret = childMaxHeight+self.textBox.bb[0], max(childTotWidth, self.textBox.bb[1])
        return ret
    def __init__(self, textBox):
        self.textBox = textBox
        self.children = []

    def boxlines(node, boxHeight, boxWidth):
        oh, ow = node.textBox.bb    # this node top text box bb
        th, tw = node.treebb()      # minimal child tree bb incl text box at top
        
        render = ['']*boxHeight
        ofmt = '|%%%ds|'% (ow-2)
        render[0] = ('+'+'-'*(ow-2)+'+').center(boxWidth)
        iLine=1
        for line in node.textBox.text.splitlines():
            render[iLine] = (ofmt%line).center(boxWidth)
            iLine += 1
        render[iLine] = render[0]
        iLine += 1
        if node.children:
            availSepSpaces = boxWidth - tw
            nch = len(node.children)
            sep = nch>1 and availSepSpaces//nch or 0
            childBoxes = []
            for child in node.children:
                chh, chw = child.treebb()
                childBoxes.append(child.boxlines(boxHeight-oh-1, sep and chw+sep or boxWidth))
            cbhs = map(len, childBoxes); assert max(cbhs)==min(cbhs) # all child boxes same ht
            for iChildline in xrange(cbhs[0]):
                iLine += 1
                render[iLine] = ''.join(
                    [childBox[iChildline] for childBox in childBoxes]
                ).center(boxWidth)

        for iLine in range(boxHeight):
            if not render[iLine]: render[iLine] = ' '*boxWidth
        return render
        
    def __str__(self):
        return '\n'.join(self.boxlines(self.PageHeight, self.PageWidth))

    def showInPage(self, pageHeight=6*11, pageWidth=78):
        return '\n'.join(self.boxlines(PageHeight, PageWidth))

def test():
    n0 = Node(TextBox("""n0
1  2  3  0
1  2  3  4
1  2  1  5
1  2  1  1
4  3  2  2
4  3  2  7
2  3  2  3
2  3  2  9
"""))

    n1 = Node(TextBox("""n1
1  2  3  0
1  2  3  4
1  2  1  5
1  2  1  1
----------
1  1  0  0
"""))

    n2 = Node(TextBox("""n2
4  3  2  2
4  3  2  7
2  3  2  3
2  3  2  9
----------
0  1  1  0
"""))

    n1a = Node(TextBox("""n1a
1  2  1  5
1  2  1  1
----------
1  1  1  0
"""))

    n1b = Node(TextBox("""n1b
1  2  3  0
1  2  3  4
----------
1  1  1  0
"""))

    n2a = Node(TextBox("""n2a
2  3  2  3
2  3  2  9
----------
1  1  1  0
"""))

    n2b = Node(TextBox("""n2b
4  3  2  2
4  3  2  7
----------
1  1  1  0
"""))

    n0.children.extend([n1, n2])
    n1.children.extend([n1a, n1b])
    n2.children.extend([n2a, n2b])

    print n0

if __name__ == '__main__': test()
=================================================================

Regards,
Bengt Richter