Binary-tree-n-Bernoulli-trials

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "733f3497",
   "metadata": {},
   "source": [
    "## <center> Binary tree associated to n Bernoulli trials </center>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3d4fb816",
   "metadata": {},
   "source": [
    " The perfect binary tree  of height (depth), h=n, is defined as a directed graph, from its  adjacency matrix.\n",
    "The node position is returned by the function `NewtorkLayout.buchheim`. To get an horizontal tree the node positions are rotated about the root (which is by default the origin [0,0]), with an angle of π/2.\n",
    "Each path, from root to a leaf, represents an outcome of this experiment. \n",
    "h-length bit strings  encode all  possible  outcomes ($2^h$) of the Bernoulli experiment."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6d8bd5dc",
   "metadata": {},
   "outputs": [],
   "source": [
    "using Graphs, NetworkLayout\n",
    "using PlotlyJS\n",
    "\n",
    "function adjacency_btree(h::Int)\n",
    "    nn = 2^(h+1)-1 #number of nodes\n",
    "    A = zeros(Int, nn, nn);\n",
    "    labels = [\"\"]\n",
    "    j=2\n",
    "    for i = 1:2^h-1\n",
    "        A[i, j] = A[i, j+1] = 1\n",
    "        append!(labels, [\"<b>0</b>\", \"<b>1</b>\"])\n",
    "        j=j+2\n",
    "    end \n",
    "    return A, labels\n",
    "end \n",
    "function perfect_btree(h::T, A:: Matrix{T}) where T<:Integer\n",
    "    G = DiGraph(A);\n",
    "    node_pos = buchheim(G.fadjlist)\n",
    "    #rotate the node positions with pi/2 abou roott at [0.0,0.0]to get an horizontal tree\n",
    "    mcoords = hcat([-P[2] for P in node_pos], [P[1] for P in node_pos])\n",
    "    xn, yn = eachcol(mcoords); #new node corrdinates\n",
    "    E = [(e.src, e.dst) for e in edges(G)]\n",
    "    xe, ye = get_plotly_data(E, xn , yn);\n",
    "    xs, ys = eachcol(mcoords[2^h:end, :]) #the coordinates of points near leafs to display bistrings\n",
    "    return xn, yn, xe, ye,  xs, ys\n",
    "end \n",
    "\n",
    "#Int8 is sufficient for h=4, 5, 6, 7\n",
    "bit_strings(h::Int;T=Int8)= String[bitstring(T(i))[sizeof(T)*8-h+1:end]   for i in 0:2^h-1]\n",
    "\n",
    "function get_plotly_data(E, xcoord, ycoord)\n",
    "    # E is the vector of tuples representing the graph edges\n",
    "    # xcoord, ycoords is the vectors of node coordinates\n",
    "\n",
    "    Xedges = Float64[]\n",
    "    Yedges = Float64[]\n",
    "    for e in E\n",
    "        append!(Xedges, [xcoord[e[1]], xcoord[e[2]], NaN])\n",
    "        append!(Yedges, [ycoord[e[1]], ycoord[e[2]], NaN])\n",
    "    end\n",
    "    return Xedges, Yedges\n",
    "end\n",
    "\n",
    "const h=4\n",
    "A, labels = adjacency_btree(h)\n",
    "xn, yn, xe, ye,  xs, ys = perfect_btree(h, A)\n",
    "vbstr= [\"<b>$s</b>\" for s in bit_strings(h;)]\n",
    "fig = Plot([scatter(\n",
    "                x=xe,\n",
    "                y=ye,\n",
    "                mode=\"lines\",\n",
    "                line_color=\"#d2d2d2\",\n",
    "                line_width=1.5,\n",
    "                hoverinfo=\"none\"),\n",
    "           scatter(\n",
    "                x=xn, \n",
    "                y=yn, \n",
    "                mode=\"markers+text\",\n",
    "                name=\" \",\n",
    "                text=labels,\n",
    "            marker_size=18, marker_color=\"rgb(255, 200, 0)\",\n",
    "                hoverinfo=\"text\")], \n",
    "                Layout(height=600, width=600, xaxis_visible=false, yaxis_visible=false,\n",
    "                       font_size=16, font_family=\"Open Sherif\", plot_bgcolor=\"#000000\",\n",
    "                       showlegend=false))\n",
    "\n",
    "addtraces!(fig, scatter(x=xs .+0.6, y=ys, mode=\"text\", text =vbstr, textfont_color=\"#d2d2d2\"))\n",
    "display(fig)    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d5458f34",
   "metadata": {},
   "outputs": [],
   "source": [
    "savefig(fig, \"Bernoulliexp.png\", width =600, height=600, scale=1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6d90249b",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "@webio": {
   "lastCommId": null,
   "lastKernelId": null
  },
  "kernelspec": {
   "display_name": "Julia 1.8.4",
   "language": "julia",
   "name": "julia-1.8"
  },
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "1.8.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}