% This file is part of the Stanford GraphBase (c) Stanford University 1993
@i boilerplate.w %<< legal stuff: PLEASE READ IT BEFORE MAKING ANY CHANGES!
@i gb_types.w
% 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
@s compl normal @q unreserve a C++ keyword @>
\prerequisite{GB\_\,LISA}
@* 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.
@ As explained in {\sc GB\_\,LISA}, the subroutine call
|lisa(m,n,d,m0,m1,n0,n1,d0,d1,@[@t\\{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 |m0|,
|m1|, |n0|, and |n1| define that region. The raw data is obtained as a
sum of |(m1-m0)(n1-n0)| pixel values between $0$ and~$255$, then
scaled in such a way that sums |<=d0| are mapped to zero, sums |>=d1|
are mapped to~$d$, and intermediate sums are mapped linearly to
intermediate values. Default values |m1=360|, |n1=250|, |m=m1-m0|,
|n=n1-n0|, |d=255|, and |d1=255(m1-m0)(n1-n0)| are substituted if any
of the parameters |m|, |n|, |d|, |m1|, |n1|, or |d1| are zero.
The user can specify the nine parameters |(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=}\, \.{m0=}\, 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).
@^UNIX dependencies@>
Here is the overall layout of this \CEE/ program:
@p
#include "gb_graph.h" /* the GraphBase data structures */
#include "gb_lisa.h" /* the |lisa| routine */
@h@#
@@;
main(argc,argv)
int argc; /* the number of command-line arguments */
char *argv[]; /* an array of strings containing those arguments */
{@+@@;@#
@;
mtx=lisa(m,n,d,m0,m1,n0,n1,d0,d1,working_storage);
if (mtx==NULL) {
fprintf(stderr,"Sorry, can't create the matrix! (error code %ld)\n",
panic_code);
return -1;
}
printf("Assignment problem for %s%s\n",lisa_id,(compl?", complemented":""));
sscanf(lisa_id,"lisa(%lu,%lu,%lu",&m,&n,&d); /* adjust for defaults */
if (m!=n) heur=0;
if (printing) @;
if (PostScript) @