# Plotting a recursion graph for a function with 2 arguments

I have a recursive function with 2 indices of the form:

``````function calc_rs(n,p)
println("Calculating for (\$n,\$p)")
if n != 1
calc_rs(n-1, 1)
calc_rs(n-1, p+1)
end
end
``````

It is called as:

``````calc_rs(N, 1)
``````

then it recurses until it hits the base case with (1,p). For example, with N=3:

``````calc_rs(3, 1)
Calculating for (3,1)
Calculating for (2,1)
Calculating for (1,1)
Calculating for (1,2)
Calculating for (2,2)
Calculating for (1,1)
Calculating for (1,3)
``````

I am trying to create a plot of this recursion. I have made this manually as:

``````using GraphRecipes, Plots
g = [0 1 1 0 0 0;
0 0 0 1 1 0;
0 1 0 1 0 1;
0 0 0 0 0 0;
0 0 0 0 0 0;
0 0 0 0 0 0]

names=["(3,1)", "(2,1)", "(2,2)", "(1,1)", "(1,2)", "(1,3)"]
p = palette(:rainbow, 3)

graphplot(g, names=names, curvature_scalar=0, fontsize=12, nodeweights=[3,2,2,1,1,1], markercolor = [p,p,p,p,p,p])
``````

Which results in what I expect:

Is there an easier way to do this using e.g. trees? It seems a little difficult to automate the process in this way, I just can’t wrap my head around it.

1 Like

You could use an actual graph:

``````using LightGraphs, MetaGraphs, Plots, GraphRecipes
Plots.pyplot() # seems to be necessary to plot arrows for directed graphs

g = MetaDiGraph() # empty graph
set_indexingprop!(g, :name) # allows one to look up nodes by the attribute :name

function calc_rs(n, p, g)
println("Calculating for (\$n,\$p)")
if !haskey(g[:name], (n, p)) # if there is not already a node with name (n, p)
# add a new vertex and set it's name to (n, p)
# the most recent added vertex always has the index nv(g)
set_prop!(g, nv(g), :name, (n, p))
end
if n != 1
# recurse as usual but with also passing g
calc_rs(n-1, 1, g)
calc_rs(n-1, p+1, g)

# at this point, the vertices with the names (n, p), (n-1, 1) and (n-1, p+1) already exist
# so we look them up by their name
v1 = g[(n, p), :name]
v2 = g[(n-1, 1), :name]
v3 = g[(n-1, p+1), :name]

# add edges (n, p) -> (n-1, 1)  and (n, p) -> (n-1, p+1)
end
return nothing
end

calc_rs(3, 1)
graphplot(g, names = [string(get_prop(g, v, :name)) for v in vertices(g)], arrow=:arrow)
`````` Otherwise, `graphplot` seem also be able to draw trees: Examples · Plots

3 Likes

Brilliant! Thank you so much! I edited the example a little bit to get the following:

``````using LightGraphs, MetaGraphs, Plots, GraphRecipes

g = MetaDiGraph() # empty graph
set_indexing_prop!(g, :name) # allows one to look up nodes by the attribute :name
size = []
col = []

function calc_rs(n, p, g, N, pal, size, col)
println("Calculating for (\$n,\$p) with order \$N")
if !haskey(g[:name], (n, p)) # if there is not already a node with name (n, p)
# add a new vertex and set it's name to (n, p)
# the most recent added vertex always has the index nv(g)
set_prop!(g, nv(g), :name, (n, p))
push!(size, N)
push!(col, pal[N])
end
if n != 1
# recurse as usual but with also passing g
calc_rs(n-1, 1, g, N-1, pal, size, col)
calc_rs(n-1, p+1, g, N-1, pal, size, col)

# at this point, the vertices with the names (n, p), (n-1, 1) and (n-1, p+1) already exist
# so we look them up by their name
v1 = g[(n, p), :name]
v2 = g[(n-1, 1), :name]
v3 = g[(n-1, p+1), :name]

# add edges (n, p) -> (n-1, 1)  and (n, p) -> (n-1, p+1)
end
return nothing
end

N = 4
pal = palette([:red, :yellow, :lightblue], N)
calc_rs(N, 1, g, N, pal, size, col)
graphplot(g, names = [string(get_prop(g, v, :name)) for v in vertices(g)], arrow=:arrow, nodeshape=:circle, curvature_scalar=0.01, nodeweights=size, markercolor=col, fontsize=14, markersize=0.05)
``````
1 Like

You could also add `:col` and `size` as additional vertex properties to your graph:

``````using LightGraphs, MetaGraphs, Plots, GraphRecipes

g = MetaDiGraph() # empty graph
set_indexing_prop!(g, :name) # allows one to look up nodes by the attribute :name

function calc_rs(n, p, g, N, pal)
println("Calculating for (\$n,\$p) with order \$N")
if !haskey(g[:name], (n, p)) # if there is not already a node with name (n, p)
# add a new vertex and set it's name to (n, p)
# the most recent added vertex always has the index nv(g)
set_prop!(g, nv(g), :name, (n, p))
set_prop!(g, nv(g), :size, N)
set_prop!(g, nv(g), :col, pal[N])
end
if n != 1
# recurse as usual but with also passing g
calc_rs(n-1, 1, g, N-1, pal)
calc_rs(n-1, p+1, g, N-1, pal)

# at this point, the vertices with the names (n, p), (n-1, 1) and (n-1, p+1) already exist
# so we look them up by their name
v1 = g[(n, p), :name]
v2 = g[(n-1, 1), :name]
v3 = g[(n-1, p+1), :name]

# add edges (n, p) -> (n-1, 1)  and (n, p) -> (n-1, p+1)
end
return nothing
end

pal = palette([:red, :yellow, :lightblue], N)

calc_rs(N, 1, g, N, pal)

graphplot(g,
names=[string(get_prop(g, v, :name)) for v in vertices(g)],
arrow=:arrow,
nodeshape=:circle,
curvature_scalar=0.01,
nodeweights=[get_prop(g, v, :size) for v in vertices(g)],
markercolor=[get_prop(g, v, :col) for v in vertices(g)],
fontsize=14,
markersize=0.05)
``````
2 Likes

Again, brilliant, thank you! I have modified it a little bit and added it to my documentation here, with proper attribution of course. Thank you again, I would have never figured this out on my own.

1 Like