Ask Your Question
1

call graph of a recursive function

asked 2013-08-06 06:08:58 -0500

pang gravatar image

updated 2015-02-24 04:23:41 -0500

A colleague asked if I could write some code to show the call graph of a recursive function. I came up with this:

def grafo_llamadas(f):
    class G(object):
        def __init__(self, f):
            self.f=f
            self.stack = []
            self.g   = DiGraph()
        def __call__(self, *args):
            if self.stack:
                sargs = ','.join(str(a) for a in args)
                last  = ','.join(str(a) for a in self.stack[-1])
                if self.g.has_edge(last, sargs):
                    l = self.g.edge_label(last, sargs)
                    self.g.set_edge_label(last, sargs, l + 1)
                else:
                    self.g.add_edge(last, sargs, 1)
            else:
                self.g   = DiGraph()
            self.stack.append(args)
            v = self.f(*args)
            self.stack.pop()
            return v
        def grafo(self):
            return self.g
    return G(f)

@grafo_llamadas
def fibo(n):
    if n<=2:
        return 1
    else:
        return fibo(n-1) + fibo(n-2)

fibo(6)
g = fibo.grafo()
g.show(edge_labels=True)

@grafo_llamadas
def particiones(n, k):
    if k == n:
        return [[1]*n]
    if k == 1:
        return [[n]]
    if not(0 < k < n):
        return []
    ls1 = [p+[1] for p in particiones(n-1, k-1)]
    ls2 = [[parte+1 for parte in p] for p in particiones(n-k, k)]
    return ls1 + ls2

particiones(8,3)
g = particiones.grafo()
g.show(edge_labels=True, figsize=(8,8), vertex_size=500)

Do you like it? Can you improve it? call graph of the partitions example

edit retag flag offensive close merge delete

Comments

Very nice. Why do you ignore `**kwds`?

Luca gravatar imageLuca ( 2013-08-07 04:42:21 -0500 )edit

I need the set of args to be a short string, otherwise the graph is a mess. Plus, I didn't feel the need: do you have some example in mind?

pang gravatar imagepang ( 2013-08-07 21:43:43 -0500 )edit

No, not really. Just curious. The fact that you declared them in the method definition, but then never used them just left me wondering.

Luca gravatar imageLuca ( 2013-08-08 02:35:52 -0500 )edit

Your're right. BTW, I'm trying to add screenshots with no success... I had to upload the screenshots to the sagemath wiki...

pang gravatar imagepang ( 2015-02-24 04:10:14 -0500 )edit

1 answer

Sort by ยป oldest newest most voted
1

answered 2015-02-24 04:25:20 -0500

pang gravatar image

The d3js version of the call graph is also cool

edge_partition = [
    [edge for edge in g.edges() if edge[-1]==el]  
    for el in set(g.edge_labels()) 
    ]
g.show(method='js', 
       edge_labels=True, 
       vertex_labels=True, 
       link_distance=90, 
       charge=-400, 
       link_strength=2, 
       force_spring_layout=True, 
       edge_partition=edge_partition)

d3js version of the partitions example

edit flag offensive delete link more

Your Answer

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

Add Answer

Question Tools

Stats

Asked: 2013-08-06 06:08:58 -0500

Seen: 296 times

Last updated: Feb 24 '15