% This file is part of the Stanford GraphBase (c) Stanford University 1992
\def\title{ASSIGN\_\thinspace MONA}
@i boilerplate.w %<< legal stuff: PLEASE READ IT BEFORE MAKING ANY CHANGES!
\def\<#1>{$\langle${\rm#1}$\rangle$}
\def\dash{\mathrel-\joinrel\joinrel\mathrel-} % adjacent vertices
\def\ddash{=\joinrel\joinrel=} % matched vertices
\prerequisite{GB\_\thinspace MONA}
@* The assignment problem.
This demonstration program takes a matrix
constructed by the |gb_mona| 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 (i.e., 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 non-random nature of pixels
in a work of art may 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 |gb_mona|, the subroutine call |mona(m,n,d,m0,m1,n0,n1,d0,d1,
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's $16\times32$ ``smile'');
\.{-c} (complement black/white); \.{-p} (print the matrix and solution);
\.{-P} (produce a PostScript file \.{mona.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_mona.h" /* the |mona| routine */
@#
@@;
main(argc,argv)
int argc; /* the number of command-line arguments */
char *argv[]; /* an array of strings containing those arguments */
{@+@;
@;
mtx=mona(m,n,d,m0,m1,n0,n1,d0,d1,working_storage);
if (mtx==NULL) {
fprintf(stderr,"Sorry, can't create the matrix! (error code %d)\n",
panic_code);
return -1;
}
printf("Assignment problem for %s%s\n",mona_id,(compl?", complemented":""));
sscanf(mona_id,"mona(%u,%u,%lu",&m,&n,&d); /* adjust for defaults */
if (m!=n) heur=0;
if (printing) @;
if (PostScript) @