Re: pretty printing graphs

Discussion in 'Python' started by Bengt Richter, Jul 29, 2003.

  1. On Mon, 28 Jul 2003 12:13:10 -0500, John Hunter <> 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

    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
     
    Bengt Richter, Jul 29, 2003
    #1
    1. Advertising

  2. On 29 Jul 2003 02:07:14 GMT, (Bengt Richter) wrote:
    [...]
    >====< pphunter.py >==============================================

    [...]
    >class Node:

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

    should be
    --
    def showInPage(self, pageHeight=6*11, pageWidth=78):
    return '\n'.join(self.boxlines(pageHeight, pageWidth))
    --
    [...]

    Sorry.

    Regards,
    Bengt Richter
     
    Bengt Richter, Jul 29, 2003
    #2
    1. Advertising

  3. Bengt Richter

    John Hunter Guest

    >>>>> "Bengt" == Bengt Richter <> writes:

    Bengt> How about (I added a name in the first node line for
    Bengt> debugging, and boxing): (code follows output). Not tested
    Bengt> much ;-)

    Thanks Bengt - that looks great. You really should be on the payroll.

    I won't have time until tonight to wrap my head around your code, but
    I think I'll add a to_dot method to the Node class which generates dot
    output, so I can use your ascii output for day-to-day stuff, and then
    go to dot for publication quality.

    Thanks all for the suggestions,
    JDH
     
    John Hunter, Jul 29, 2003
    #3
  4. On Tue, 29 Jul 2003 08:53:27 -0500, John Hunter <> wrote:

    >>>>>> "Bengt" == Bengt Richter <> writes:

    >
    > Bengt> How about (I added a name in the first node line for
    > Bengt> debugging, and boxing): (code follows output). Not tested
    > Bengt> much ;-)
    >
    >Thanks Bengt - that looks great. You really should be on the payroll.
    >

    Email me for particulars on how to send money ;-))

    >I won't have time until tonight to wrap my head around your code, but
    >I think I'll add a to_dot method to the Node class which generates dot
    >output, so I can use your ascii output for day-to-day stuff, and then
    >go to dot for publication quality.

    If you have an interactive window with tty font with box characters, it could
    look pretty nice for "day-to-day", I think (though requiring a little more logic
    for choosing boxing and connection line characters).
    >
    >Thanks all for the suggestions,

    You're welcome. Be aware that I just copied your original post and
    vimmed at it until something emerged. It's pretty brute force, recomputing
    a lot, etc etc. And not very well factored. OTOH, it seems to work, within its limits ;-)
    It could use some sanity checks etc. though.

    BTW, also in this thread there is a version with connector lines
    called pptree.py, in case that is of interest.

    I think to make a real tool, I would design differently. Off hand IWT using a random access
    2-dimensional mutable character array as a page "canvas" to paint on would eliminate
    some of the constraints on the layout that are inherent in the way I did it in pptree.
    (I.e., hierarchical box model where any box may be contain a centered smaller
    box connected to one row of boxes underneath it, and any of those may similarly either
    be a single box or contain a smaller top box with its row of children, etc., so each box
    is only a matter of one top single box and one row of child boxes, whatever the content of
    the child boxes. Then its just a matter of dealing with the different sizes.)

    Also more abstract element definitions and drawing primitives could allow for subclassing
    for different output media like ascii, tty/boxchars, tkinter, postscript, etc.

    I'm curious as to what your actual text blocks represent...

    Regards,
    Bengt Richter
     
    Bengt Richter, Jul 29, 2003
    #4
  5. On Tue, 29 Jul 2003 10:31:51 -0500, John Hunter <> wrote:

    >>>>>> "Bengt" == Bengt Richter <> writes:

    >
    > Bengt> should be -- def showInPage(self, pageHeight=6*11,
    > Bengt> pageWidth=78): return '\n'.join(self.boxlines(pageHeight,
    > Bengt> pageWidth)) -- [...]
    >
    >I think I may have discovered another bug. In the longish example below,
    >the children of n2 are n20 and n21
    >
    > n2.children.extend([n20, n21])
    >
    >These children are the branch:
    >
    > |------------------+
    > +-------+ +-------+
    > |3 4 5 6| |6 4 5 6|
    > |3 4 5 6| |-------|
    > |-------| |1 1 1 1|
    > |1 1 1 1| +-------+
    > +-------+
    >
    >However, if you run your pprint on this example, they appear below the
    >n4 branch.
    >

    I suspect the default "page" width of 78 is insufficient. I modded your
    data to include a node names (e.g., see first two below)
    e.g.,
    >Haven't had a chance to grok the code yet -- I just came across this
    >bug when using your code on a test case for a projective clustering
    >neural network algorithm I'm implementing. The example is from Cao
    >and Wu, Neural Networks 15(2002) 105-120.
    >
    > http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6T08-43T2MC4-1&_user=5745&_handle=W-WA-A-A-AD-MsSAYZA-UUW-AUCEZCZEBD-AZZEEDDUV-AD-U&_fmt=full&_coverDate=01%2F31%2F2002&_rdoc=10&_orig=browse&_srch=%23toc%234856%232002%23999849998%23290257!&_cdi=4856&view=c&_acct=C000001358&_version=1&_urlVersion=0&_userid=5745&md5=61f59ff40e082d56154538b436b0010e
    >
    >
    >def test3():

    #> n = Node(TextBox("""1 2 3 4
    n = Node(TextBox("""n
    1 2 3 4
    >2 3 4 5
    >3 4 5 6
    >4 5 6 7
    >6 7 8 9
    >1 2 3 4
    >3 4 5 6
    >2 3 4 5
    >6 4 5 6
    >4 2 3 1
    >6 7 1 2
    >4 5 6 7
    >-------
    >0 0 0 0
    >"""))
    >

    #> n0 = Node(TextBox("""1 2 3 4
    n0 = Node(TextBox("""n0
    1 2 3 4
    >1 2 3 4
    >4 2 3 1
    >-------
    >0 1 1 0
    >"""))
    >

    [...]
    > n4.children.extend([n40, n41])
    >
    > print n

    To specify a page wide enough here, try

    print n.showInPage(35, 90)

    With the name-modded data, I got

    [11:56] C:\pywk\clp>pptree_t3.py 35 90

    +-------+
    | n|
    |1 2 3 4|
    |2 3 4 5|
    |3 4 5 6|
    |4 5 6 7|
    |6 7 8 9|
    |1 2 3 4|
    |3 4 5 6|
    |2 3 4 5|
    |6 4 5 6|
    |4 2 3 1|
    |6 7 1 2|
    |4 5 6 7|
    |-------|
    |0 0 0 0|
    +-------+
    +---------------+----------------|---------------+----------------+
    +-------+ +-------+ +-------+ +-------+ +-------+
    | n0| | n1| | n2| | n3| | n4|
    |1 2 3 4| |2 3 4 5| |3 4 5 6| |4 5 6 7| |6 7 8 9|
    |1 2 3 4| |2 3 4 5| |3 4 5 6| |4 5 6 7| |6 7 1 2|
    |4 2 3 1| |-------| |6 4 5 6| |-------| |-------|
    |-------| |1 1 1 1| |-------| |1 1 1 1| |1 1 0 0|
    |0 1 1 0| +-------+ |0 1 1 1| +-------+ +-------+
    +-------+ +-------+ +----|----+
    +----|----+ +----|----+ +-------+ +-------+
    +-------+ +-------+ +-------+ +-------+ | n40| | n41|
    | n00| | n01| | n20| | n21| |6 7 8 9| |6 7 1 2|
    |1 2 3 4| |4 2 3 1| |3 4 5 6| |6 4 5 6| |-------| |-------|
    |1 2 3 4| |-------| |3 4 5 6| |-------| |1 1 1 1| |1 1 1 1|
    |-------| |1 1 1 1| |-------| |1 1 1 1| +-------+ +-------+
    |1 1 1 1| +-------+ |1 1 1 1| +-------+
    +-------+ +-------+

    I guess it would be good to make it self-expanding if the default page is too small, or raise
    an informative exception.

    Regards,
    Bengt Richter
     
    Bengt Richter, Jul 29, 2003
    #5
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Craig Duffield

    Pretty Printing

    Craig Duffield, Feb 26, 2004, in forum: Java
    Replies:
    0
    Views:
    376
    Craig Duffield
    Feb 26, 2004
  2. Christian Ashby

    Pretty Printing / Code formatting for JSPs

    Christian Ashby, Aug 20, 2004, in forum: Java
    Replies:
    0
    Views:
    374
    Christian Ashby
    Aug 20, 2004
  3. Andy Fish

    MXXMLWriter for pretty printing

    Andy Fish, Oct 28, 2003, in forum: XML
    Replies:
    0
    Views:
    1,813
    Andy Fish
    Oct 28, 2003
  4. Scherer, Bill

    Re: pretty printing graphs

    Scherer, Bill, Jul 28, 2003, in forum: Python
    Replies:
    3
    Views:
    527
    Michele Simionato
    Jul 29, 2003
  5. David
    Replies:
    5
    Views:
    322
    bsneddon
    Jul 8, 2007
Loading...

Share This Page