7

What is the best way to get Knuth style line numbering of algorithms using the algorithm2e package? I.e., rather than numbering algorithm lines as 1, 2, 3, ... each line number should include a prefix which is the algorithm number, e.g., 3.1 3.2, 3.2...

When using the algorithm2e latex package, lines are numbered 1, 2, 3,... I can add prefix and suffixes with \SetNlSty{textbf}{\ref{algo.rte}.}{}

So that the algorithm number appears as a prefix. E.g., lines algorithm 3 is numbered 3.1, 3.2, 3.3, etc... This is not really sufficient, however because when I refer to a line number later with \ref{..label...}, the reference only grabs the number, not the prefix.

This is motivated by the way Knuth numbers algorithm lines in Art of Computer Programming, except that his algorithms are numbers with letters, so the line numbers are e.g. B1, B2, B3... enter image description here

Here is the latex code I tried.

\documentclass[a4paper]{article}
\usepackage{amsmath}
\usepackage[linesnumbered,ruled,vlined]{algorithm2e}
\makeatletter
\renewcommand{\theAlgoLine}{%
  \@arabic{\numexpr\value{algocf}+1\relax}.\arabic{AlgoLine}}
\makeatother
\begin{document}
\begin{algorithm}[H]
\DontPrintSemicolon % Some LaTeX compilers require you to use \dontprintsemicolon instead
    \While{true} { \label{algo.rte.1300}
      $V' \gets \{u \in U | u' \in U\setminus\{u\} \implies u \perp u'\}$ \label{algo.rte.1301}\;
      $U \gets U \setminus V'$ \label{algo.rte.1304}\;
      \uIf{$U = \emptyset$} {
        \Return{$V$} \label{algo.rte.1305}\;
      }}
\caption{Finds the maximal disjoint decomposition}
\label{algo.rte}
\end{algorithm}

\vbox{Notes about Algorithm~\ref{algo.rte}:
  \begin{itemize}
  \item[Line \ref{algo.rte.1301}] we find the set, $V'$ of all elements
    of $U$ which are disjoint from all other elements of $U$.  Notice
    that if $U$ is a singleton set, then
    $V'$ is that singleton element, thus $U \gets \emptyset$ on
    line~\ref{algo.rte.1304}.
  \item[Line \ref{algo.rte.1301}] This is of course an
    $\mathcal{O}(n^2)$ search, and what is worse, it is repeated each
    time through the loop headed on line~\ref{algo.rte.1300}.
  \item[Line \ref{algo.rte.1305}] If $U = \emptyset$ then we have
    collected all the disjoint sets into $V$.    
\end{itemize}}

\end{document}
  • Welcome to TeX.SX! Please add a minimal working example (MWE), so we could use compilable code, starting with \documentclass and ending with \end{document}. – Bobyandbob Jun 5 '17 at 12:35
  • Hi Bobyandbob, I was trying to include an example, but I'm not allowed to use more then 550 characters (approx). And I don't see a way to upload images either. – Jim Newton Jun 5 '17 at 13:00
  • Okay. There is a way to add images, have a look to the top line(sixth symbol from the left side. Right of the two braces ...). You also could edit your question(below left -> edit). A MWE should as short as possible. Here you can find strategies to reduce your code: tex.meta.stackexchange.com/a/3225/124842 – Bobyandbob Jun 5 '17 at 13:08
  • HI Bobyandbob, I see. I can add code and images by edited the original post, but I cannot from a comment, apparently. – Jim Newton Jun 5 '17 at 13:18
  • The time limit for editing comments is only 5 minutes and you can't add images. If the answer of egreg works fine for you, you can accept the question. Please read What should I do when someone answers my question? – Bobyandbob Jun 5 '17 at 13:23
3

If your captions are below the algorithm,

\documentclass{article}
\usepackage[linesnumbered]{algorithm2e}

\makeatletter
\renewcommand{\theAlgoLine}{%
  \@arabic{\numexpr\value{algocf}+1\relax}.\arabic{AlgoLine}}
\makeatother

\begin{document}

\begin{algorithm}
\SetKwData{Left}{left}\SetKwData{This}{this}\SetKwData{Up}{up}
\SetKwFunction{Union}{Union}\SetKwFunction{FindCompress}{FindCompress}
\SetKwInOut{Input}{input}\SetKwInOut{Output}{output}
\Input{A bitmap $Im$ of size $w\times l$}
\Output{A partition of the bitmap}
\BlankLine
\emph{special treatment of the first line}\;
\For{$i\leftarrow 2$ \KwTo $l$}{
  \emph{special treatment of the first element of line $i$}\;
  \For{$j\leftarrow 2$ \KwTo $w$}{\label{forins}
    \Left$\leftarrow$ \FindCompress{$Im[i,j-1]$}\;
    \Up$\leftarrow$ \FindCompress{$Im[i-1,]$}\;
    \This$\leftarrow$ \FindCompress{$Im[i,j]$}\;
    \If(\tcp*[h]{O(\Left,\This)==1}){\Left compatible with \This}{\label{lt}
      \lIf{\Left $<$ \This}{\Union{\Left,\This}}
      \lElse{\Union{\This,\Left}}
    }
    \If(\tcp*[f]{O(\Up,\This)==1}){\Up compatible with \This}{\label{ut}
      \lIf{\Up $<$ \This}{\Union{\Up,\This}}
      \tcp{\This is put under \Up to keep tree as flat as possible}\label{cmt}
      \lElse{\Union{\This,\Up}}\tcp*[h]{\This linked to \Up}\label{lelse}
    }
  }
  \lForEach{element $e$ of the line $i$}{\FindCompress{p}}
}
\caption{disjoint decomposition}\label{algo_disjdecomp}
\end{algorithm}

\end{document}

If you place captions above, then \thealgocf should be used instead of \@arabic{\numexpr\value{algocf}+1\relax}.

enter image description here

  • Thanks egreg, but when I try your advise it doesn't work for me. I indeed get the line numbering like you do 1.1, 1.2, 1.3 ... but when I add a \label to one of the lines, (line 7) for example, then in the next paragraph reference the line with \ref{label}, it renders as "7" not "1.7" in the paragraph text. – Jim Newton Jun 5 '17 at 12:59
  • Hi egreg, it turns out that if I compile the latex multiple, times I get the desired line numbers, 1.1 1.2, etc in the references. That's great! Thanks, it seems to work. – Jim Newton Jun 5 '17 at 13:20
  • 1
    If the answer works, you should accept it; not so much to give @egreg his reputation reward - he deserves it but he hardly needs it :-) - but to indicate to others that there is indeed an accepted solution to the problem. – NickD Jun 5 '17 at 22:16
  • @Nick I have to preserve (and possibly increase) the gap from David. ;-) – egreg Jun 5 '17 at 22:21
0

Note that option algonl do already that, no need to redefine \TheAlgoNl. Note also that you need to put caption first to have correct numbering.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.