using Graphs, NetworkLayout
using PlotlyJS
function adjacency_btree(h::Int)
nn = 2^(h+1)-1 #number of nodes
A = zeros(Int, nn, nn);
labels = [""]
j=2
for i = 1:2^h-1
A[i, j] = A[i, j+1] = 1
append!(labels, ["<b>0</b>", "<b>1</b>"])
j=j+2
end
return A, labels
end
function perfect_btree(h::T, A:: Matrix{T}) where T<:Integer
G = DiGraph(A);
node_pos = buchheim(G.fadjlist)
#rotate the node positions with pi/2 about root (by defaul it's the origin) to get an horizontal tree
mcoords = hcat([-P[2] for P in node_pos], [P[1] for P in node_pos])
xn, yn = eachcol(mcoords); #new node corrdinates
E = [(e.src, e.dst) for e in edges(G)]
xe, ye = get_plotly_data(E, xn , yn);
xs, ys = eachcol(mcoords[2^h:end, :]) #the coordinates of points near leafs to display bistrings
return xn, yn, xe, ye, xs, ys
end
#T=Int8 is sufficient for tree depth, h=4, 5, 6, 7
bit_strings(h::Int;T=Int8)= String[bitstring(T(i))[sizeof(T)*8-h+1:end] for i in 0:2^h-1]
function get_plotly_data(E, xcoord, ycoord)
# E is the vector of tuples representing the graph edges
# xcoord, ycoords is the vectors of node coordinates
Xedges = Float64[]
Yedges = Float64[]
for e in E
append!(Xedges, [xcoord[e[1]], xcoord[e[2]], NaN])
append!(Yedges, [ycoord[e[1]], ycoord[e[2]], NaN])
end
return Xedges, Yedges
end
const h=4
A, labels = adjacency_btree(h)
xn, yn, xe, ye, xs, ys = perfect_btree(h, A)
vbstr= ["<b>$s</b>" for s in bit_strings(h;)]
fig = Plot([scatter(
x=xe,
y=ye,
mode="lines",
line_color="#d2d2d2",
line_width=1.5,
hoverinfo="none"),
scatter(
x=xn,
y=yn,
mode="markers+text",
name=" ",
text=labels,
marker_size=18, marker_color="rgb(255, 200, 0)",
hoverinfo="text")],
Layout(height=600, width=600, xaxis_visible=false, yaxis_visible=false,
font_size=16, font_family="Open Sherif", plot_bgcolor="#000000",
showlegend=false))
#one more traces to display the corresponding bitsring for each leaf
addtraces!(fig, scatter(x=xs .+0.6, y=ys, mode="text", text =vbstr, textfont_color="#d2d2d2"))
display(fig)
