Want Knuth style line numbering in algorithm2e algorithms

Question

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...

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}

Answer 1

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.

Answer 2

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}.