Algorithms in bookdown

[dppalomar]

This is related to @yihui comment in Issue #422 :

@dataopt Algorithms are different with theorems in LaTeX, so they cannot be implemented as easily as theorems. The major challenge is that it is difficult to provide a portable environment that works for all output formats: it is super easy if you only need to consider LaTeX output. You can just use raw LaTeX: https://bookdown.org/yihui/bookdown/faq.html I don't know what to do when the output is HTML or EPUB.

I really think the environment for Algorithm is necessary. I personally need it for html and Latex. One quick hack would be if one could include a separate code for html and for Latex so that when building the correct code would be chosen. I only know how to do this inside an R code chunk, but not directly in the Markdown. But even if this was possible, then the issue of the referencing to the algorithm with automatic numbering would not be solved for html.

@yihui said he wouldn't know what to do when the output is HTML. Well, at least some simple table that looks like an algorithms could be done (automatic numbering of the algorithm for later referencing with a link would be great). For example, I use a code like this for html:

---

Algorithm 1: Bisection method

Input: interval $[l,u]$ (with $l>0$) containing $p^\star$, tolerance $\epsilon>0$

Output: solution $w$

repeat

1. $t \leftarrow (l+u)/2$
2. solve the convex feasibility problem
3. if problem feasible, $l \leftarrow t$ and keep solution $w$; else $u \leftarrow t$

until $u-l \leq \epsilon$;

---

And for Latex, something simple like:

\begin{algorithm} \SetAlgoLined \KwIn{interval $[l,u]$ containing $p^\star$, tolerance $\epsilon>0$} \KwOut{solution $x$} \Repeat{$u-l \leq \epsilon$}{ $t \leftarrow (l+u)/2$\ Solve the convex feasibility problem\ \eIf{feasible}{ $u \leftarrow t$ and keep solution $x$ } { $l \leftarrow t$ } } \caption{Bisection method.} \end{algorithm}

Could this be done? I would really really appreciate it... Thanks!!

[cderv]

Hi @dppalomar,

I am not sure to follow how you would do it in HTML. Maybe it is something related to the formatting of your post that is not clear. Please see https://yihui.org/issue/#please-format-your-issue-correctly to add the proper number of backticks.

If you can share how you would write it in the HTML document that would help (using HTML nodes).

For now, the comment is the same: Implementing new feature in bookdown means that we need to have one syntax in the Rmd document that we could use to generate several type of outputs (LaTeX, HTML and even Docx and epub if possible).

Also, if you have a solution to propose we'll be happy to review a Pull Request.

[dppalomar]

Thanks for your comment. Here is the super simple code that I used for the html table:

---
**Algorithm 1**:  Bisection method
---

**Input:** interval $[l,u]$ (with $l>0$) containing $p^\star$, tolerance $\epsilon>0$

**Output:** solution $w$

**repeat**

  1. $t \leftarrow (l+u)/2$
  2. solve the convex feasibility problem
  3. **if** problem feasible, $l \leftarrow t$ and keep solution $w$; **else** $u \leftarrow t$
  
**until** $u-l \leq \epsilon$;

---

Basically, I tried to imitate the way the Latex package algorithm2e outputs it, for which I used:

\usepackage[linesnumbered,ruled,vlined,algochapter]{algorithm2e}

\begin{algorithm}
\SetAlgoLined
\KwIn{interval $[l,u]$ containing $p^\star$, tolerance $\epsilon>0$}
\KwOut{solution $x$}
\Repeat{$u-l \leq \epsilon$}{
$t \leftarrow (l+u)/2$\
Solve the convex feasibility problem\
\eIf{feasible}{
$u \leftarrow t$ and keep solution $x$
} {
$l \leftarrow t$
}
}
\caption{Bisection method.}
\end{algorithm}

I have no idea how difficult this would be. In the worst case, would it be possible to let the user type the two alternate codes directly (in html and in Latex) so that depending on the compilation output the correct code is used? And also including the automatic numbering so that one can refer to it later in the text.

Thanks a lot!!!

[cderv]

would it be possible to let the user type the two alternate codes directly (in html and in Latex) so that depending on the compilation output the correct code is used?

You can already do that using the asis chunk and conditional insertion depending on the format for example:

• Write content conditionnaly : https://bookdown.org/yihui/rmarkdown-cookbook/eng-asis.html
• Conditional on output format: https://bookdown.org/yihui/rmarkdown-cookbook/latex-html.html
• custom block for styling : https://bookdown.org/yihui/rmarkdown-cookbook/custom-blocks.html

You would need to add the \usepackage call as a preamble, either using the YAML header field or in a file

Example

---
title: "test cache"
output:
  html_document: default
  pdf_document: 
    keep_md: true
    keep_tex: true
header-includes:
  - |
    ```{=latex}
    \usepackage[linesnumbered,ruled,vlined]{algorithm2e}
    ```
---

```{css, include = knitr::is_html_output(), echo = FALSE}
div.lined {
  border-top: 1px solid lightgrey;
  border-bottom: 1px solid lightgrey;
  padding-top: 0.5em;
  margin: 0.5em 0 0.5em 0;
}

div.algorithm {
  border-bottom: 1px solid lightgrey;
  margin: 0.5em 0 0.5em 0;
}
```


```{asis, echo = knitr::is_html_output()}
:::: algorithm
::: lined
**Algorithm 1**:  Bisection method
:::

**Input:** interval $[l,u]$ (with $l>0$) containing $p^\star$, tolerance $\epsilon>0$

**Output:** solution $w$

**repeat**

  1. $t \leftarrow (l+u)/2$
  2. solve the convex feasibility problem
  3. **if** problem feasible, $l \leftarrow t$ and keep solution $w$; **else** $u \leftarrow t$
  
**until** $u-l \leq \epsilon$;
::::
```

```{asis, echo = knitr::is_latex_output()}
````{=latex}
\begin{algorithm}
\SetAlgoLined
\KwIn{interval $[l,u]$ containing $p^\star$, tolerance $\epsilon>0$}
\KwOut{solution $x$}
\Repeat{$u-l \leq \epsilon$}{
$t \leftarrow (l+u)/2$\
Solve the convex feasibility problem\
\eIf{feasible}{
$u \leftarrow t$ and keep solution $x$
} {
$l \leftarrow t$
}
}
\caption{Bisection method.}
\end{algorithm}
````
```

You can also create a R function that would take input and output raw content to include depending on the output type using knitr::asis_output as the example in https://bookdown.org/yihui/rmarkdown-cookbook/latex-html.html

Is something like that for HTML would be helpful ? https://rpubs.com/cderv/pseudocodejs This is a prototype I made using https://github.com/SaswatPadhi/pseudocode.js

Maybe we can add support to this, or at least offer a third party tool for this. I'll think more about it.

[dppalomar]

Thanks @cderv for your awesome response. A couple of comments:

1. I have tried your code example and it works perfectly. There is only one detail left though: the numbering of the algorithms and later referencing. Ideally, both the latex algorithm and the html algorithm should have automatic numbering and then when referencing code should be simple and work for both cases. Right now, I can only do it with latex output including the \label{} and later \ref{}.

2. Then, you mentioned the use of that pseudocode.js and it is great indeed, much much better than the plain algorithm style I was writing. So I think definitely that's the way to go. However, the numbering and referencing should work in this case as well. With pseudocode.js (in html) there is automatic numbering but i) it doesn't include the chapter (which for a book is needed); and ii) I don't know how to include a label and cite later. With latex everything is fine since one has automatic numbering that can be referenced with \ref{ddd}.

3. If the referencing issue can be solved, then the next ambitious step would be, like you were saying, to be able to write the algorithm only once so that automatically depending on the output html/latex it would be transformed for one case or the other.

Thanks again!

[cderv]

Yes the referencing and numbering is the hard part. It was the meaning behind original Yihui's comment I guess. It is easy for LaTeX but not to provide the same feature for HTML.

This requires some works to either use the existing trick in bookdown or adapt them so that it works for this two. It may require a different implementation mechanism for references and in this case more heavy work. All this because it is not brought by Markdown feature and needs to be done in R directly.

We circle back to https://bookdown.org/yihui/bookdown/faq.html mentioned in the original comment.

I have mark this as a feature request so that we have this issue in the bucket next time we consider adding feature in bookdown. I'll keep you updated in this thread.

Thanks for the suggestion.

[dppalomar]

Thanks. In the meantime, two quick questions about pseudocode.js:

1. As a temporary fix, at least it would be good if one could fix the numbering of the algorithm in pseudocode.js. For example, I may automatically get Algorithm 1 but I may want Algorithm A.1 or Algorithm 2.1. Do you know if it's possible to specify this number manually? If not possible, then it's a deal breaker because not even manually we can make it work...
2. I have noticed that from within pseudocode.js one cannot refer to an equation (I tried both \@ref(eq:test) and \ref{eq:test} without success). Well, I guess in this second point one can manually write the equation number if not possible automatically.

Thanks for your help.

[cderv]

Do you know if it's possible to specify this number manually? If not possible, then it's a deal breaker because not even manually we can make it work..

Unfortunately, I don't know.

I have noticed that from within pseudocode.js one cannot refer to an equation (I tried both @ref(eq:test) and \ref{eq:test} without success). Well, I guess in this second point one can manually write the equation number if not possible automatically.

In HTML, the numbering equation feature from bookdown may not know how to handle equation reference inside pseudocode part. This is part of what needs to be done if we go the road of supporting this feature.

Supporting Algorithm is on the roadmap but we don't know when exactly we'll be able to tackle this.

[marcishak]

Just ran into this issue. Until something is fixed I quickly hacked a language engine today that works with html and latex by leveraging the already existing tikz renderer, messing around with some settings and embedding a prerendered algorithm. It's not perfect but so far (ie: today) it's worked for me, including referencing algorithms, which are numbered separately in latex but as figures in HTML (hence the addition of "algorithm" on the figure caption when in HTML). It's pretty basic but it has enough features for me

engine:

# enable algorithm env
eng_algo <- function(options) {
  if (!options$eval) {
    return(engine_output(options, options$code, ""))
  }

  # wrap in algorithm
  options$fig.env <- "algorithm"
  options$fig.align <- "default"
  options$fig.lp <- "fig:" # alg doesn't work!!

  # stuff from knitr
  `%n%` <- function(x, y) if (is.null(x)) y else x

  # template
  # H required to work in standalone...
  lines <- r"(\documentclass{standalone}
  %% EXTRA_PREAMBLE_CODE %%
  \usepackage[
  %% ALGO_CLASSOPTION %%
  ]{algorithm2e}
  \begin{document}
  \begin{algorithm}[H]
  %% ALGO_CODE %%
  \end{algorithm}
  \end{document}
  )"

  lines <- unlist(strsplit(lines, "\n"))

  options$resize.width <- NULL
  options$resize.height <- NULL
  options$resize.command <- NULL

  # add class options to template
  lines <- knitr:::insert_template(
    lines, "%% ALGO_CLASSOPTION %%", "linesnumbered,vlined", F
  )
  # insert code into preamble
  lines <- knitr:::insert_template(
    lines, "%% EXTRA_PREAMBLE_CODE %%", options$engine.opts$extra.preamble, F
  )

  options$fig.cap <- if (knitr::is_html_output() && !(grepl("(A|a)lgorithm", options$fig.cap))) {
    paste(options$fig.cap, "algorithm")
  } else {
    options$fig.cap
  }

  # insert tikz code into the tex template
  s <- knitr:::insert_template(lines, "%% ALGO_CODE %%", options$code)
  xfun::write_utf8(s, texf <- knitr:::wd_tempfile("tikz", ".tex"))
  # on.exit(unlink(texf), add = TRUE)

  ext <- tolower(options$fig.ext %n% knitr:::dev2ext(options$dev))

  to_svg <- ext == "svg"
  outf <- if (to_svg) tinytex::latexmk(texf, "latex") else tinytex::latexmk(texf)

  fig <- knitr:::fig_path(if (to_svg) ".dvi" else ".pdf", options)
  dir.create(dirname(fig), recursive = TRUE, showWarnings = FALSE)
  file.rename(outf, fig)

  fig2 <- xfun:::with_ext(fig, ext)
  if (to_svg) {
    # dvisvgm needs to be on the path
    # dvisvgm for windows needs ghostscript bin dir on the path also
    if (Sys.which("dvisvgm") == "") tinytex::tlmgr_install("dvisvgm")
    if (system2("dvisvgm", c(
      options$engine.opts$dvisvgm.opts, "-o", shQuote(fig2), fig
    )) != 0) {
      stop("Failed to compile ", fig, " to ", fig2)
    }
  } else {
    # convert to the desired output-format using magick
    if (ext != "pdf") {
      magick::image_write(do.call(magick::image_convert, c(
        list(magick::image_read_pdf(fig), ext), options$engine.opts$convert.opts
      )), fig2)
    }
  }
  fig <- fig2

  options$engine <- "tikz" # pretend to be tikz
  options$fig.num <- 1L
  options$fig.cur <- 1L
  extra <- knitr:::run_hook_plot(fig, options)
  options$engine <- "tex" # for output hooks to use the correct language class
  knitr::engine_output(options, options$code, "", extra)
}

# set engine
knitr::knit_engines$set(algorithm = eng_algo)

call:

```{algorithm, test1, fig.cap = "Test1"}
\SetAlgoLined
\KwIn{interval $[l,u]$ containing $p^\star$, tolerance $\epsilon>0$}
\KwOut{solution $x$}
\Repeat{$u-l \leq \epsilon$}{
$t \leftarrow (l+u)/2$\
Solve the convex feasibility problem\
\eIf{feasible}{
$u \leftarrow t$ and keep solution $x$
} {
$l \leftarrow t$
}
}
\``` 

For Latex, you'll also need \usepackage[ruled,algochapter]{algorithm2e} in your latex preamble as we're embedding a rendered algorithm inside an algorithm environment

For HTML I recommend having ghostscript and dvisvgm installed and including something like this within an output hook. That way you'll have selectable text if you export to svg.

if (knitr::opts_current$get("engine") %in% c("algorithm")) {
      options$engine.opts$dvisvgm.opts <- "--font-format=woff"
    }

Results:

Latex:

HTML:

[dppalomar]

@marcishak This is very nice, thanks! However, for a book, I cannot have in the caption "Figure" when it is an algorithm...

[marcishak]

@dppalomar

Yeah, it only applies to HTML though (hence the hardcoded "algorithm" suffix for html output), and unfortunately, I can't do anything right now about it due to the way references work in Bookdown/Rmarkdown. The tags for distinct refrence counters like "eq", "fig", and "thm" are hardcoded in.

@cderv @yihui As far as feature requests go, could it be possible to set new refrence counters for custom blocks/engines? As far as latex goes (in this case at least) the implementation wouldn't matter as simply having having a label inside the algorithm enviroment means its counter there is handled. For HTML (at least) and other formats (i have no clue tbh), an enviroment like this could simply output as HTML (in this case an inline svg) and potentially work that way?