Trees in Julia

microlifecc · July 5, 2018, 1:21am

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

JackDevine · July 5, 2018, 1:34am

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])).

microlifecc · July 5, 2018, 1:50am

Thanks a lot!!!

swissr · July 5, 2018, 9:20am

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

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

wookyoung · July 5, 2018, 11:35am

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

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)

kapple · July 11, 2019, 7:53am

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?

baggepinnen · July 11, 2019, 9:04am

kapple · July 11, 2019, 10:44am

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)

BeastyBlacksmith · July 11, 2019, 11:57am

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

using Plots
pyplot()

kapple · July 12, 2019, 12:49am

Thanks!

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

I might start making it from scratch.

chakravala · July 12, 2019, 2:46am

kapple · July 12, 2019, 4:15am

Yeah I’ve seen this too.

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

chakravala · July 12, 2019, 4:26am

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

mhw · July 14, 2019, 2:36am

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

kapple · July 15, 2019, 11:59am

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.