# 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.

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
[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
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

: 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

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.