Ask Your Question
1

Getting a rooted graph from a nested list of lists

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

kcrisman gravatar image

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.

edit retag flag offensive close merge delete

1 answer

Sort by ยป oldest newest most voted
2

answered 2013-09-03 08:08:40 -0500

niles gravatar image

updated 2013-09-04 04:10:28 -0500

One way to do this would be to modify the original tree function to parse the list; another would be to build the graph directly. The second one is slightly trickier because the names of graph vertices must be unique, so you have to ensure this with some kind of global counter. Here's one version I made by writing a class to contain both the counter, the graph, and the recursive tree builder:

class ExpressionGraph():
    def __init__(self,expr):
        self.G = Graph()
        self.i = 0
        self.expr = expr
        self.root = None
        self.graph_expr(self.expr)
    def plot(self,*args,**kwds):
        #print "root is {0}".format(self.root)
        return self.G.plot(*args,layout='tree',tree_root=self.root,**kwds)
    def graph_expr(self,expr):
        try:
            operator = expr.operator()
        except AttributeError: # e.g. if expr is an integer
            operator = None

        if operator is None:
            name = "[{0}] {1}".format(self.i,expr)
            print self.i
            print "(leaf) {0}".format(expr)
            self.i += 1
            self.G.add_vertex(name)
            return name
        else:
            name = "[{0}] {1}".format(self.i,expr.operator().__name__)
            print self.i
            print "(node) {0}; {1}".format(expr,expr.operator().__name__)
            if self.i == 0:
                self.root = name
                print "  ** root is '{0}' **".format(self.root)
            self.i += 1
            new_nodes = []
            for opnd in expr.operands():
                new_nodes += [self.graph_expr(opnd)]
            self.G.add_vertex(name)
            self.G.add_edges([(name,node) for node in new_nodes])
            return name

Note that I've included some print statements so you can see how it's working:

f = 2*(x+2^x)
E = ExpressionGraph(f)

prints out

0
(node) 2*2^x + 2*x; add
  ** root is '[0] add' **
1
(node) 2*2^x; mul
2
(node) 2^x; pow
3
(leaf) 2
4
(leaf) x
5
(leaf) 2
6
(node) 2*x; mul
7
(leaf) x
8
(leaf) 2

and E.plot() plots the tree, with additional arguments passed to the underlying graph. For example:

E.plot(vertex_size=2000,vertex_colors='#ffccff')

image description

edit flag offensive delete link more

Comments

Congratulations on earning the Necromancer badge, Niles!

kcrisman gravatar imagekcrisman ( 2013-09-03 14:54:38 -0500 )edit

Now you just need it to show up as a *rooted* graph for an acceptance ;-)

kcrisman gravatar imagekcrisman ( 2013-09-03 14:55:27 -0500 )edit

oops -- forgot that! Updated now, with some other minor improvements :)

niles gravatar imageniles ( 2013-09-04 04:11:57 -0500 )edit

Interestingly, this makes it look like it's `x^2`, not `2^x`. But this really answers what I wanted!

kcrisman gravatar imagekcrisman ( 2013-09-04 07:33:01 -0500 )edit
1

Yes -- I was going to note that the numbering of the vertices is useful for non-commutative operations like pow and div.

niles gravatar imageniles ( 2013-09-04 09:42:46 -0500 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

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

Seen: 1,159 times

Last updated: Sep 04 '13