IT博客汇 | LaTeX Application Notes: Pseudocode (with examples)

LaTeX Application Notes: Pseudocode (with examples)

SparkandShine发表于 2016-10-31 22:03:28

This article presents two notable algorithm typesetting environments: algorithmic and algorithmicx with illustrated examples.

1. Overview

LaTeX has several packages for typesetting algorithms in form of pseudocode. There are four notable packages: algorithmic, algorithmicx, algorithm2e and program^[1]. In a nutshell^[2]，

algorithm – float wrapper for algorithms (provide a floating environment for algorithms).
algorithmic – algorithm typesetting environment.
algorithmicx – algorithm typesetting environment.
algpseudocode – layout for algorithmicx.
algorithm2e – algorithm typesetting environment.
program – algorithm typesetting environment

The package algorithmicx is like algorithmic upgraded. algorithm2e is an environment for writing algorithms in LaTeX2e. It allows typesetting algorithms with a lot of customization.

2. algorithm

The algorithm environment provides a floating environment for algorithms. It enables to wrap around algorithms to avoid it being split over pages.

\begin{algorithm}
    \caption{Algorithm caption}
    \label{alg:algorithm-label (for references later in your document)}
    \begin{algorithmic}
        ...pseudocode...
    \end{algorithmic}
\end{algorithm}

Other useful features are below.

% Algorithm numbering
\usepackage[chapter]{algorithm}     % part, chapter, section, subsection, subsubsection or nothing (default)

% List of algorithms
\listofalgorithms

% Change the name of the label Algorithm
\floatname{algorithm}{算法}

\makeatletter
\renewcommand{\ALG@name}{算法}
\makeatother

% Rename require/ensure to input/output:
\renewcommand{\algorithmicrequire}{\textbf{Input:}}
\renewcommand{\algorithmicensure}{\textbf{Output:}}

3. algorithmicx

3.1 An example

Put \usepackage{algpseudocode} (algorithmicx will be loaded automatically) in the preamble to use the algorithmic environment. Here is a minimum working example.

\documentclass{article}

\usepackage{algorithm}          %  float wrapper for algorithms.
\usepackage{algpseudocode}      % layout for algorithmicx

\usepackage{amsmath}            % AMS mathematical facilities for LATEX

% Nice looking for empty set
\usepackage{amssymb}            %  provides an extended symbol collection
\let\oldemptyset\emptyset
\let\emptyset\varnothing

\begin{document}

% algorithm 
\begin{algorithm}
    \begin{algorithmic}%[1]
        \caption{CDS with betweenness centrality} \label{algorithm: cds bw}
        \Require A connected graph $G(V, E)$
        \State $d \gets \{v : bw(v)\}, v \in V$, sort by BW on ascending order
        \State $V' \gets \emptyset$, connected dominating sets
        \ForAll{$v$ : $bw(v), v \notin V'$}
            \If{$bw(v) = 0$ OR $G(V-\{v\})$ is connected}
                \State $V' \gets V' \cup MAX-BW(N(v))$      
            \Else
                \State $V' \gets V' \cup \{v\}$
            \EndIf
            \State $V \gets V-\{v\}$
        \EndFor             
    \end{algorithmic}
\end{algorithm}

\end{document}

which produces,

an-example-of-pseudocode-produced-by-algorithmicx
Fig. 1: An example of pseudocode produced by algorithmicx

3.2 Basic commands

Basic commands are,

% Pre- and postcondition:
\Require <text>
\Ensure <text>

% Functions
\Function{<name>}{<params>} <body> \EndFunction
\Return <text>
\Call{<name>}{<params>}

% Statement (\State causes a new line, can also be used in front of other commands)
\State $x\gets <value>$
% Comments:
\Comment{<text>}

% Three forms of if-statements
\If{<condition>} <text> \EndIf
\If{<condition>} <text> \Else <text> \EndIf
\If{<condition>} <text> \ElsIf{<condition>} <text> \Else <text> \EndIf

% Loops:
\For{<condition>} <text> \EndFor
\ForAll{<condition>} <text> \EndFor
\While{<condition>} <text> \EndWhile
\Repeat <text> \Until{<condition>}
\Loop <text> \EndLoop

4. algorithmic

4.1 A minimum working example

The above example is adapted for algorithmic.

\documentclass{article}

\usepackage{algorithm}          %  float wrapper for algorithms.
\usepackage{algorithmic} 

\usepackage{amsmath}            % AMS mathematical facilities for LATEX

% Nice looking for empty set
\usepackage{amssymb}            %  provides an extended symbol collection
\let\oldemptyset\emptyset
\let\emptyset\varnothing

\begin{document}

% algorithm 
\begin{algorithm}
    \begin{algorithmic}%[1]
        \caption{CDS with betweenness centrality} \label{algorithm: cds bw}
        \REQUIRE A connected graph $G(V, E)$
        \STATE $d \gets \{v : bw(v)\}, v \in V$, sort by BW on ascending order
        \STATE $V' \gets \emptyset$, connected dominating sets
        \FORALL{$v$ : $bw(v), v \notin V'$}
            \IF{$bw(v) = 0$ OR $G(V-\{v\})$ is connected}
                \STATE $V' \gets V' \cup MAX-BW(N(v))$      
            \ELSE
                \STATE $V' \gets V' \cup \{v\}$
            \ENDIF
            \STATE $V \gets V-\{v\}$
        \ENDFOR             
    \end{algorithmic}
\end{algorithm}

\end{document}

4.2 Basic commands

The algorithmic package (use all capital letters) uses a similar set of commands as the algorithmicx package (capitalize the first letter). Basic commands are:

\REQUIRE <text>
\ENSURE <text>

\STATE <text>
\COMMENT{<text>}

\IF{<condition>} \STATE {<text>} \ELSE \STATE{<text>} \ENDIF
\IF{<condition>} \STATE {<text>} \ELSIF{<condition>} \STATE{<text>} \ENDIF

\FOR{<condition>} \STATE {<text>} \ENDFOR
\FOR{<condition> \TO <condition> } \STATE {<text>} \ENDFOR
\FORALL{<condition>} \STATE{<text>} \ENDFOR
\WHILE{<condition>} \STATE{<text>} \ENDWHILE
\REPEAT \STATE{<text>} \UNTIL{<condition>}
\LOOP \STATE{<text>} \ENDLOOP

\RETURN <text>
\PRINT <text>

\AND, \OR, \XOR, \NOT, \TO, \TRUE, \FALSE

PS: The related source code is shared on my GitHub, here.

References:
[1] Wikibooks: LaTeX Algorithms
[1] TeX – LaTeX: algorithm, algorithmic, algorithmicx, algorithm2e, algpseudocode = confused
[2] 博文：LaTeX/Algorithms 伪代码
[3] TeX – LaTeX: What does each AMS package do?