Algorithmes (algorithm2e/algpseudocode)

Une recherche sur « latex algorithm package » renvoie quatre noms presque identiques — algorithm, algorithmic, algorithmicx, algorithm2e — et il y a de bonnes chances que le préambule en cours de réparation en charge deux qui refusent de cohabiter dans le même document. Cet enchevêtrement est le vrai sujet de cette page, car une fois démêlé, composer du pseudocode en LaTeX est simple. L’essentiel à retenir : le pseudocode n’est pas un collage de code. Contrairement aux listings de la page voisine, un algorithme se compose comme des mathématiques — variables en italique, flèche pour l’affectation, mots-clés en gras — à l’intérieur d’un flottant numéroté que \ref peut viser. Au programme : quelle paire de packages charger, les erreurs exactes que produit la mauvaise paire, et les deux dialectes écrits en entier.

Pseudocode et listings : coller du code ou le composer

En une phrase : listings conserve des caractères, le pseudocode compose du sens. Ce que l’on confie à listings ou minted est traité en verbatim — chaque espace, chaque symbole survit jusqu’à la page —, ce dont le vrai code source a précisément besoin; cet arbitrage appartient à la page voisine. Le pseudocode inverse la logique. Écrivez $y \gets 1$ et y devient une variable en italique tandis que \gets devient la flèche ← : le corps vit en mode mathématique, non dans un environnement verbatim. Seuls les mots-clés se dressent en romain gras, visuellement détachés des variables. Cette convention — italique pour les variables, gras pour les mots-clés — est celle des manuels, héritée de The Art of Computer Programming de Knuth. Le nom \gets relève du même héritage : il vient de l’informatique, où x \gets 1 se lit « x gets 1 ».

La seconde différence tient à l’emplacement. Un lstlisting reste dans le flux du texte, tandis que le pseudocode va par convention dans un flottant, exactement comme figure ou table. LaTeX l’écarte alors d’une coupure de page malheureuse, lui donne un titre numéroté « Algorithm 1 » et l’inscrit dans \listofalgorithms. Une fois admis le fait structurel unique — le contenant (le flottant) et le contenu (le pseudocode) viennent de packages différents —, les quatre noms déroutants se rangent d’eux-mêmes.

Quel package faut-il réellement charger avec \usepackage ?

Pour un document neuf, la réponse tient en deux lignes. Soit \usepackage{algorithm} à côté de \usepackage{algpseudocode}, soit \usepackage{algorithm2e} tout seul. Presque toute autre combinaison finit mal. La confusion vient de ce que les noms de packages sur CTAN et les noms de fichiers de style ne coïncident pas. algorithm.sty ne provient pas d’un package nommé algorithm mais du lot algorithms — au pluriel. Et algpseudocode.sty provient d’algorithmicx. On tape donc deux noms de fichiers dans le préambule tout en installant deux lots aux noms entièrement différents.

% Camp 1 -- two packages, two jobs. This is the usual choice.
\usepackage{algorithm}      % the float: \begin{algorithm}, \caption, \listofalgorithms
\usepackage{algpseudocode}  % the body:  \begin{algorithmic}, \State, \If, \For

% Camp 2 -- one package does everything. Do NOT also load algorithm.
\usepackage[ruled,vlined,linesnumbered]{algorithm2e}

La rigueur de cette division du travail saute aux yeux dès qu’on ouvre algorithm.sty : moins de cent lignes, et pas une seule ne parle de pseudocode. Le package charge float, déclare un unique nouveau type de flottant avec \newfloat{algorithm}{htbp}{loa}, le nomme « Algorithm » et définit \listofalgorithms — c’est tout (la version livrée avec TeX Live 2024 est la v0.1 du 24 août 2009). Effet de bord réjouissant : toute option qu’il ne reconnaît pas est interprétée comme le nom du flottant. Après \usepackage[Procedure]{algorithm}, toutes les légendes du document affichent « Procedure 1 », « Procedure 2 ».

Quand apparaît Command \algorithm already defined.

Cette erreur ne signifie qu’une chose : algorithm et algorithm2e sont chargés tous les deux. Chacun veut créer un environnement nommé algorithm, et le second arrivé heurte le premier. Supprimez l’un des deux du préambule et c’est réglé. Pour la même raison, la formulation change avec l’ordre de chargement : algorithm2e d’abord et algorithm ensuite donne plutôt ! LaTeX Error: Command \listofalgorithms already defined. — même cause. L’autre message fréquent est ! LaTeX Error: Command \algorithmic already defined., symptôme d’un chargement simultané de l’ancien algorithmic et du plus récent algpseudocode. La famille algorithmicx est le successeur d’algorithmic : les deux ensemble ne servent à rien.

% Each of these three preambles stops the compile.
\usepackage{algorithm}\usepackage{algorithm2e}
%   ! LaTeX Error: Command \algorithm already defined.

\usepackage{algorithm2e}\usepackage{algorithm}
%   ! LaTeX Error: Command \listofalgorithms already defined.

\usepackage{algorithmic}\usepackage{algpseudocode}
%   ! LaTeX Error: Command \algorithmic already defined.

% If a class or a co-author really forces algorithm2e into a document that
% already owns the algorithm float, this option renames the environment to
% algorithm2e and \listofalgorithms to \listofalgorithmes, so nothing collides.
\usepackage[algo2e]{algorithm2e}

La combinaison la plus pénible, pourtant, ne produit aucune erreur. Chargez algorithm2e et algpseudocode côte à côte : le document se compile sans broncher. En effet, lorsqu’algorithmicx définit un nom destiné à l’utilisateur comme \For ou \If, il vérifie d’abord si ce nom existe déjà et, le cas échéant, renonce silencieusement à le définir. Les significations d’algorithm2e survivent donc, et rien ne casse jusqu’au moment où l’on rédige un corps algorithmic : surgit alors, sur la ligne du \EndWhile, quelque chose d’apparemment sans rapport, du genre ! Missing number, treated as zero.. Casser aussi loin que possible de la cause est sans doute pire qu’une erreur franche. C’est précisément pour désamorcer ce type de collision qu’algorithm2e propose l’option algo2e; avec elle, \listofalgorithms devient \listofalgorithmes, orthographié autrement — une trace de l’origine francophone du package.

\begin{algorithm} est un flottant : \caption, \label, [H]

algorithm est un flottant véritable, au sens exact où figure et table le sont. Son placement par défaut est htbp — ici, en haut, en bas, puis sur une page dédiée — et son fichier de liste porte l’extension .loa. Tout ce que l’on sait des figures se transpose donc : \caption{…} produit le titre numéroté « Algorithm 1 », et un \label{alg:…} placé juste après permet au texte de récupérer le numéro avec \ref{alg:power} et la page avec \pageref{alg:power}. Si le \label précède la \caption, le numéro sort faux — décalé d’un cran, ou celui de la section : l’ordre compte. Un \listofalgorithms en tête de document — le frère de \listoffigures et \listoftables — donne une « List of Algorithms » associant chaque numéro à son texte de légende. Comme toujours, numéros, renvois et liste ne se stabilisent qu’après deux compilations. Et lorsque flotter est précisément ce qu’on ne veut pas, \begin{algorithm}[H] fixe la boîte à l’endroit écrit — [H] fonctionne d’emblée puisqu’algorithm charge déjà le package float.

Écrire le corps : \State, \If, \For, \While, \Function

L’environnement intérieur s’appelle algorithmic — dernier piège de la nomenclature : le package s’appelle algpseudocode, l’environnement non. Toutes les commandes sont en casse titre : \State ouvre une ligne d’instruction, et les blocs se ferment explicitement avec \If … \EndIf, \For … \EndFor, etc. L’argument optionnel initial fixe l’intervalle de numérotation : [1] numérote chaque ligne, [5] une sur cinq, et l’omettre n’en numérote aucune. L’exemple ci-dessous est une recherche dichotomique; il met en jeu des branchements, une boucle, une fonction, une précondition et un commentaire de fin de ligne.

\documentclass{article}
\usepackage{algorithm}
\usepackage{algpseudocode}
\begin{document}
\listofalgorithms

\begin{algorithm}
  \caption{Binary search}\label{alg:bsearch}
  \begin{algorithmic}[1]
    \Require sorted array $a[1..n]$, key $k$
    \Ensure index of $k$, or $0$
    \Function{Search}{$a,k$}
      \State $lo \gets 1$;\ $hi \gets n$ \label{ln:init}
      \While{$lo \le hi$}
        \State $m \gets \lfloor (lo+hi)/2 \rfloor$ \Comment{midpoint}
        \If{$a[m] = k$}
          \State \Return $m$
        \ElsIf{$a[m] < k$}
          \State $lo \gets m+1$
        \Else
          \State $hi \gets m-1$
        \EndIf
      \EndWhile
      \State \Return $0$
    \EndFunction
  \end{algorithmic}
\end{algorithm}

Algorithm~\ref{alg:bsearch} halves the interval; the bounds are set on
line~\ref{ln:init}, page~\pageref{alg:bsearch}.

\end{document}

Voici le résultat. Une boîte encadrée de règles en haut et en bas vient flotter sur la page, titrée « Algorithm 1 Binary search ». À l’intérieur, \Require et \Ensure produisent les libellés gras Require: et Ensure:, placés hors de la numérotation. Les numéros démarrent à la ligne du \Function et se suivent en marge gauche : 1, 2, 3 …; \Comment{midpoint} compose un petit triangle en fin de ligne : ▷ midpoint. Le nom de \Function{Search}{$a,k$} est composé en petites capitales, et pour l’appeler depuis une autre ligne on écrit \Call{Search}{$a,k$}. Beaucoup souhaitent d’autres libellés : les chaînes Require: et Ensure: résident dans \algorithmicrequire et \algorithmicensure, si bien que \renewcommand{\algorithmicrequire}{\textbf{Input:}} donne Input:.

L’accident le plus fréquent dans ce camp est l’oubli d’un \State, et il ne produit aucune erreur. Faites suivre \State $x \gets 1$ d’un simple $y \gets 2$ et la sortie affiche « 1: x ← 1 y ← 2 » : deux instructions tassées sur une ligne, et un numéro de moins. Si le compte des lignes semble faux, cherchez d’abord ici. Par ailleurs, si un vieux modèle de conférence emploie des commandes tout en capitales comme \STATE, \WHILE, \ENDWHILE, c’est le dialecte algorithmic de 1994. Pour réutiliser tel quel un manuscrit de ce genre, chargez \usepackage{algcompatible} au lieu d’algpseudocode : les commandes majuscules continuent de fonctionner, sur le socle d’algorithmicx.

Numéroter les lignes et renvoyer à « la ligne 3 »

Les numéros de ligne sont référençables. Ouvrez l’environnement algorithmic avec [1], placez \label{ln:init} à la fin de la ligne visée, et \ref{ln:init} dans le texte se développe en son numéro. Dans l’exemple ci-dessus, la ligne du \Function porte le 1, donc \ref{ln:init} donne 2. Cela compte davantage qu’il n’y paraît : écrire « le test de la ligne 3 » à la main transforme votre prose en mensonge dès qu’une instruction s’ajoute. Le procédé est identique dans algorithm2e : activez linesnumbered et placez \label{…} après le \; qui clôt la ligne. Une réserve : étiqueter une ligne non numérotée n’a pas de sens, car sans [1] ni linesnumbered il n’existe aucun numéro à viser.

algorithm2e : des accolades au lieu de \End…, et le \; à ne pas oublier

L’autre camp ne ferme pas un bloc par une commande du type \EndFor. Il passe le corps en argument entre accolades — \For{condition}{corps}, \While{condition}{corps}, et pour if–then–else \eIf{cond}{then}{else} (\uIf sans else, \lIf pour tenir sur une ligne). L’entrée et la sortie ont des commandes dédiées, \KwIn{…} et \KwOut{…}, composées en Input: et Output: gras (\KwData{…} et \KwResult{…} si l’on préfère les mots Data: et Result:). Le grand piège : chaque instruction doit se terminer par \;. L’oublier ne provoque aucune erreur — l’instruction suivante enchaîne simplement sur la même ligne. Pour ne pas voir le « ; » à l’impression, \DontPrintSemicolon le masque (le \; reste obligatoire). Toute l’apparence se règle au chargement : ruled (règles en haut et en bas), boxed (boîte autour de l’ensemble), vlined et lined (deux façons de tracer les traits verticaux de bloc), plain (par défaut), plus linesnumbered pour les numéros de ligne. Ces trois options de trait sont littéralement les commandes \SetAlgoVlined, \SetAlgoLined et \SetAlgoNoLine appliquées à votre place. TeX Live 2024 livre la v5.2, datée du 18 juillet 2017.

\documentclass{article}
\usepackage[ruled,vlined,linesnumbered]{algorithm2e}
\begin{document}
\listofalgorithms

\begin{algorithm}
  \DontPrintSemicolon
  \KwIn{an array $a[1..n]$}
  \KwOut{the sum $s$ of its positive entries}
  $s \gets 0$\;\label{ln:zero}
  \For{$i \gets 1$ \KwTo $n$}{
    \eIf{$a[i] > 0$}{
      $s \gets s + a[i]$\;
    }{
      \tcp{negative or zero: skip}
    }
  }
  \Return $s$\;
  \caption{Sum of positive entries}\label{alg:sum}
\end{algorithm}

Algorithm~\ref{alg:sum} accumulates into $s$, initialised on line~\ref{ln:zero}.

\end{document}

Le titre sort en « Algorithm 1: Sum of positive entries » — les deux-points après le numéro constituent la différence visible avec le flottant algorithm. Au-dessus du corps figurent Input: et Output:; le corps se lit for i ← 1 to n do et if … then … else, avec un trait vertical à gauche de chaque bloc puisque vlined a été demandé. \tcp{…} est un commentaire en ligne et s’imprime // negative or zero: skip. Remarquez que \caption est écrit à la fin de l’environnement : c’est la convention d’algorithm2e, et avec ruled le titre apparaît malgré tout en haut de la boîte. Le même texte alimente \listofalgorithms. Enfin, l’environnement algorithm2e étant lui aussi flottant par défaut, \begin{algorithm}[H] reste disponible pour le fixer.

Des mots-clés en français : l’option onelanguage

algorithm2e sait traduire les mots-clés du pseudocode lui-même. Seul ce camp le propose; algpseudocode n’a pas d’équivalent. Les options disponibles sont french, german, ngerman, spanish, italiano, portuguese, czech, slovak, croatian et english. Le comportement comporte toutefois une marche. \usepackage[french]{algorithm2e} seul renomme le flottant en « Algorithme 1 : » mais laisse \For et \eIf s’imprimer en anglais : pour obtenir du français, il faut employer les noms de commandes français, \Pour{…}{…}, \Si{…}{…}, \KwA. Si l’on préfère ne pas réécrire les noms de commandes d’un manuscrit existant, on ajoute onelanguage : avec \usepackage[french,onelanguage]{algorithm2e}, les mêmes \For et \eIf produisent pour i ← 1 à n faire et si … alors … sinon … fin. En allemand, [german,onelanguage] donne für i ← 1 bis n tue, wenn … dann … sonst … Ende, sous le titre « Algorithmus 1: ».

% Keep the English command names, print French keywords.
\usepackage[french,onelanguage,ruled,linesnumbered]{algorithm2e}
%   \For{...}{...}  ->  pour i <- 1 a n faire ... fin

% Without onelanguage, only the float name is translated; use the
% French command names for a French body.
\usepackage[french,ruled]{algorithm2e}
%   \Pour{...}{...}, \Si{...}{...}, \KwA

Alors, lequel choisir : algpseudocode ou algorithm2e

Si le modèle de la revue ou de la conférence en désigne un, suivez-le : beaucoup de classes de conférence règlent marges et polices autour d’un choix précis. Sinon : algpseudocode si le pseudocode doit se lire comme un texte mathématique, et algorithm2e s’il faut des déclarations d’entrée/sortie explicites, des traits de bloc ou des mots-clés traduits. Le tableau règle le reste.

Quel que soit le choix, la couche de présentation est identique : \caption donne le titre numéroté, \label et \ref permettent au texte de le viser, \listofalgorithms construit la liste, et deux compilations stabilisent les numéros. Et une dernière fois, car c’est toute la leçon de cette page : exactement un package de corps par document. Avec algorithm2e, ne jamais charger algorithm. Avec algpseudocode, ne jamais charger algorithmic. Cette seule ligne de discipline évite la quasi-totalité des accidents liés aux quatre noms confondables du début. Si ce que l’on veut est du vrai code source avec coloration syntaxique et numéros de ligne plutôt que du pseudocode, la page voisine consacrée à listings et minted est la bonne destination.