Ask Your Question

# 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') 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 close merge delete

## 1 Answer

Sort by » oldest newest most voted

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 ' 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') more

## Comments

Congratulations on earning the Necromancer badge, Niles!

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

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

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

1

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

## Your Answer

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

Add Answer

## Stats

Asked: 2012-12-06 22:36:07 +0200

Seen: 1,657 times

Last updated: Sep 04 '13