\input cwebmac
% This file is part of the Stanford GraphBase (c) Stanford University 1993
% This material goes at the beginning of all Stanford GraphBase CWEB files

\def\topofcontents{
  \leftline{\sc\today\ at \hours}\bigskip\bigskip
  \centerline{\titlefont\title}}

\font\ninett=cmtt9
\def\botofcontents{\vskip 0pt plus 1filll
    \ninerm\baselineskip10pt
    \noindent\copyright\ 1993 Stanford University
    \bigskip\noindent
    This file may be freely copied and distributed, provided that
    no changes whatsoever are made. All users are asked to help keep
    the Stanford GraphBase files consistent and ``uncorrupted,''
    identical everywhere in the world. Changes are permissible only
    if the modified file is given a new name, different from the names of
    existing files in the Stanford GraphBase, and only if the modified file is
    clearly identified as not being part of that GraphBase.
    (The {\ninett CWEB} system has a ``change file'' facility by
    which users can easily make minor alterations without modifying
    the master source files in any way. Everybody is supposed to use
    change files instead of changing the files.)
    The author has tried his best to produce correct and useful programs,
    in order to help promote computer science research,
    but no warranty of any kind should be assumed.
    \smallskip\noindent
    Preliminary work on the Stanford GraphBase project
    was supported in part by National Science
    Foundation grant CCR-86-10181.}

\def\prerequisite#1{\def\startsection{\noindent
    Important: Before reading {\sc\title},
    please read or at least skim the program for {\sc#1}.\bigskip
    \let\startsection=\stsec\stsec}}
\def\prerequisites#1#2{\def\startsection{\noindent
    Important: Before reading {\sc\title}, please read
    or at least skim the programs for {\sc#1} and {\sc#2}.\bigskip
    \let\startsection=\stsec\stsec}}


% PostScript is a registered trade mark of Adobe Systems Incorporated.

\def\title{ASSIGN\_\,LISA}
\def\<#1>{$\langle${\rm#1}$\rangle$}
\def\dash{\mathrel-\joinrel\joinrel\mathrel-} % adjacent vertices
\def\ddash{\mathrel{\above.2ex\hbox to1.1em{}}}  % matched vertices

\prerequisite{GB\_\,LISA}

\N{1}{1}The assignment problem.
This demonstration program takes a matrix of numbers
constructed by the {\sc GB\_\,LISA} module and chooses at most one number from
each row and column in such a way as to maximize the sum of the numbers
chosen. It also reports the number of ``mems'' (memory references)
expended during its computations, so that the algorithm it uses
can be compared with alternative procedures.

The matrix has $m$ rows and $n$ columns. If $m\le n$, one number will
be chosen in each row; if $m\ge n$, one number will be chosen in each column.
The numbers in the matrix are brightness levels (pixel values) in
a digitized version of the Mona Lisa.

Of course the author does not pretend that the location of ``highlights'' in
da Vinci's painting, one per row and one per column, has any application
to art appreciation. However, this program does seem to have pedagogic value,
because the relation between pixel values and shades of gray allows us
to visualize the data underlying this special case of the
assignment problem; ordinary matrices of numeric data are much harder
to perceive. The nonrandom nature of pixels
in a work of art might also have similarities to the ``organic'' properties
of data in real-world applications.

This program is optionally able to produce an encapsulated PostScript file
from which the solution can be displayed graphically, with halftone shading.

\fi

\M{2}As explained in {\sc GB\_\,LISA}, the subroutine call
\PB{$\\{lisa}(\|m,\|n,\|d,\\{m0},\\{m1},\\{n0},\\{n1},\\{d0},\\{d1},\hbox{%
\\{area}})$} constructs an $m\times n$
matrix of integers between $0$ and~$d$, inclusive, based on the brightness
levels in a rectangular region of a digitized Mona Lisa, where \PB{\\{m0}},
\PB{\\{m1}}, \PB{\\{n0}}, and \PB{\\{n1}} define that region. The raw data is
obtained as a
sum of \PB{$(\\{m1}-\\{m0})(\\{n1}-\\{n0})$} pixel values between $0$
and~$255$, then
scaled in such a way that sums \PB{$\Z$ \\{d0}} are mapped to zero, sums \PB{$%
\G$ \\{d1}}
are mapped to~$d$, and intermediate sums are mapped linearly to
intermediate values. Default values \PB{$\\{m1}\K\T{360}$}, \PB{$\\{n1}\K%
\T{250}$}, \PB{$\|m\K\\{m1}-\\{m0}$},
\PB{$\|n\K\\{n1}-\\{n0}$}, \PB{$\|d\K\T{255}$}, and \PB{$\\{d1}\K\T{255}(%
\\{m1}-\\{m0})(\\{n1}-\\{n0})$} are substituted if any
of the parameters \PB{\|m}, \PB{\|n}, \PB{\|d}, \PB{\\{m1}}, \PB{\\{n1}}, or %
\PB{\\{d1}} are zero.

The user can specify the nine parameters \PB{$(\|m,\|n,\|d,\\{m0},\\{m1},%
\\{n0},\\{n1},\\{d0},\\{d1})$}
on the command line, at least in a \UNIX/ implementation, thereby
obtaining a variety of special effects; the relevant
command-line options are \.{m=}\<number>, \.{m0=}\<number>, and so on,
with no spaces before or after the \.= signs that separate parameter
names from parameter values. Additional options are also provided:
\.{-s} (use only Mona Lisa's $16\times32$ ``smile'');
\.{-e} (use only her $20\times50$ eyes);
\.{-c} (complement black/white); \.{-p} (print the matrix and solution);
\.{-P} (produce a PostScript file \.{lisa.eps} for graphic output);
\.{-h} (use a heuristic that applies only when $m=n$); and
\.{-v} or \.{-V} (print verbose or Very verbose commentary about the
algorithm's performance).

Here is the overall layout of this \CEE/ program:

\Y\B\8\#\&{include} \.{"gb\_graph.h"}\C{ the GraphBase data structures }\6
\8\#\&{include} \.{"gb\_lisa.h"}\C{ the \PB{\\{lisa}} routine }\6
\ATH\7
\X3:Global variables\X\6
$\\{main}(\\{argc},\39\\{argv}){}$\1\1\6
\&{int} \\{argc};\C{ the number of command-line arguments }\6
\&{char} ${}{*}\\{argv}[\,]{}$;\C{ an array of strings containing those
arguments }\6
$\{{}$\5
\X4:Local variables\X\7
\X5:Scan the command-line options\X;\6
${}\\{mtx}\K\\{lisa}(\|m,\39\|n,\39\|d,\39\\{m0},\39\\{m1},\39\\{n0},\39\\{n1},%
\39\\{d0},\39\\{d1},\39\\{working\_storage});{}$\6
\&{if} ${}(\\{mtx}\E\NULL){}$\5
${}\{{}$\1\6
${}\\{fprintf}(\\{stderr},\39\.{"Sorry,\ can't\ create}\)\.{\ the\ matrix!\
(error\ }\)\.{code\ \%ld)\\n"},\39\\{panic\_code});{}$\6
\&{return} ${}{-}\T{1};{}$\6
\4${}\}{}$\2\6
\\{printf} $(\.{"Assignment\ problem\ }\)\.{for\ \%s\%s\\n"},\39\\{lisa\_id},%
\39$ ( $\MRL{\Xcompl{\?\.{",\ complemented"}:}}$ \.{""} ) )  ;\6
${}\\{sscanf}(\\{lisa\_id},\39\.{"lisa(\%lu,\%lu,\%lu"},\39{\AND}\|m,\39{\AND}%
\|n,\39{\AND}\|d){}$;\C{ adjust for defaults }\6
\&{if} ${}(\|m\I\|n){}$\1\5
${}\\{heur}\K\T{0};{}$\2\6
\&{if} (\\{printing})\1\5
\X6:Display the input matrix\X;\2\6
\&{if} (\\{PostScript})\1\5
\X28:Output the input matrix in PostScript format\X;\2\6
${}\\{mems}\K\T{0};{}$\6
\X24:Solve the assignment problem\X;\6
\&{if} (\\{printing})\1\5
\X27:Display the solution\X;\2\6
\&{if} (\\{PostScript})\1\5
\X31:Output the solution in PostScript format\X;\2\6
${}\\{printf}(\.{"Solved\ in\ \%ld\ mems\%}\)\.{s.\\n"},\39\\{mems},\39(%
\\{heur}\?\.{"\ with\ square-matrix}\)\.{\ heuristic"}:\.{""}));{}$\6
\&{return} \T{0};\C{ normal exit }\6
$\}{}$\par
\fi

\M{3}\B\X3:Global variables\X${}\E{}$\6
\&{Area} \\{working\_storage};\C{ where to put the input data and auxiliary
arrays }\6
\&{long} ${}{*}\\{mtx}{}$;\C{ input data for the assignment problem }\6
\&{long} \\{mems};\C{ the number of memory references counted
  while solving the problem }\par
\A29.
\U2.\fi

\M{4}The following local variables are related to the command-line options:

\Y\B\4\X4:Local variables\X${}\E{}$\6
\&{unsigned} \&{long} \|m${}\K\T{0},{}$ \|n${}\K\T{0}{}$;\C{ number of rows and
columns desired }\6
\&{unsigned} \&{long} \|d${}\K\T{0}{}$;\C{ number of pixel values desired,
minus~1 }\6
\&{unsigned} \&{long} \\{m0}${}\K\T{0},{}$ \\{m1}${}\K\T{0}{}$;\C{ input will
be from rows $[\PB{\\{m0}}\,.\,.\,\PB{\\{m1}})$ }\6
\&{unsigned} \&{long} \\{n0}${}\K\T{0},{}$ \\{n1}${}\K\T{0}{}$;\C{ and from
columns $[\PB{\\{n0}}\,.\,.\,\PB{\\{n1}})$ }\6
\&{unsigned} \&{long} \\{d0}${}\K\T{0},{}$ \\{d1}${}\K\T{0}{}$;\C{ lower and
upper threshold of raw pixel scores }\6
\&{long} ${}{\Xcompl}\K\T{0}{}$;\C{ should the input values be complemented? }\6
\&{long} \\{heur}${}\K\T{0}{}$;\C{ should the square-matrix heuristic be used?
}\6
\&{long} \\{printing}${}\K\T{0}{}$;\C{ should the input matrix and solution be
printed? }\6
\&{long} \\{PostScript}${}\K\T{0}{}$;\C{ should an encapsulated PostScript file
be produced? }\par
\As13, 14\ETs26.
\U2.\fi

\M{5}\B\X5:Scan the command-line options\X${}\E{}$\6
\&{while} ${}(\MM\\{argc})$ $\{$ \6
\&{if} ${}(\\{sscanf}(\\{argv}[\\{argc}],\39\.{"m=\%lu"},\39{\AND}\|m)\E%
\T{1}){}$\1\5
;\2\6
\&{else} \&{if} ${}(\\{sscanf}(\\{argv}[\\{argc}],\39\.{"n=\%lu"},\39{\AND}\|n)%
\E\T{1}){}$\1\5
;\2\6
\&{else} \&{if} ${}(\\{sscanf}(\\{argv}[\\{argc}],\39\.{"d=\%lu"},\39{\AND}\|d)%
\E\T{1}){}$\1\5
;\2\6
\&{else} \&{if} ${}(\\{sscanf}(\\{argv}[\\{argc}],\39\.{"m0=\%lu"},\39{\AND}%
\\{m0})\E\T{1}){}$\1\5
;\2\6
\&{else} \&{if} ${}(\\{sscanf}(\\{argv}[\\{argc}],\39\.{"m1=\%lu"},\39{\AND}%
\\{m1})\E\T{1}){}$\1\5
;\2\6
\&{else} \&{if} ${}(\\{sscanf}(\\{argv}[\\{argc}],\39\.{"n0=\%lu"},\39{\AND}%
\\{n0})\E\T{1}){}$\1\5
;\2\6
\&{else} \&{if} ${}(\\{sscanf}(\\{argv}[\\{argc}],\39\.{"n1=\%lu"},\39{\AND}%
\\{n1})\E\T{1}){}$\1\5
;\2\6
\&{else} \&{if} ${}(\\{sscanf}(\\{argv}[\\{argc}],\39\.{"d0=\%lu"},\39{\AND}%
\\{d0})\E\T{1}){}$\1\5
;\2\6
\&{else} \&{if} ${}(\\{sscanf}(\\{argv}[\\{argc}],\39\.{"d1=\%lu"},\39{\AND}%
\\{d1})\E\T{1}){}$\1\5
;\2\6
\&{else} \&{if} ${}(\\{strcmp}(\\{argv}[\\{argc}],\39\.{"-s"})\E\T{0}){}$\5
${}\{{}$\1\6
\\{smile};\C{ sets \PB{\\{m0}}, \PB{\\{m1}}, \PB{\\{n0}}, \PB{\\{n1}} }\6
${}\\{d1}\K\T{100000}{}$;\C{ makes the pixels brighter }\6
\4${}\}{}$\2\6
\&{else} \&{if} ${}(\\{strcmp}(\\{argv}[\\{argc}],\39\.{"-e"})\E\T{0}){}$\5
${}\{{}$\1\6
\\{eyes};\6
${}\\{d1}\K\T{200000};{}$\6
\4${}\}{}$\2\6
\&{else} \&{if} ${}(\\{strcmp}(\\{argv}[\\{argc}],\39\.{"-c"})\E\T{0})$ $\MRL{%
\Xcompl{\K}}$ \T{1};\6
\&{else}\1\6
\&{if} ${}(\\{strcmp}(\\{argv}[\\{argc}],\39\.{"-h"})\E\T{0}){}$\1\5
${}\\{heur}\K\T{1};{}$\2\6
\&{else} \&{if} ${}(\\{strcmp}(\\{argv}[\\{argc}],\39\.{"-v"})\E\T{0}){}$\1\5
${}\\{verbose}\K\T{1};{}$\2\6
\&{else} \&{if} ${}(\\{strcmp}(\\{argv}[\\{argc}],\39\.{"-V"})\E\T{0}){}$\1\5
${}\\{verbose}\K\T{2}{}$;\C{ terrifically verbose }\2\6
\&{else} \&{if} ${}(\\{strcmp}(\\{argv}[\\{argc}],\39\.{"-p"})\E\T{0}){}$\1\5
${}\\{printing}\K\T{1};{}$\2\6
\&{else} \&{if} ${}(\\{strcmp}(\\{argv}[\\{argc}],\39\.{"-P"})\E\T{0}){}$\1\5
${}\\{PostScript}\K\T{1};{}$\2\6
\&{else}\5
${}\{{}$\1\6
${}\\{fprintf}(\\{stderr},\39\.{"Usage:\ \%s\ [param=va}\)\.{lue]\ [-s]\ [-c]\
[-h]\ }\)\.{[-v]\ [-p]\ [-P]\\n"},\39\\{argv}[\T{0}]);{}$\6
\&{return} ${}{-}\T{2};{}$\6
\4${}\}{}$\2\2\6
$\}{}$\par
\U2.\fi

\M{6}\B\X6:Display the input matrix\X${}\E{}$\6
\&{for} ${}(\|k\K\T{0};{}$ ${}\|k<\|m;{}$ ${}\|k\PP)$ $\{$ \&{for} ${}(\|l\K%
\T{0};{}$ ${}\|l<\|n;{}$ ${}\|l\PP)$ \\{printf} $(\.{"\%\ 4ld"},\39$ $\MRL{%
\Xcompl{\?\|d-{*}(\\{mtx}+\|k*\|n+\|l):}}$ ${*}(\\{mtx}+\|k*\|n+\|l)$ )  ;\6
\\{printf}(\.{"\\n"}); $\}{}$\par
\U2.\fi

\M{7}We obtain a crude but useful estimate of the computation time
by counting mem units, as explained in the {\sc MILES\_\,SPAN} program.

\Y\B\4\D$\|o$ \5
$\\{mems}\PP{}$\par
\B\4\D$\\{oo}$ \5
$\\{mems}\MRL{+{\K}}{}$\T{2}\par
\B\4\D$\\{ooo}$ \5
$\\{mems}\MRL{+{\K}}{}$\T{3}\par
\fi

\N{1}{8}Algorithmic overview. The assignment problem is the classical
problem of weighted bipartite matching: to choose
a maximum-weight set of disjoint edges in a bipartite graph. We will consider
only the case of complete bipartite graphs, when the weights are
specified by an $m\times n$ matrix.

An algorithm is most easily developed if we begin with the assumption
that the matrix is square (i.e., that $m=n$), and if we change from
maximization to minimization. Then the assignment problem is the task
of finding a permutation $\pi[0]\ldots\pi[n-1]$ of $\{0,\ldots,n-1\}$
such that $\sum_{k=0}^{n-1} a_{k\pi[k]}$ is minimized, where
$A=(a_{kl})$ is a given matrix of numbers $a_{kl}$ for $0\le k,l<n$.
The algorithm below works for arbitrary real numbers $a_{kl}$, but we
will assume in our implementation that the matrix entries are integers.

One way to approach the assignment problem is to make three simple
observations: (a)~Adding a constant to any row of the matrix does not
change the solution $\pi[0]\ldots\pi[n-1]$. (b)~Adding a constant to
any column of the matrix does not change the solution. (c)~If $a_{kl}\ge0$
for all $k$ and~$l$, and if $\pi[0]\ldots\pi[n-1]$ is a permutation
with the property that $a_{k\pi[k]}=0$ for all~$k$, then $\pi[0]\ldots\pi[n-1]$
solves the assignment problem.

The remarkable fact is that these three observations actually suffice. In
other words, there is always a sequence of constants $(\sigma_0,\ldots,\sigma_
{n-1})$ and $(\tau_0,\ldots,\tau_{n-1})$ and a permutation $\pi[0]\ldots
\pi[n-1]$ such that
$$\vbox{\halign{$#$,\hfil&\quad for #\hfil\cr
a_{kl}-\sigma_k+\tau_{\,l}\ge0& $0\le k<n$ and $0\le l<n$;\cr
a_{k\pi[k]}-\sigma_k+\tau_{\pi[k]}=0& $0\le k<n$.\cr}}$$

\fi

\M{9}To prove the remarkable fact just stated, we start by reviewing the
theory of {\sl unweighted\/} bipartite matching. Any $m\times n$ matrix
$A=(a_{kl})$ defines a bipartite graph on the vertices $(r_0,\ldots,r_{m-1})$
and $(c_0,\ldots,c_{n-1})$ if we say that $r_k\dash c_l$ whenever
$a_{kl}=0$; in other words, the edges of the bipartite graph are the zeroes
of the matrix. Two zeroes of~$A$ are called {\sl independent\/} if they appear
in different rows and columns; this means that the corresponding edges have
no vertices in common. A set of mutually independent zeroes of the matrix
therefore corresponds to a set of mutually disjoint edges, also called a
{\sl matching\/} between rows and columns.

The Hungarian mathematicians Egerv\'ary and K\"onig proved
[{\sl Matematikai \'es Fizikai Lapok\/ \bf38} (1931), 16--28, 116--119]
that the maximum number of independent zeroes in a matrix is equal to
the minimum number of rows and/or columns that are needed to ``cover''
every zero. In other words, if we can find $p$ independent zeroes but
not~$p+1$, then there is a way to choose $p$ lines in such a way that
every zero of the matrix is included in at least one of the chosen lines,
where a ``line'' is either a row or a column.

Their proof was constructive, and it leads to a useful computer algorithm.
Given a set of $p$ independent zeroes of a matrix, let us write
$r_k\ddash c_l$ or $c_l\ddash r_k$ and say that $r_k$ is matched with $c_l$
if $a_{kl}$ is one of these $p$ special
zeroes, while we continue to write $r_k\dash c_l$ or $c_l\dash r_k$
if $a_{kl}$ is one of the nonspecial zeroes. A given set of $p$
special zeroes defines a choice of $p$ lines in the following way: Column~$c$
is chosen if and only if it is reachable by a path of the form
$$r^{(0)}\dash c^{(1)}\ddash r^{(1)}\dash c^{(2)}\ddash\cdots
\dash c^{(q)}\ddash r^{(q)}\,,\eqno(*)$$
where $r^{(0)}$ is unmatched, $q\ge1$, and $c=c^{(q)}$. Row~$r$ is chosen if
and only if it is matched with a column that is not chosen. Thus exactly
$p$ lines are chosen. We can now prove that the chosen lines cover
all the zeroes, unless there is a way to find $p+1$ independent zeroes.

For if $c\ddash r$, either $c$ or $r$ has been chosen. And
if $c\dash r$, one of the following cases must arise. (1)~If $r$ and~$c$
are both unmatched, we can increase~$p$ by matching them to each other.
(2)~If $r$ is unmatched and $c\ddash r'$, then $c$ has been chosen, so
the zero has been covered. (3)~If $r$ is matched to $c'\ne c$, then
either $r$ has been chosen or $c'$ has been chosen. In the latter case,
there is a path of the form
$$r^{(0)}\dash c^{(1)}\ddash r^{(1)}\dash c^{(2)}\ddash\cdots\ddash
r^{(q-1)}\dash c'\ddash r\dash c\,,$$
where $r^{(0)}$ is unmatched and $q\ge1$.
If $c$ is matched, it has therefore been chosen; otherwise we can increase $p$
by redefining the matching to include
$$r^{(0)}\ddash c^{(1)}\dash r^{(1)}\ddash c^{(2)}\dash\cdots\dash
r^{(q-1)}\ddash c'\dash r\ddash c\,.$$

\fi

\M{10}Now suppose $A$ is a {\sl nonnegative\/} matrix, of size $n\times n$.
Cover the zeroes of~$A$ with a minimum number of lines, $p$, using the
algorithm of Egerv\'ary and K\"onig. If $p<n$, some elements are still
uncovered, so those elements are positive. Suppose the minimum uncovered
value is $\delta>0$. Then we can subtract $\delta$ from each unchosen row
and add $\delta$ to each chosen column. The net effect is to subtract~$\delta$
from all uncovered elements and to add~$\delta$ to all doubly covered
elements, while leaving all singly covered elements unchanged. This
transformation causes a new zero to appear, while preserving
$p$ independent zeroes of the previous matrix (since they were each
\vadjust{\goodbreak}%
covered only once). If we repeat the Egerv\'ary-K\"onig construction
with the same $p$ independent zeroes, we find that either $p$~is no
longer maximum or at least one more column has been chosen.
(The new zero $r\dash c$ occurs in a row~$r$ that was either unmatched
or matched to a previously chosen column, because row~$r$ was not
chosen.) Therefore if we repeat the process, we must eventually
be able to increase $p$ until finally $p=n$. This will solve the
assignment problem, proving the remarkable claim made earlier.

\fi

\M{11}If the given matrix $A$ has $m$ rows and $n>m$ columns,
we can extend it artificially
until it is square, by setting $a_{kl}=0$ for all $m\le k<n$ and
$0\le l<n$. The construction above will then apply. But we need not
waste time making such an extension, because it suffices to run the
algorithm on the original $m\times n$ matrix until $m$ independent zeroes
have been found. The reason is that the set of matched vertices always
grows monotonically in the Egerv\'ary-K\"onig construction: If a
column is matched at some stage, it will remain matched from that time on,
although it might well change partners. The $n-m$ dummy rows at the bottom
of~$A$ are always chosen to be part of the covering; so the dummy entries
become nonzero only in the columns that are part of some covering.
Such columns are part of some matching, so they are part of the
final matching. Therefore at most $m$ columns of the dummy entries
become nonzero during the procedure. We can always find $n-m$ independent
zeroes in the $n-m$ dummy rows of the matrix, so we need not deal with the
dummy elements explicitly.

\fi

\M{12}It has been convenient to describe the algorithm by saying that
we add and subtract constants to and from the columns and rows of~$A$.
But all those additions and subtractions can take a lot of time. So we will
merely pretend to make the adjustments that the method calls for; we will
represent them implicitly by two vectors $(\sigma_0,\ldots,\sigma_{m-1})$
and $(\tau_0,\ldots,\tau_{n-1})$. Then the current value of each matrix
entry will be $a_{kl}-\sigma_k+\tau_{\,l}$, instead of $a_{kl}$. The
``zeroes'' will be positions such that $a_{kl}=\sigma_k-\tau_{\,l}$.

Initially we will set $\tau_{\,l}=0$ for $0\le l<n$ and $\sigma_k=
\min\{a_{k0},\ldots,a_{k(n-1)}\}$ for $0\le k<m$. If $m=n$ we can also
make sure that there's a zero in every column by subtracting
$\min\{a_{0l},\ldots,a_{(n-1)l}\}$ from $a_{kl}$ for all $k$ and~$l$.
(This initial adjustment can conveniently be made to the original
matrix entries, instead of indirectly via the $\tau$'s.) Users can
discover if such a transformation is worthwhile by trying the program
both with and without the \.{-h} option.

We have been saying a lot of things and proving a bunch of theorems,
without writing any code. Let's get back into programming mode
by writing the routine that is called into
action when the \.{-h} option has been specified:

\Y\B\4\D$\\{aa}(\|k,\|l)$ \5
${*}(\\{mtx}+\|k*\|n+\|l{}$)\C{ a macro to access the matrix elements }\par
\Y\B\4\X12:Subtract column minima in order to start with lots of zeroes\X${}%
\E{}$\6
${}\{{}$\1\6
\&{for} ${}(\|l\K\T{0};{}$ ${}\|l<\|n;{}$ ${}\|l\PP){}$\5
${}\{{}$\1\6
${}\|o,\39\|s\K\\{aa}(\T{0},\39\|l){}$;\C{ the \PB{\|o} macro counts one mem }\6
\&{for} ${}(\|k\K\T{1};{}$ ${}\|k<\|n;{}$ ${}\|k\PP){}$\1\6
\&{if} ${}(\|o,\39\\{aa}(\|k,\39\|l)<\|s){}$\1\5
${}\|s\K\\{aa}(\|k,\39\|l);{}$\2\2\6
\&{if} ${}(\|s\I\T{0}){}$\1\6
\&{for} ${}(\|k\K\T{0};{}$ ${}\|k<\|n;{}$ ${}\|k\PP){}$\1\5
${}\\{oo},\39\\{aa}(\|k,\39\|l)\MRL{-{\K}}\|s{}$;\C{ \PB{\\{oo}} counts two
mems }\2\2\6
\4${}\}{}$\2\6
\&{if} (\\{verbose})\1\5
${}\\{printf}(\.{"\ The\ heuristic\ has\ }\)\.{cost\ \%ld\ mems.\\n"},\39%
\\{mems});{}$\2\6
\4${}\}{}$\2\par
\U24.\fi

\M{13}\B\X4:Local variables\X${}\mathrel+\E{}$\6
\&{register} \&{long} \|k;\C{ the current row of interest }\6
\&{register} \&{long} \|l;\C{ the current column of interest }\6
\&{register} \&{long} \|j;\C{ another interesting column }\6
\&{register} \&{long} \|s;\C{ the current matrix element of interest }\par
\fi

\N{1}{14}Algorithmic details.
The algorithm sketched above is quite simple, except that we did not
discuss how to determine the chosen columns~$c^{(q)}$ that
are reachable by paths of the stated form $(*)$. It is easy to find
all such columns by constructing an unordered forest whose nodes are rows,
beginning with all unmatched rows~$r^{(0)}$ and adding a row~$r$
for which $c\ddash r$ when $c$ is adjacent to a row already in the forest.

Our data structure, which is based on suggestions of Papadimitriou and
Steiglitz [{\sl Combinatorial Optimization\/} (Prentice-Hall, 1982),
$\mathchar"278$11.1], will use several arrays. If row~$r$ is matched
with column~$c$, we will have \PB{$\\{col\_mate}[\|r]\K\|c$} and \PB{$\\{row%
\_mate}[\|c]\K\|r$};
if row~$r$ is unmatched, \PB{\\{col\_mate}[\|r]} will be \PB{${-}\T{1}$}, and
if column~$c$ is unmatched, \PB{\\{row\_mate}[\|c]} will be \PB{${-}\T{1}$}.
If column~$c$ has a mate and is also reachable in a path of the form $(*)$,
we will have $\PB{\\{parent\_row}}[c]=r'$ for some $r'$ in the forest.
Otherwise
column~$c$ is not chosen, and we will have \PB{$\\{parent\_row}[\|c]\K{-}%
\T{1}$}. The rows
in the current forest will be called \PB{\\{unchosen\_row}[\T{0}]} through
\PB{$\\{unchosen\_row}[\|t-\T{1}]$}, where \PB{\|t} is the current total number
of nodes.

The amount $\sigma_k$ subtracted from row $k$ is called \PB{\\{row\_dec}[\|k]};
the
amount $\tau_{\,l}$ added to column~$l$ is called \PB{\\{col\_inc}[\|l]}. To
compute the minimum uncovered element efficiently, we maintain a
quantity called \PB{\\{slack}[\|l]}, which represents the minimum uncovered
element
in each column. More precisely, if column~$l$ is not chosen,
\PB{\\{slack}[\|l]} is the minimum of $a_{kl}
-\sigma_k+\tau_{\,l}$ for $k\in\{\PB{\\{unchosen\_row}}[0],\ldots,\allowbreak
\PB{\\{unchosen\_row}}[q-1]\}$, where $q\le t$ is the number of rows in the
forest that we have explored so far. We also remember \PB{\\{slack\_row}[\|l]},
the number of a row where the stated minimum occurs.

Column $l$ is chosen if and only if \PB{$\\{parent\_row}[\|l]\G\T{0}$}. We will
arrange
things so that we also have \PB{$\\{slack}[\|l]\K\T{0}$} in every chosen
column.

\Y\B\4\X4:Local variables\X${}\mathrel+\E{}$\6
\&{long} ${}{*}\\{col\_mate}{}$;\C{ the column matching a given row, or $-1$ }\6
\&{long} ${}{*}\\{row\_mate}{}$;\C{ the row matching a given column, or $-1$ }\6
\&{long} ${}{*}\\{parent\_row}{}$;\C{ ancestor of a given column's mate, or
$-1$ }\6
\&{long} ${}{*}\\{unchosen\_row}{}$;\C{ node in the forest }\6
\&{long} \|t;\C{ total number of nodes in the forest }\6
\&{long} \|q;\C{ total number of explored nodes in the forest }\6
\&{long} ${}{*}\\{row\_dec}{}$;\C{ $\sigma_k$, the amount subtracted from a
given row }\6
\&{long} ${}{*}\\{col\_inc}{}$;\C{ $\tau_{\,l}$, the amount added to a given
column }\6
\&{long} ${}{*}\\{slack}{}$;\C{ minimum uncovered entry seen in a given column
}\6
\&{long} ${}{*}\\{slack\_row}{}$;\C{ where the \PB{\\{slack}} in a given column
can be found }\6
\&{long} \\{unmatched};\C{ this many rows have yet to be matched }\par
\fi

\M{15}\B\X15:Allocate the intermediate data structures\X${}\E{}$\6
$\\{col\_mate}\K\\{gb\_typed\_alloc}(\|m,\39\&{long},\39\\{working%
\_storage});{}$\6
${}\\{row\_mate}\K\\{gb\_typed\_alloc}(\|n,\39\&{long},\39\\{working%
\_storage});{}$\6
${}\\{parent\_row}\K\\{gb\_typed\_alloc}(\|n,\39\&{long},\39\\{working%
\_storage});{}$\6
${}\\{unchosen\_row}\K\\{gb\_typed\_alloc}(\|m,\39\&{long},\39\\{working%
\_storage});{}$\6
${}\\{row\_dec}\K\\{gb\_typed\_alloc}(\|m,\39\&{long},\39\\{working%
\_storage});{}$\6
${}\\{col\_inc}\K\\{gb\_typed\_alloc}(\|n,\39\&{long},\39\\{working%
\_storage});{}$\6
${}\\{slack}\K\\{gb\_typed\_alloc}(\|n,\39\&{long},\39\\{working\_storage});{}$%
\6
${}\\{slack\_row}\K\\{gb\_typed\_alloc}(\|n,\39\&{long},\39\\{working%
\_storage});{}$\6
\&{if} (\\{gb\_trouble\_code})\5
${}\{{}$\1\6
${}\\{fprintf}(\\{stderr},\39\.{"Sorry,\ out\ of\ memor}\)\.{y!\\n"});{}$\6
\&{return} ${}{-}\T{3};{}$\6
\4${}\}{}$\2\par
\U24.\fi

\M{16}The algorithm operates in stages, where each stage terminates
when we are able to increase the number of matched elements.

The first stage is different from the others; it simply goes through
the matrix and looks for zeroes, matching as many rows and columns
as it can. This stage also initializes table entries that will be
useful in later stages.

\Y\B\4\D$\.{INF}$ \5
\T{\^7fffffff}\C{ infinity (or darn near) }\par
\Y\B\4\X16:Do the initial stage\X${}\E{}$\6
$\|t\K\T{0}{}$;\C{ the forest starts out empty }\6
\&{for} ${}(\|l\K\T{0};{}$ ${}\|l<\|n;{}$ ${}\|l\PP){}$\5
${}\{{}$\1\6
${}\|o,\39\\{row\_mate}[\|l]\K{-}\T{1};{}$\6
${}\|o,\39\\{parent\_row}[\|l]\K{-}\T{1};{}$\6
${}\|o,\39\\{col\_inc}[\|l]\K\T{0};{}$\6
${}\|o,\39\\{slack}[\|l]\K\.{INF};{}$\6
\4${}\}{}$\2\6
\&{for} ${}(\|k\K\T{0};{}$ ${}\|k<\|m;{}$ ${}\|k\PP){}$\5
${}\{{}$\1\6
${}\|o,\39\|s\K\\{aa}(\|k,\39\T{0}){}$;\C{ get ready to calculate the minimum
entry of row $k$ }\6
\&{for} ${}(\|l\K\T{1};{}$ ${}\|l<\|n;{}$ ${}\|l\PP){}$\1\6
\&{if} ${}(\|o,\39\\{aa}(\|k,\39\|l)<\|s){}$\1\5
${}\|s\K\\{aa}(\|k,\39\|l);{}$\2\2\6
${}\|o,\39\\{row\_dec}[\|k]\K\|s;{}$\6
\&{for} ${}(\|l\K\T{0};{}$ ${}\|l<\|n;{}$ ${}\|l\PP){}$\1\6
\&{if} ${}((\|o,\39\|s\E\\{aa}(\|k,\39\|l))\W(\|o,\39\\{row\_mate}[\|l]<%
\T{0})){}$\5
${}\{{}$\1\6
${}\|o,\39\\{col\_mate}[\|k]\K\|l;{}$\6
${}\|o,\39\\{row\_mate}[\|l]\K\|k;{}$\6
\&{if} ${}(\\{verbose}>\T{1}){}$\1\5
${}\\{printf}(\.{"\ matching\ col\ \%ld==}\)\.{row\ \%ld\\n"},\39\|l,\39%
\|k);{}$\2\6
\&{goto} \\{row\_done};\6
\4${}\}{}$\2\2\6
${}\|o,\39\\{col\_mate}[\|k]\K{-}\T{1};{}$\6
\&{if} ${}(\\{verbose}>\T{1}){}$\1\5
${}\\{printf}(\.{"\ \ node\ \%ld:\ unmatch}\)\.{ed\ row\ \%ld\\n"},\39\|t,\39%
\|k);{}$\2\6
${}\|o,\39\\{unchosen\_row}[\|t\PP]\K\|k;{}$\6
\4\\{row\_done}:\5
;\6
\4${}\}{}$\2\par
\U18.\fi

\M{17}If a subsequent stage has not succeeded in matching every row,
we prepare for a new stage by reinitializing the forest as follows.

\Y\B\4\X17:Get ready for another stage\X${}\E{}$\6
$\|t\K\T{0};{}$\6
\&{for} ${}(\|l\K\T{0};{}$ ${}\|l<\|n;{}$ ${}\|l\PP){}$\5
${}\{{}$\1\6
${}\|o,\39\\{parent\_row}[\|l]\K{-}\T{1};{}$\6
${}\|o,\39\\{slack}[\|l]\K\.{INF};{}$\6
\4${}\}{}$\2\6
\&{for} ${}(\|k\K\T{0};{}$ ${}\|k<\|m;{}$ ${}\|k\PP){}$\1\6
\&{if} ${}(\|o,\39\\{col\_mate}[\|k]<\T{0}){}$\5
${}\{{}$\1\6
\&{if} ${}(\\{verbose}>\T{1}){}$\1\5
${}\\{printf}(\.{"\ \ node\ \%ld:\ unmatch}\)\.{ed\ row\ \%ld\\n"},\39\|t,\39%
\|k);{}$\2\6
${}\|o,\39\\{unchosen\_row}[\|t\PP]\K\|k;{}$\6
\4${}\}{}$\2\2\par
\U18.\fi

\M{18}Here, then, is the algorithm's overall control structure.
There are at most $m$ stages, and each stage does $O(mn)$ operations,
so the total running time is $O(m^2n)$.

\Y\B\4\X18:Do the Hungarian algorithm\X${}\E{}$\6
\X16:Do the initial stage\X;\6
\&{if} ${}(\|t\E\T{0}){}$\1\5
\&{goto} \\{done};\2\6
${}\\{unmatched}\K\|t;{}$\6
\&{while} (\T{1})\5
${}\{{}$\1\6
\&{if} (\\{verbose})\1\5
${}\\{printf}(\.{"\ After\ \%ld\ mems\ I'v}\)\.{e\ matched\ \%ld\ rows.\\}\)%
\.{n"},\39\\{mems},\39\|m-\|t);{}$\2\6
${}\|q\K\T{0};{}$\6
\&{while} (\T{1})\5
${}\{{}$\1\6
\&{while} ${}(\|q<\|t){}$\5
${}\{{}$\1\6
\X19:Explore node \PB{\|q} of the forest; if the matching can be increased, %
\PB{\&{goto} \\{breakthru}}\X;\6
${}\|q\PP;{}$\6
\4${}\}{}$\2\6
\X21:Introduce a new zero into the matrix by modifying \PB{\\{row\_dec}} and %
\PB{\\{col\_inc}}; if the matching can be increased, \PB{\&{goto} %
\\{breakthru}}\X;\6
\4${}\}{}$\2\6
\4\\{breakthru}:\5
\X20:Update the matching by pairing row $k$ with column $l$\X;\6
\&{if} ${}(\MM\\{unmatched}\E\T{0}){}$\1\5
\&{goto} \\{done};\2\6
\X17:Get ready for another stage\X;\6
\4${}\}{}$\2\6
\4\\{done}:\5
\X23:Doublecheck the solution\X;\par
\U24.\fi

\M{19}\B\X19:Explore node \PB{\|q} of the forest; if the matching can be
increased, \PB{\&{goto} \\{breakthru}}\X${}\E{}$\6
${}\{{}$\1\6
${}\|o,\39\|k\K\\{unchosen\_row}[\|q];{}$\6
${}\|o,\39\|s\K\\{row\_dec}[\|k];{}$\6
\&{for} ${}(\|l\K\T{0};{}$ ${}\|l<\|n;{}$ ${}\|l\PP){}$\1\6
\&{if} ${}(\|o,\39\\{slack}[\|l]){}$\5
${}\{{}$\5
\1\&{register} \&{long} \\{del};\7
${}\\{oo},\39\\{del}\K\\{aa}(\|k,\39\|l)-\|s+\\{col\_inc}[\|l];{}$\6
\&{if} ${}(\\{del}<\\{slack}[\|l]){}$\5
${}\{{}$\1\6
\&{if} ${}(\\{del}\E\T{0}){}$\5
${}\{{}$\C{ we found a new zero }\1\6
\&{if} ${}(\|o,\39\\{row\_mate}[\|l]<\T{0}){}$\1\5
\&{goto} \\{breakthru};\2\6
${}\|o,\39\\{slack}[\|l]\K\T{0}{}$;\C{ this column will now be chosen }\6
${}\|o,\39\\{parent\_row}[\|l]\K\|k;{}$\6
\&{if} ${}(\\{verbose}>\T{1}){}$\1\5
${}\\{printf}(\.{"\ \ node\ \%ld:\ row\ \%ld}\)\.{==col\ \%ld--row\ \%ld\\n}\)%
\.{"},\39\|t,\39\\{row\_mate}[\|l],\39\|l,\39\|k);{}$\2\6
${}\\{oo},\39\\{unchosen\_row}[\|t\PP]\K\\{row\_mate}[\|l];{}$\6
\4${}\}{}$\5
\2\&{else}\5
${}\{{}$\1\6
${}\|o,\39\\{slack}[\|l]\K\\{del};{}$\6
${}\|o,\39\\{slack\_row}[\|l]\K\|k;{}$\6
\4${}\}{}$\2\6
\4${}\}{}$\2\6
\4${}\}{}$\2\2\6
\4${}\}{}$\2\par
\U18.\fi

\M{20}At this point, column $l$ is unmatched, and row $k$ is in
the forest. By following parent links in the forest,
we can rematch rows and columns so that a previously unmatched row~$r^{(0)}$
gets a mate.

\Y\B\4\X20:Update the matching by pairing row $k$ with column $l$\X${}\E{}$\6
\&{if} (\\{verbose})\1\5
${}\\{printf}(\.{"\ Breakthrough\ at\ no}\)\.{de\ \%ld\ of\ \%ld!\\n"},\39\|q,%
\39\|t);{}$\2\6
\&{while} (\T{1})\5
${}\{{}$\1\6
${}\|o,\39\|j\K\\{col\_mate}[\|k];{}$\6
${}\|o,\39\\{col\_mate}[\|k]\K\|l;{}$\6
${}\|o,\39\\{row\_mate}[\|l]\K\|k;{}$\6
\&{if} ${}(\\{verbose}>\T{1}){}$\1\5
${}\\{printf}(\.{"\ rematching\ col\ \%ld}\)\.{==row\ \%ld\\n"},\39\|l,\39%
\|k);{}$\2\6
\&{if} ${}(\|j<\T{0}){}$\1\5
\&{break};\2\6
${}\|o,\39\|k\K\\{parent\_row}[\|j];{}$\6
${}\|l\K\|j;{}$\6
\4${}\}{}$\2\par
\U18.\fi

\M{21}If we get to this point, we have explored the entire forest; none of
the unchosen rows has led to a breakthrough. An unchosen column with
smallest \PB{\\{slack}} will allow us to make further progress.

\Y\B\4\X21:Introduce a new zero into the matrix by modifying \PB{\\{row\_dec}}
and \PB{\\{col\_inc}}; if the matching can be increased, \PB{\&{goto} %
\\{breakthru}}\X${}\E{}$\6
$\|s\K\.{INF};{}$\6
\&{for} ${}(\|l\K\T{0};{}$ ${}\|l<\|n;{}$ ${}\|l\PP){}$\1\6
\&{if} ${}(\|o,\39\\{slack}[\|l]\W\\{slack}[\|l]<\|s){}$\1\5
${}\|s\K\\{slack}[\|l];{}$\2\2\6
\&{for} ${}(\|q\K\T{0};{}$ ${}\|q<\|t;{}$ ${}\|q\PP){}$\1\5
${}\\{ooo},\39\\{row\_dec}[\\{unchosen\_row}[\|q]]\MRL{+{\K}}\|s;{}$\2\6
\&{for} ${}(\|l\K\T{0};{}$ ${}\|l<\|n;{}$ ${}\|l\PP){}$\1\6
\&{if} ${}(\|o,\39\\{slack}[\|l]){}$\5
${}\{{}$\C{ column $l$ is not chosen }\1\6
${}\|o,\39\\{slack}[\|l]\MRL{-{\K}}\|s;{}$\6
\&{if} ${}(\\{slack}[\|l]\E\T{0}){}$\1\5
\X22:Look at a new zero, and \PB{\&{goto} \\{breakthru}} with \PB{\\{col\_inc}}
up to date if there's a breakthrough\X;\2\6
\4${}\}{}$\5
\2\&{else}\1\5
${}\\{oo},\39\\{col\_inc}[\|l]\MRL{+{\K}}\|s{}$;\2\2\par
\U18.\fi

\M{22}There might be several columns tied for smallest slack. If any of them
leads to a breakthrough, we are very happy; but we must finish the loop on~\PB{%
\|l}
before going to \PB{\\{breakthru}}, because the \PB{\\{col\_inc}} variables
need to be maintained for the next stage.

Within column \PB{\|l}, there might be several rows that produce the same
slack;
we have remembered only one of them, \PB{\\{slack\_row}[\|l]}. Fortunately, one
is
sufficient for our purposes. Either we have a breakthrough or we choose
column~\PB{\|l}, regardless of which row or rows led us to consider that
column.

\Y\B\4\X22:Look at a new zero, and \PB{\&{goto} \\{breakthru}} with \PB{\\{col%
\_inc}} up to date if there's a breakthrough\X${}\E{}$\6
${}\{{}$\1\6
${}\|o,\39\|k\K\\{slack\_row}[\|l];{}$\6
\&{if} ${}(\\{verbose}>\T{1}){}$\1\5
${}\\{printf}(\.{"\ Decreasing\ uncover}\)\.{ed\ elements\ by\ \%ld\ p}\)%
\.{roduces\ zero\ at\ [\%ld}\)\.{,\%ld]\\n"},\39\|s,\39\|k,\39\|l);{}$\2\6
\&{if} ${}(\|o,\39\\{row\_mate}[\|l]<\T{0}){}$\5
${}\{{}$\1\6
\&{for} ${}(\|j\K\|l+\T{1};{}$ ${}\|j<\|n;{}$ ${}\|j\PP){}$\1\6
\&{if} ${}(\|o,\39\\{slack}[\|j]\E\T{0}){}$\1\5
${}\\{oo},\39\\{col\_inc}[\|j]\MRL{+{\K}}\|s;{}$\2\2\6
\&{goto} \\{breakthru};\6
\4${}\}{}$\5
\2\&{else}\5
${}\{{}$\C{ not a breakthrough, but the forest continues to grow }\1\6
${}\|o,\39\\{parent\_row}[\|l]\K\|k;{}$\6
\&{if} ${}(\\{verbose}>\T{1}){}$\1\5
${}\\{printf}(\.{"\ \ node\ \%ld:\ row\ \%ld}\)\.{==col\ \%ld--row\ \%ld\\n}\)%
\.{"},\39\|t,\39\\{row\_mate}[\|l],\39\|l,\39\|k);{}$\2\6
${}\\{oo},\39\\{unchosen\_row}[\|t\PP]\K\\{row\_mate}[\|l];{}$\6
\4${}\}{}$\2\6
\4${}\}{}$\2\par
\U21.\fi

\M{23}The code in the present section is redundant, unless cosmic
radiation has caused the hardware to malfunction. But there is some
reassurance whenever we find that mathematics still appears to be
consistent, so the author could not resist writing these few unnecessary lines,
which verify that the assignment problem has indeed been solved optimally.
(We don't count the mems.)

\Y\B\4\X23:Doublecheck the solution\X${}\E{}$\6
\&{for} ${}(\|k\K\T{0};{}$ ${}\|k<\|m;{}$ ${}\|k\PP){}$\1\6
\&{for} ${}(\|l\K\T{0};{}$ ${}\|l<\|n;{}$ ${}\|l\PP){}$\1\6
\&{if} ${}(\\{aa}(\|k,\39\|l)<\\{row\_dec}[\|k]-\\{col\_inc}[\|l]){}$\5
${}\{{}$\1\6
${}\\{fprintf}(\\{stderr},\39\.{"Oops,\ I\ made\ a\ mist}\)\.{ake!\\n"});{}$\6
\&{return} ${}{-}\T{6}{}$;\C{ can't happen }\6
\4${}\}{}$\2\2\2\6
\&{for} ${}(\|k\K\T{0};{}$ ${}\|k<\|m;{}$ ${}\|k\PP){}$\5
${}\{{}$\1\6
${}\|l\K\\{col\_mate}[\|k];{}$\6
\&{if} ${}(\|l<\T{0}\V\\{aa}(\|k,\39\|l)\I\\{row\_dec}[\|k]-\\{col\_inc}[%
\|l]){}$\5
${}\{{}$\1\6
${}\\{fprintf}(\\{stderr},\39\.{"Oops,\ I\ blew\ it!\\n"});{}$\6
\&{return} ${}{-}\T{66}{}$;\C{ can't happen }\6
\4${}\}{}$\2\6
\4${}\}{}$\2\6
${}\|k\K\T{0};{}$\6
\&{for} ${}(\|l\K\T{0};{}$ ${}\|l<\|n;{}$ ${}\|l\PP){}$\1\6
\&{if} (\\{col\_inc}[\|l])\1\5
${}\|k\PP;{}$\2\2\6
\&{if} ${}(\|k>\|m){}$\5
${}\{{}$\1\6
${}\\{fprintf}(\\{stderr},\39\.{"Oops,\ I\ adjusted\ to}\)\.{o\ many\ columns!%
\\n"});{}$\6
\&{return} ${}{-}\T{666}{}$;\C{ can't happen }\6
\4${}\}{}$\2\par
\U18.\fi

\N{1}{24}Interfacing.
A few nitty-gritty details still need to be handled: Our algorithm
is not symmetric between rows and columns, and it works only for $m\le n$;
so we will transpose the matrix when
$m>n$. Furthermore, our algorithm minimizes, but we actually want
it to maximize (except when \PB{$\Xcompl$} is nonzero).

Hence, we want to make the following transformations to the data before
processing it with the algorithm developed above.

\Y\B\4\X24:Solve the assignment problem\X${}\E{}$\6
\&{if} ${}(\|m>\|n){}$\1\5
\X25:Transpose the matrix\X\2\6
\&{else}\1\5
${}\\{transposed}\K\T{0};{}$\2\6
\X15:Allocate the intermediate data structures\X;\6
\&{if} ( $\MRL{\Xcompl{\E}}$ \T{0} ) \6
\&{for} ${}(\|k\K\T{0};{}$ ${}\|k<\|m;{}$ ${}\|k\PP){}$\1\6
\&{for} ${}(\|l\K\T{0};{}$ ${}\|l<\|n;{}$ ${}\|l\PP){}$\1\5
${}\\{aa}(\|k,\39\|l)\K\|d-\\{aa}(\|k,\39\|l);{}$\2\2\6
\&{if} (\\{heur})\1\5
\X12:Subtract column minima in order to start with lots of zeroes\X;\2\6
\X18:Do the Hungarian algorithm\X;\par
\U2.\fi

\M{25}\B\X25:Transpose the matrix\X${}\E{}$\6
${}\{{}$\1\6
\&{if} ${}(\\{verbose}>\T{1}){}$\1\5
\\{printf}(\.{"Temporarily\ transpo}\)\.{sing\ rows\ and\ column}\)\.{s...%
\\n"});\2\6
${}\\{tmtx}\K\\{gb\_typed\_alloc}(\|m*\|n,\39\&{long},\39\\{working%
\_storage});{}$\6
\&{if} ${}(\\{tmtx}\E\NULL){}$\5
${}\{{}$\1\6
${}\\{fprintf}(\\{stderr},\39\.{"Sorry,\ out\ of\ memor}\)\.{y!\\n"}){}$;\5
\&{return} ${}{-}\T{4};{}$\6
\4${}\}{}$\2\6
\&{for} ${}(\|k\K\T{0};{}$ ${}\|k<\|m;{}$ ${}\|k\PP){}$\1\6
\&{for} ${}(\|l\K\T{0};{}$ ${}\|l<\|n;{}$ ${}\|l\PP){}$\1\5
${}{*}(\\{tmtx}+\|l*\|m+\|k)\K{*}(\\{mtx}+\|k*\|n+\|l);{}$\2\2\6
${}\|m\K\|n{}$;\5
${}\|n\K\|k{}$;\C{ \PB{\|k} holds the former value of \PB{\|m} }\6
${}\\{mtx}\K\\{tmtx};{}$\6
${}\\{transposed}\K\T{1};{}$\6
\4${}\}{}$\2\par
\U24.\fi

\M{26}\B\X4:Local variables\X${}\mathrel+\E{}$\6
\&{long} ${}{*}\\{tmtx}{}$;\C{ the transpose of \PB{\\{mtx}} }\6
\&{long} \\{transposed};\C{ has the data been transposed? }\par
\fi

\M{27}\B\X27:Display the solution\X${}\E{}$\6
${}\{{}$\1\6
\\{printf}(\.{"The\ following\ entri}\)\.{es\ produce\ an\ optimu}\)\.{m\
assignment:\\n"});\6
\&{for} ${}(\|k\K\T{0};{}$ ${}\|k<\|m;{}$ ${}\|k\PP){}$\1\5
${}\\{printf}(\.{"\ [\%ld,\%ld]\\n"},\3{-1}\39\\{transposed}\?\\{col\_mate}[%
\|k]:\|k,\3{-1}\39\\{transposed}\?\|k:\\{col\_mate}[\|k]);{}$\2\6
\4${}\}{}$\2\par
\U2.\fi

\N{1}{28}Encapsulated PostScript.
A special output file called \.{lisa.eps} is written if the user has
selected the \.{-P} option. This file contains a sequence of
PostScript commands that can be used to generate an illustration
within many kinds of documents. For example, if \TEX/ is being used
with the \.{dvips} output driver from Radical Eye Software and with the
associated \.{epsf.tex} macros, one can say
$$\.{\\epsfxsize=10cm \\epsfbox\{lisa.eps\}}$$
within a \TEX/ document and the illustration will be typeset in
a box that is 10 centimeters wide.

The conventions of PostScript allow the illustration to be scaled to
any size. Best results are probably obtained if each pixel is at
least one millimeter wide (about 1/25 inch) when printed.

The illustration is formed by first
``painting'' the input data as a rectangle of pixels,
with up to 256 shades of gray. Then the solution pixels are
framed in black, with a white trim just inside the black edges
to help make the frame visible in already-dark places. The frames are
created by painting over the original image; the
center of each solution pixel retains its original color.

Encapsulated PostScript files have a simple format that is recognized
by many software packages and printing devices. We use a subset of
PostScript that should be easy to convert to other languages if necessary.

\Y\B\4\X28:Output the input matrix in PostScript format\X${}\E{}$\6
${}\{{}$\1\6
${}\\{eps\_file}\K\\{fopen}(\.{"lisa.eps"},\39\.{"w"});{}$\6
\&{if} ${}(\R\\{eps\_file}){}$\5
${}\{{}$\1\6
${}\\{fprintf}(\\{stderr},\39\.{"Sorry,\ I\ can't\ open}\)\.{\ the\ file\
`lisa.eps'}\)\.{!\\n"});{}$\6
${}\\{PostScript}\K\T{0};{}$\6
\4${}\}{}$\5
\2\&{else}\5
${}\{{}$\1\6
${}\\{fprintf}(\\{eps\_file},\39\.{"\%\%!PS-Adobe-3.0\ EPS}\)\.{F-3.0\\n"}){}$;%
\C{ \.{1.0} and \.{2.0} also OK }\6
${}\\{fprintf}(\\{eps\_file},\39\.{"\%\%\%\%BoundingBox:\ -1}\)\.{\ -1\ \%ld\ %
\%ld\\n"},\39\|n+\T{1},\39\|m+\T{1});{}$\6
${}\\{fprintf}(\\{eps\_file},\39\.{"/buffer\ \%ld\ string\ }\)\.{def\\n"},\39%
\|n);{}$\6
${}\\{fprintf}(\\{eps\_file},\39\.{"\%ld\ \%ld\ 8\ [\%ld\ 0\ 0\ }\)\.{-\%ld\ 0\
\%ld]\\n"},\39\|n,\39\|m,\39\|n,\39\|m,\39\|m);{}$\6
${}\\{fprintf}(\\{eps\_file},\39\.{"\{currentfile\ buffer}\)\.{\ readhexstring\
pop\}\ }\)\.{bind\\n"});{}$\6
${}\\{fprintf}(\\{eps\_file},\39\.{"gsave\ \%ld\ \%ld\ scale}\)\.{\ image\\n"},%
\39\|n,\39\|m);{}$\6
\&{for} ${}(\|k\K\T{0};{}$ ${}\|k<\|m;{}$ ${}\|k\PP){}$\1\5
\X30:Output row \PB{\|k} as a hexadecimal string\X;\2\6
${}\\{fprintf}(\\{eps\_file},\39\.{"grestore\\n"});{}$\6
\4${}\}{}$\2\6
\4${}\}{}$\2\par
\U2.\fi

\M{29}\B\X3:Global variables\X${}\mathrel+\E{}$\6
\&{FILE} ${}{*}\\{eps\_file}{}$;\C{ file for encapsulated PostScript output }%
\par
\fi

\M{30}This program need not produce machine-independent output, so we can
safely use floating-point arithmetic here. At most 64 characters
(32 pixel-bytes) are output on each line.

\Y\B\4\X30:Output row \PB{\|k} as a hexadecimal string\X${}\E{}$\6
$\{{}$\5
\&{register} \&{float} \\{conv}${}\K\T{255.0}/{}$(\&{float}) \|d;\6
\&{register} \&{long} \|x; \&{for} ${}(\|l\K\T{0};{}$ ${}\|l<\|n;{}$ ${}\|l%
\PP)$ $\{$ \|x $\K$ (\&{long})( \\{conv} $*$ (\&{float})( $\MRL{\Xcompl{\?\|d-%
\\{aa}(\|k,\39\|l):}}$ $\\{aa}(\|k,\39\|l)$ ) )  ;\6
${}\\{fprintf}(\\{eps\_file},\39\.{"\%02lx"},\39\|x>\T{255}\?\T{255\$L}:%
\|x);{}$\6
\&{if} ${}((\|l\AND\T{\^1f})\E\T{\^1f}){}$\1\5
${}\\{fprintf}(\\{eps\_file},\39\.{"\\n"});{}$\2\6
$\}$ \6
\&{if} ${}(\|n\AND\T{\^1f}){}$\1\5
${}\\{fprintf}(\\{eps\_file},\39\.{"\\n"});{}$\2\6
$\}{}$\par
\U28.\fi

\M{31}\B\X31:Output the solution in PostScript format\X${}\E{}$\6
${}\{{}$\1\6
${}\\{fprintf}(\\{eps\_file},\39\.{"/bx\ \{moveto\ 0\ 1\ rli}\)\.{neto\ 1\ 0\
rlineto\ 0\ -}\)\.{1\ rlineto\ closepath\\}\)\.{n"});{}$\6
${}\\{fprintf}(\\{eps\_file},\39\.{"\ gsave\ .3\ setlinewi}\)\.{dth\ 1\ setgray%
\ clip\ s}\)\.{troke"});{}$\6
${}\\{fprintf}(\\{eps\_file},\39\.{"\ grestore\ stroke\}\ b}\)\.{ind\ def%
\\n"});{}$\6
${}\\{fprintf}(\\{eps\_file},\39\.{"\ .1\ setlinewidth\\n"});{}$\6
\&{for} ${}(\|k\K\T{0};{}$ ${}\|k<\|m;{}$ ${}\|k\PP){}$\1\5
${}\\{fprintf}(\\{eps\_file},\39\.{"\ \%ld\ \%ld\ bx\\n"},\3{-1}\39%
\\{transposed}\?\|k:\\{col\_mate}[\|k],\3{-1}\39\\{transposed}\?\|n-\T{1}-%
\\{col\_mate}[\|k]:\|m-\T{1}-\|k);{}$\2\6
\\{fclose}(\\{eps\_file});\6
\4${}\}{}$\2\par
\U2.\fi

\N{1}{32}Index. As usual, we close with a list of identifier definitions and
uses.
\fi

\inx
\fin
\con
