% This file is part of the Stanford GraphBase (c) Stanford University 1992
\def\title{ECON\_\thinspace ORDER}
@i boilerplate.w %<< legal stuff: PLEASE READ IT BEFORE MAKING ANY CHANGES!
\def\<#1>{$\langle${\rm#1}$\rangle$}
\prerequisite{GB\_\thinspace ECON}
@* Near-triangular ordering.
This demonstration program takes a matrix
constructed by the |gb_econ| module and permutes the economic sectors
so that the first sectors of the ordering tend to be producers of
primary materials for other industries, while the last sectors
tend to be final-product
industries that deliver their output mostly to end users.
More precisely, suppose the rows of the matrix represent the outputs
of a sector and the columns represent the inputs. This program attempts
to find a permutation of rows and columns that minimizes the sum of
the elements below the main diagonal. (If this sum were zero, the
matrix would be upper triangular; each supplier of a sector would precede
it in the ordering, while each customer of that sector would follow it.)
The general problem of finding a minimizing permutation is NP-complete;
it includes, as a very special case, the {\sc FEEDBACK ARC SET} problem
discussed in Karp's classic paper [{\sl Complexity of Computer
Computations} (Plenum Press, 1972), 85--103].
Here we use a simple heuristic downhill method
to find a permutation that is locally optimum, in the sense that
the below-diagonal sum does not decrease if any individual
sector is moved to another position while preserving the relative order
of the other sectors. We start with a random permutation and repeatedly
improve it, choosing the improvement that gives the least positive
gain at each step. One of the main motives for the present implementation
was to get further experience with this method of cautious descent, which
was proposed by A. M. Gleason in {\sl AMS Proceedings of Symposia in Applied
Mathematics\/ \bf10} (1958), 175--178. (See the comments below.)
@ As explained in |gb_econ|, the subroutine call |econ(n,2,0,s)|
constructs a graph whose |n<=79| vertices represent sectors of the
U.S. economy, and whose arcs $u\to v$ are assigned numbers corresponding to the
flow of products from sector~|u| to sector~|v|. When |n<79|, the
|n| sectors are obtained from a basic set of 79 sectors by
combining related commodities; if |s=0|, the combination is done in
a way that tends to equalize the row sums, while if |s>0| the combination
is done by choosing a random subtree of a given 79-leaf tree (where the
``randomness'' is fully determined by the value of~|s|).
This program uses two random number seeds, one for |econ| and one
for choosing the random initial permutation. The former is called~|s|
and the latter is called~|t|. A further parameter, |r|, governs the
number of repetitions to be made, trying different starting permutations
on the same matrix. When |r>1|, new solutions are displayed only when
they improve on the previous best.
By default, |n=79|, |r=1|, and |s=t=0|. The user can change these
default parameters by specifying options
on the command line, at least in a \UNIX\ implementation, thereby
obtaining a variety of special effects; the relevant
command-line options are \.{-n}\, \.{-r}\,
\.{-s}\, and/or \.{-t}\. Additional options
\.{-v} (verbose), \.{-V} (extreme verbosity), and \.{-g}
(greedy or steepest descent instead of cautious descent) are also provided.
@^UNIX dependencies@>
Here is the overall layout of this \Cee\ program:
@p
#include "gb_graph.h" /* the GraphBase data structures */
#include "gb_flip.h" /* the random number generator */
#include "gb_econ.h" /* the |econ| routine */
@#
@@;
main(argc,argv)
int argc; /* the number of command-line arguments */
char *argv[]; /* an array of strings containing those arguments */
{@+unsigned n=79; /* the desired number of sectors */
long s=0; /* random |seed| for |econ| */
long t=0; /* random |seed| for initial permutation */
unsigned r=1; /* the number of repetitions */
long greedy=0; /* should we use steepest descent? */
register int j,k; /* all-purpose indices */
@;
g=econ(n,2,0,s);
if (g==NULL) {
fprintf(stderr,"Sorry, can't create the matrix! (error code %d)\n",
panic_code);
return -1;
}
printf("Ordering the sectors of %s, using seed %ld:\n",g->id,t);
printf(" (%s descent method)\n",greedy?"Steepest":"Cautious");
@;
@;
gb_init_rand(t);
while (r--)
@;
}
@ Besides the matrix $M$ of input/output coefficients, we will find it
convenient to use the matrix $\Delta$, where $\Delta_{jk}=M_{jk}-M_{kj}$.
@d INF 0x7fffffff /* infinity (or darn near) */
@f Vertex int /* |gb_graph| defines these data types */
@f Arc int
@f Graph int
@=
Graph *g; /* the graph we will work on */
long mat[79][79]; /* the corresponding matrix */
long del[79][79]; /* skew-symmetric differences */
long best_score=INF; /* the smallest below-diagonal sum we've seen so far */
@ @=
while (--argc) {
@^UNIX dependencies@>
if (sscanf(argv[argc],"-n%u",&n)==1) ;
else if (sscanf(argv[argc],"-r%u",&r)==1) ;
else if (sscanf(argv[argc],"-s%ld",&s)==1) ;
else if (sscanf(argv[argc],"-t%ld",&t)==1) ;
else if (strcmp(argv[argc],"-v")==0) verbose=1;
else if (strcmp(argv[argc],"-V")==0) verbose=2;
else if (strcmp(argv[argc],"-g")==0) greedy=1;
else {
fprintf(stderr,"Usage: %s [-nN][-rN][-sN][-tN][-g][-v][-V]\n",argv[0]);
return -2;
}
}
@ @=
{@+register Vertex *v;
register Arc *a;
n=g->n;
for (v=g->vertices;vvertices+n;v++)
for (a=v->arcs;a;a=a->next)
mat[v-g->vertices][a->tip-g->vertices]=a->flow;
for (j=0;j=
{@+register long s=0;
for (j=1;jvertices+mapping[k]|. The current below-diagonal sum will be
the value of |score|. We will not actually have to permute anything
inside of |mat|.
@d sec_name(k) (g->vertices+mapping[k])->name
@=
int mapping[79]; /* current permutation */
long score; /* current sum of elements above main diagonal */
long steps; /* the number of iterations so far */
@ @=
{
@;
while(1) {
@