Trees in Julia

Hi Guys!
I am new to Julia and am trying to learn by writing some code. So I was trying to implement a tree and get the sum of node of all the elements in the sub-tree given a particular node.
Selection_028
Here is my work:

struct element
    name::String
    data::Int64
    loe
end


F1 = element("F1", 1, nothing)
F2 = element("F2", 2, nothing)
F3 = element("F3", 3, nothing)
D4 = element("D4", 0, [F1, F2])
D5 = element("D5", 0, [F3])
D6 = element("D6", 0, [D4, D5])


function sum_data_loe(loe)
    if loe == nothing
        0
    else
        (length(loe)>1)?(sum_data_element(loe[1]) + sum_data_loe[2:end]):sum_data_element(loe[1])
    end
end


function sum_data_element(e)
    if e.data == 0
        sum_data_loe(e.loe)
    else
        e.data
    end
end


@test sum_data_element(F1) == 1 #Test Passed
@test sum_data_loe(nothing) == 0 #Test Passed
@test sum_data_element(D5) == 3 #Test Passed
@test sum_data_element(D4) == 3 #Failed
@test sum_data_element(D6) == 6 #Failed

Error:

Error During Test
Test threw an exception of type MethodError
Expression: sum_data_element(D4) == 3
MethodError: no method matching endof(::#sum_data_loe)
Closest candidates are:
endof(::SimpleVector) at essentials.jl:257
endof(::Char) at char.jl:18
endof(::String) at strings/string.jl:153

Stacktrace:
[1] sum_data_loe(::Array{element,1}) at ./In[9]:5
[2] sum_data_element(::element) at ./In[10]:3
[3] include_string(::String, ::String) at ./loading.jl:522
[4] execute_request(::ZMQ.Socket, ::IJulia.Msg) at /home/subhankar/.julia/v0.6/IJulia/src/execute_request.jl:158
[5] (::Compat.#inner#18{Array{Any,1},IJulia.#execute_request,Tuple{ZMQ.Socket,IJulia.Msg}})() at /home/subhankar/.julia/v0.6/Compat/src/Compat.jl:378
[6] eventloop(::ZMQ.Socket) at /home/subhankar/.julia/v0.6/IJulia/src/eventloop.jl:8
[7] (::IJulia.##14#17)() at ./task.jl:335
There was an error during testing
Stacktrace:
[1] record(::Base.Test.FallbackTestSet, ::Base.Test.Error) at ./test.jl:533
[2] do_test(::Base.Test.Threw, ::Expr) at ./test.jl:352

It looks like you tried to index into a function in the else part of sum_data_loe. All of the tests pass for me if I replace sum_data_loe[2:end] with sum_data_loe(loe[2:end])).

Thanks a lot!!!

A bit nitpicking maybe, but element is a type and should begin with a capital letter. See here for the conventions: https://docs.julialang.org/en/latest/manual/variables/#Stylistic-Conventions-1. Of course you are free to do what you want :wink:

[Edit]: ah, and the variables F1, F2, … D6 should be in lower case, i.e. f1, f2, … d6.

2 Likes

As you might know already, there are Julia packages for data structures such as
https://github.com/Keno/AbstractTrees.jl https://github.com/JuliaCollections/DataStructures.jl

Try this in Julia 0.7

struct Element
    name::String
    data::Int64
    loe
end

F1 = Element("F1", 1, nothing)
F2 = Element("F2", 2, nothing)
F3 = Element("F3", 3, nothing)
D4 = Element("D4", 0, [F1, F2])
D5 = Element("D5", 0, [F3])
D6 = Element("D6", 0, [D4, D5])


import AbstractTrees: children, printnode, print_tree, Leaves
children(el::Element) = something(el.loe, [])

sum_data_element(el::Element) = sum(map(x->x.data, Leaves(el)))

using Test
@test sum_data_element(F1) == 1
@test sum_data_element(D5) == 3
@test sum_data_element(D4) == 3
@test sum_data_element(D6) == 6


printnode(io::IO, el::Element) = print(io, el.name, ' ', el.data)
print_tree(D6)
3 Likes

Hi @microlifecc, have you finished your code and successfully created the tree diagram?

I can’t find any Julia/Matlab/LaTeX solutions for how to make a nice tree?

Anyone know how to make a tree diagram?

Wanna help me out? It’s ugly.

using GraphRecipes
using Plots

edges = [[1, 2, 3] ,[2, 4, 5], [3, 6, 7], [5, 8, 9]]

N = maximum(maximum.(edges)) + 1

A = zeros(N, N)

for n = 1:length(edges)
    r = edges[n][1]
    for c in edges[n][2:end]
        A[r, c] = 1
    end
end
A += A'

graphplot(A,
    node_weights = 1:N,
    names = 1:N,
    linecolor = :darkgrey)

I think it looks a bit nicer when using the pyplot-backend. So

using Plots
pyplot()

Thanks!

Though, I want to plot a tree-structured view.

I might start making it from scratch.

Yeah I’ve seen this too.

It’s for Syntax trees, and not really for general tree-diagram plotting.

It’s for AST, but also a good starting point for LaTeX plotting other kinds of tree types.

Hi kapple,
you can generate really nice trees with LuaLaTeX if you are using the Tikz package, especially \usetikzlibrary{graphdrawing} and \usegdlibrary{trees}. Here is a LaTeX-file as an example. This example has included Lua code which is necessary when using Windows. The indentations in the Lua code are important (layout rule)!

\documentclass{article}

\usepackage{tikz}
\usetikzlibrary{graphdrawing}

\usepackage{luacode}

\begin{luacode}
	function pgf_lookup_and_require(name)
		local sep = '/'
		if string.find(os.getenv('PATH'),';') then
			sep = '\string\\'
		end
		local function lookup(name)
			local sub = name:gsub('%.',sep)
			local find_func = function (name, suffix)
				if resolvers then
					local n = resolvers.findfile (name.."."..suffix, suffix) -- changed
					return (not (n == '')) and n or nil
				else
					return kpse.find_file(name,suffix)
				end
			end
			if find_func(sub, 'lua') then
				require(name)
			elseif find_func(sub, 'clua') then
				collectgarbage('stop')
				require(name)
				collectgarbage('restart')
			else
				return false
			end
			return true
		end
		return
			lookup('pgf.gd.' .. name .. '.library') or
			lookup('pgf.gd.' .. name) or
			lookup(name .. '.library') or
			lookup(name)
	end
\end{luacode}

\usetikzlibrary{graphs}
\usegdlibrary{trees}

\begin{document}
	\input{t.tex};
\end{document}

The Tex-file t.tex contains the data for generating the tree layout. This file is generated by a small Julia program which I have written for trees with Int values and with arbitrary many childs.The program can easily be adapted to other (generic) tree data structures

struct IntTree
    node :: Int64
    childs :: Array{IntTree,1}
end

leaf(x:: Int64) = IntTree(x,[])

isLeaf(t:: IntTree) = t.childs == []

oneChild(t:: IntTree) = length(t.childs) == 1

tree(x:: Int64, ts:: Array{IntTree,1}) = IntTree(x,ts)

# examples for type Tree

l1 = leaf(1)
l2 = leaf(64)
l3 = leaf(17)
l4 = leaf(9)

t1 = tree(11,[l1,l2])
t2 = tree(4,[l3,l4])
t3 = tree(6,[l1,l2,l4])
t4 = tree(21,[t1,t3,l3])

function drawTree(r:: IntTree)
    if (isLeaf(r))
        return string(r.node)
    elseif (oneChild(r))
        return string(r.node) * " -- " * drawTree(r.child[1])
    else
        xs = map( drawTree, r.childs )
        return string(r.node) * " -- " * "{ " * join(xs, ", ") * " }"
    end
end


function tree2Latex(t:: IntTree, fileName:: String)
    s1 = "\\begin{tikzpicture}[every node/.style={circle, draw, minimum size=0.75cm}] \n\n "
    s2 = "\\graph [tree layout, grow=down, fresh nodes, level distance=0.5in, sibling distance=0.5in] \n {"
    s3 = " };\n \\end{tikzpicture}"
    s = s1 * s2 * drawTree(t) * s3
    outfile = open(fileName, "w")
    write(outfile, s)
    close(outfile)
end

If you want the tree diagram of the tree t4 in the Julia code above then first execute

tree2Latex(t4, “t.tex”)
and then compile the above given LaTeX source with lualatex. Here is the result
t4

4 Likes

That’s very kind of you, thank you.

I’ll give them a shot.

Edit: It would be amazing if we had Julia instead of Lua with Tex documentation in the future. Weave documentation lacks so many features. It’s nice though.