---
title: "Drawing a Bratteli graph with R"
author: "Stéphane Laurent"
date: "14/08/2015"
output:
html_document:
keep_md: yes
---
```{r setup, include=FALSE}
library(knitr)
opts_chunk$set(fig.path="assets/fig/bratteli-")
knit_hooks$set(plot = function(x, options) {
paste('',
options$fig.cap, '', #
sep = '')
})
fscale <- 1.8
```
```{r functions, include=FALSE}
source("./assets/Rfunctions/Bgraph.R")
Bgraph <- Bgraph_v1
source("./assets/Rfunctions/utils_latex.R")
Pascal_Mn <- function (n) {
M <- matrix(0, nrow = n + 1, ncol = n + 2)
for (i in 1:(n + 1)) {
M[i, ][c(i, i + 1)] <- 1
}
return(M)
}
```
*Hey, ergodicians!* How do you draw your Bratteli graphs ? Are you using `Xfig`? Are you typing raw `pstricks` or `TikZ` code? Are you crazy? I have written the `Bgraph` R function, and it does the job without pain for you (feel free to take it [here](./assets/Rfunctions/Bgraph_v1.R)). You just have to write a R function returning the incidence matrices of the graph.
### Bratelli graphs - The Pascal example
A *Bratteli graph*, such as the *Pascal graph* shown below, is a graded graph whose edges only connect vertices from one level to some vertices of the next level.
```{r, echo=FALSE, fig.width=fscale*3, fig.height=fscale*3, fig.cap="Pascal graph"}
par(mar=c(.1,.1,.1,.1))
Bgraph(Pascal_Mn, N=3, path=c(1,0,1), first_vertex=1)
```
Such a graph is defined by a sequence of *incidence matrices* $M_n$. Denoting by $c_n$ the number of vertices at level $n$, the incidence matrix $M_n$ is a $c_n \times c_{n+1}$ matrix showing all connections between level $n$ and level $n+1$. A "$0$" means there's no edge, a "$1$" means there's one edge, a "$2$" means there's a double edge, etc. The first three incidence matrices of the Pascal graph are
```{r, echo=FALSE, results='asis'}
cat("$$", "M_0=", latex_matrix(Pascal_Mn(0)), ", \\, M_1=", latex_matrix(Pascal_Mn(1)), ", \\, M_2=", latex_matrix(Pascal_Mn(2)), ".$$")
```
and I get them with this function:
```{r}
Pascal_Mn <- function(n){
M <- matrix(0, nrow=n+1, ncol=n+2)
for(i in 1:(n+1)){
M[i, ][c(i, i+1)] <- 1
}
return(M)
}
```
Given a function `fun_Mn` taking a nonnegative integer `n` as argument and returning an incidence matrix, such as the `Pascal_Mn` function, my `Bgraph` function, based on the [diagram package](http://www.inside-r.org/packages/cran/diagram), draws the corresponding Bratteli graph from the root level to a desired level `N`. Its arguments are:
```{r}
formalArgs(Bgraph)
```
The effects of most of the arguments will be illustrated below. The ellipsis `...` is intended for additional arguments to the [coordinates](http://www.inside-r.org/packages/cran/diagram/docs/coordinates) function of the `diagram` package. For example the `hor` argument allows to rotate the picture.
The figure above has been generated by this code, except that this time we change its orientation with the `hor` argument:
```{r}
par(mar=c(.1,.1,.1,.1))
Bgraph(Pascal_Mn, N=3, path=c(1,0,1), first_vertex=1, hor=FALSE)
```
The path shown in blue on the figure, is given as the sequence of labels on the edges of this path. The `first_vertex` argument, intended to be `0` or `1`, controls the label of the first vertex at each level. The user can decide to show the edge labels of the blue path only with the `labels_path` argument. By setting the `only_end` argument to `TRUE`, only the vertex labels at the last level are shown:
```{r}
par(mar=c(.1,.1,.1,.1))
Bgraph(Pascal_Mn, N=3, path=c(1,0,1), first_vertex=0, labels_path=TRUE, only_end=TRUE)
```
By setting the `USE.COLNAMES` argument to `TRUE`, the vertex labels appearing at level $n$ are the column names of $M_n$. For example, on figure below we display the binomial numbers on the vertices Pascal graph, which give the number of paths from the root vertex. We also show the effect of the `ellipse_vertex` argument.
```{r}
Pascal_Mn <- function(n){
M <- matrix(0, nrow=n+1, ncol=n+2)
for(i in 1:(n+1)){
M[i, ][c(i, i+1)] <- 1
}
colnames(M) <- choose(n+1, 0:(n+1))
return(M)
}
par(mar=c(.1,.1,.1,.1))
Bgraph(Pascal_Mn, N=4, path=c(1,0,1,1), labels_path=TRUE, USE.COLNAMES=TRUE, ellipse_vertex=TRUE)
```
### Odometers
Bratteli graphs are well-known in ergodic theory since Vershik has shown that every invertible measure-preserving transformations can be represented as a transformation on the set of paths of such a graph.
The canonical Bratteli graph of an odometer is given by incidence matrixes full of "$1$":
```{r}
Odometer_Mn <- function(sizes){
sizes <- c(1,sizes)
function(n){
return(matrix(1, nrow=sizes[n+1], ncol=sizes[n+2]))
}
}
```
```{r odometer, fig.width=fscale*3, fig.height=fscale*3, fig.cap="(3,4,5)-ary odometer"}
par(mar=c(.1,.1,.1,.1))
fun_Mn <- Odometer_Mn(c(3,4,5))
Bgraph(fun_Mn, N=3, labels_vertex=TRUE, path=c(2,1,2), labels_path=TRUE)
```
This graph is related to [Cantor expansions](http://stla.github.io/stlapblog/posts/Greedy.html). For the previous example, the paths starting from the root level and going to the third level provide a representation of the Cartesian product $\{0,1,2\}\times\{0,1,2,3\}\times\{0,1,2,3,4\}$.
### Homogeneous trees
A homogeneous tree is a Bratteli graph. I use a trick to generate the incidence matrices, [the same I already used before](http://stla.github.io/stlapblog/posts/KantorovichWithR.html).
```{r}
Tree_Mn <- function(sizes){
function(n){
if(n==0) return(matrix(1, ncol=sizes[1]))
unname(t(model.matrix(~0+gl(prod(sizes[1:n]),sizes[n+1])))[,])
}
}
```
As for the odometer, the paths of the tree provide a representation of a Cartesian producct, but in less compact form:
```{r tree, fig.width=fscale*3, fig.height=fscale*3, fig.cap="(3,4,5)-ary tree"}
par(mar=c(.1,.1,.1,.1))
fun_Mn <- Tree_Mn(c(3,4,5))
Bgraph(fun_Mn, N=3, labels_vertex=FALSE, labels_edges=FALSE, path=c(2,1,2))
```
### Conversion to `TikZ`
Mathematicians like $\LaTeX$ figures. The `tikzDevice` package allows to convert any R figure to a `TikZ` figure. For example we generate below the Pascal graph with the binomial numbers ${n \choose k}$ as vertex labels. We set the argument `LaTeX` to `TRUE` in the `Bgraph` function to generate edge labels in $\LaTeX$ math mode.
```{r, eval=!file.exists("assets/fig/bratteli-Pascal.pdf"), message=FALSE, results='hide'}
Pascal_Mn <- function(n){
M <- matrix(0, nrow=n+1, ncol=n+2)
for(i in 1:(n+1)){
M[i, ][c(i, i+1)] <- 1
}
colnames(M) <- sprintf("${%s \\choose %s}$", n+1, 0:(n+1))
return(M)
}
# convert to TikZ code:
library(tikzDevice)
texfile <- "bratteli-Pascal.tex"
tikz(texfile, standAlone=TRUE,
packages=c(getOption("tikzLatexPackages"), "\\usepackage{amsmath}\n\\usepackage{amssymb}\n"))
par(mar=c(.1,.1,.1,.1))
Bgraph(Pascal_Mn, N=3, path=c(1,0,1), labels_path=TRUE, USE.COLNAMES=TRUE, LaTeX=TRUE, label_root="$\\varnothing$", relsize=.6)
dev.off()
# convert to pdf:
tools::texi2dvi(texfile, pdf=TRUE, clean=TRUE)
# crop the figure (remove white margins):
knitr::plot_crop("bratteli-Pascal.pdf")
```
```{r, echo=FALSE, eval=!file.exists("assets/fig/bratteli-Pascal.pdf"), echo=FALSE}
file.copy("bratteli-Pascal.tex", "assets/fig/bratteli-Pascal.tex")
file.copy("bratteli-Pascal.pdf", "assets/fig/bratteli-Pascal.pdf")
file.remove("bratteli-Pascal.tex", "bratteli-Pascal.pdf")
```
This is the result:
### Multiples edges
My `Bgraph` function currently handles double edges too. Let us try the Pascal graph with some double edges taken at random.
```{r doubleedge}
Pascal2_Mn <- function(n){
M <- matrix(0, nrow=n+1, ncol=n+2)
for(i in 1:(n+1)){
M[i, ][c(i, i+1)] <- sample.int(2, 1)
}
return(M)
}
set.seed(666)
par(mar=c(.1,.1,.1,.1))
Bgraph(Pascal2_Mn, N=4, labels_vertex=FALSE, labels_path=TRUE, path=c(1,0,1,0))
```
Currently, the rendering of the colored path is not correct, because the two edges of a double edge appears in color. The label edges are not correct too. This will be fixed in a next version of the `Bgraph` function.