Ask Your Question

Revision history [back]

click to hide/show revision 1
initial version

asked 2012-12-06 15:36:07 -0500

kcrisman gravatar image

Getting a rooted graph from a nested list of lists

At Trac 9329, a very simple expression tree walker is defined.

def tree(expr):
    if expr.operator() is None:
        return expr
    else:
        return [expr.operator()]+map(tree,expr.operands())

This gives a nested list of lists, like

sage: tree(2*(x+2^x))
[<built-in function add>, [<built-in function mul>, [<built-in function pow>, 2, x], 2], 
    [<built-in function mul>, x, 2]]

I'm trying to build a similar walker which would (roughly speaking) give the following dictionary which I could plot as a tree.

Graph({'add':['mul-lev1-1','mul-lev1-2'],'mul-lev1-1':['pow-lev2-1','2-lev2-1'],
    'pow-lev2-1':['2-lev3','x-lev3'],'mul-lev1-2':['x-lev2','2-lev2-2']}).show(
    layout='tree',tree_root='add')

Binary Tree of this expression

Naturally, the same element could appear as many times as one liked in any level of the tree, so the naming scheme probably would be overly ponderous... but I'm wondering whether anyone who understands Converter better than I do (which isn't saying much) can get around the problem that dictionaries of dictionaries don't work here in any case to build a nice tree walker that can make such graph-able dictionaries. 'Cause doing it by hand is not particularly fun.