Plotting a recursion graph for a function with 2 arguments

[ash]

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[1],p[2],p[2],p[3],p[3],p[3]])

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.

[simonschoelly]

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)
        add_vertex!(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)
         add_edge!(g, v1, v2)
         add_edge!(g, v1, v3)
    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: https://docs.juliaplots.org/latest/graphrecipes/examples/#AbstractTrees-Trees

[ash]

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)
        add_vertex!(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)
         add_edge!(g, v1, v2)
         add_edge!(g, v1, v3)
    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)

[simonschoelly]

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)
        add_vertex!(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)
        add_edge!(g, v1, v2)
        add_edge!(g, v1, v3)
    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)

[ash]

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.