[Tex/LaTex] Want Knuth style line numbering in algorithm2e algorithms

algorithm2e

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}

Best Answer

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.

Related Question