gb_econ.w

模拟器提供了一个简单易用的平台

% 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

\def\title{GB\_\,ECON}

\prerequisites{GB\_\,GRAPH}{GB\_\,IO}
@* Introduction. This GraphBase module contains the |econ| subroutine,
which creates a family of directed graphs related to the flow of money
between industries.  An example of the use of this procedure can be
found in the demo program {\sc ECON\_\,ORDER}.

@(gb_econ.h@>=
extern Graph *econ();

@ The subroutine call |econ(n,omit,threshold,seed)|
constructs a directed graph based on the information in \.{econ.dat}.
Each vertex of the graph corresponds to one of 81 sectors of the U.S.
economy. The data values come from the year 1985; they were derived from
tables published in {\sl Survey of Current Business\/ \bf70} (1990), 41--56.

If |omit=threshold=0|, the directed graph is a ``circulation'';
that is, each arc has an associated |flow| value, and
the sum of arc flows leaving each vertex is equal to the
sum of arc flows entering. This sum is called the ``total commodity output''
for the sector in question. The flow in an arc from sector $j$~to
sector~$k$ is the amount of the commodity made by sector~$j$ that was
used by sector~$k$, rounded to millions of dollars at producers' prices.
For example, the total commodity output of the sector called \.{Apparel}
is 54031, meaning that the total cost of making all kinds of apparel in
1985 was about 54 billion dollars. There is an arc from \.{Apparel} to
itself with a flow of 9259, meaning that 9.259 billion dollars' worth
of apparel went from one group within the apparel industry to another.
There also is an arc of flow~44 from \.{Apparel} to \.{Household}
\.{furniture}, indicating that some 44 million dollars' worth of apparel
went into the making of household furniture. By looking at all
arcs that leave the \.{Apparel} vertex, you can see where all that
new apparel went; by looking at all arcs that enter \.{Apparel}, you can
see what ingredients the apparel industry needed to make~it.

One vertex, called \.{Users}, represents people like you and me, the
non-industrial end users of everything. The arc from \.{Apparel} to
\.{Users} has flow 42172; this is the ``total final demand'' for
apparel, the amount that didn't flow into other sectors of the economy
before it reached people like us. The arc from \.{Users} to \.{Apparel}
has flow 19409, which is called the ``value added'' by users; it
represents wages and salaries paid to support the manufacturing
process. The sum of total final demand over all sectors, which also
equals the sum of value added over all sectors, is conventionally
called the Gross National Product (GNP). In 1985 the GNP was 3999362,
nearly 4 trillion dollars, according to \.{econ.dat}. (The sum of all
arc flows coming out of all vertices was 7198680; this sum
overestimates the total economic activity, because it counts some
items more than once---statistics are recorded whenever an item
passes a statistics gatherer. Economists try to adjust the data so that
they avoid double-counting as much as possible.)

Speaking of economists, there is another special vertex called
\.{Adjustments}, included by economists so that GNP is measured
more accurately. This vertex takes account of such things as changes in
the value of inventories, and imported materials that cannot be obtained
within the U.S., as well as work done for the government and for foreign
concerns. In 1985, these adjustments accounted for about 11\% of the GNP.

Incidentally, some of the ``total final demand'' arcs are negative.
For example, the arc from \.{Petroleum} \.{and} \.{natural} \.{gas}
\.{production} to \.{Users} has flow $-27032$. This might seem strange
at first, but it makes sense when imports are considered, because
crude oil and natural gas go more to other industries than to end users.
Total final demand does not mean total user demand.

@d flow a.I /* utility field |a| specifies the flow in an arc */

@ If |omit=1|, the \.{Users} vertex is omitted from the digraph; in
particular, this will eliminate all arcs of negative flow. If
|omit=2|, the \.{Adjustments} vertex is also omitted, thereby leaving
79~sectors with arcs showing inter-industry flow. (The graph is no
longer a ``circulation,'' of course, when |omit>0|.)  If \.{Users} and
\.{Adjustments} are not omitted, \.{Users} is the last vertex of the
graph, and \.{Adjustments} is next-to-last.

If |threshold=0|, the digraph has an arc for every nonzero |flow|.
But if |threshold>0|, the digraph becomes more sparse;
there is then an arc from $j$ to~$k$ if and
only if the amount of commodity $j$ used by sector~$k$ exceeds
|threshold/65536| times the total input of sector~$k$.  (The total
input figure always includes value added, even if |omit>0|.)
Thus the arcs go to each sector from
that sector's main suppliers. When |n=79|, |omit=2|, and
|threshold=0|, the digraph has 4602 arcs out of a possible
$79\times79=6241$. Raising |threshold| to 1 decreases the number of
arcs to 4473; raising it to 6000 leaves only~72 arcs.
The |len| field in each arc is~1.

The constructed graph will have $\min(n,81-|omit|)$ vertices. If |n| is less
than |81-omit|, the |n| vertices will be selected by repeatedly combining
related sectors. For example, two of the 81 original sectors are called
`\.{Paper} \.{products,} \.{except} \.{containers}' and
`\.{Paperboard} \.{containers} \.{and} \.{boxes}'; these might be combined
into a sector called `\.{Paper} \.{products}'. There is a binary tree
with 79 leaves, which describes a fixed hierarchical breakdown of the
79 non-special sectors. This tree is
pruned, if necessary, by replacing pairs of leaves by their parent node,
which becomes a new leaf; pruning continues
until just |n| leaves remain. Although pruning is a bottom-up process, its
effect can also be obtained from the top down if we imagine ``growing''
the tree, starting out with a whole economy as a single sector and
repeatedly subdividing a sector into two parts. For example,
if |omit=2| and |n=2|, the two sectors will
be called \.{Goods} and \.{Services}. If |n=3|, \.{Goods} might be
subdivided into \.{Natural} \.{Resources} and \.{Manufacturing}; or
\.{Services} might be subdivided into \.{Indirect} \.{Services} and
\.{Direct} \.{Services}.

If |seed=0|, the binary tree is pruned in such a way that the |n|
resulting sectors are as equal as possible with respect to total
input and output, while respecting the tree structure. If |seed>0|,
the pruning is carried out at random, in such a way that all |n|-leaf
subtrees of the original tree are obtained with approximately equal
probability (depending on |seed| in a machine-independent fashion).
Any |seed| value from 1 to $2^{31}-1=2147483647$ is permissible.

As usual in GraphBase routines, you can set |n=0| to get the default
situation where |n| has its maximum value. For example, either
|econ(0,0,0,0)| or |econ(81,0,0,0)| produces the full graph;
|econ(0,2,0,0)| or |econ(79,2,0,0)| produces the full graph except 
for the two special vertices.

@d MAX_N 81 /* maximum number of vertices in constructed graph */
@d NORM_N MAX_N-2 /* the number of normal SIC sectors */
@d ADJ_SEC MAX_N-1 /* code number for the \.{Adjustments} sector */

@ The U.S. Bureau of Economic Analysis and the U.S. Bureau of the Census have
assigned code numbers 1--79 to the individual sectors for which
statistics are given in \.{econ.dat}. These sector numbers are
traditionally called Standard Industrial Classification (SIC) codes.
If for some reason you want to know the SIC codes for
all sectors represented by vertex |v| of a graph generated by |econ|,
you can access them via a list of |Arc| nodes starting at the utility
field |v->SIC_codes|.
This list is linked by |next| fields in the usual way, and each
SIC code appears in the |len| field; the |tip| field is unused.

The special vertex \.{Adjustments} is given code number~80; it is
actually a composite of six different SIC categories, numbered 80--86 in their
published tables.

For example, if |n=80| and |omit=1|, each list will have length~1.
Hence |v->SIC_codes->next| will equal |NULL| for each~|v|, and
|v->SIC_codes->len| will be |v|'s SIC code, a number between 1 and~80.

The special vertex \.{Users} has no SIC code; it is the only vertex
whose |SIC_codes| field will be null in the graph returned by |econ|.

@d SIC_codes z.A /* utility field |z| leads to the SIC codes for a vertex */

@ The total output of each sector, which also equals the total input of that
sector, is placed in utility field |sector_total| of the corresponding vertex.

@d sector_total y.I /* utility field |y| holds the total flow in and out */

@(gb_econ.h@>=
#define flow @t\quad@> a.I
   /* definitions of utility fields in the header file */
#define SIC_codes @t\quad@> z.A
#define sector_total @t\quad@> y.I

@ If the |econ| routine encounters a problem, it returns |NULL|
(\.{NULL}), after putting a nonzero number into the external variable
|panic_code|. This code number identifies the type of failure.
Otherwise |econ| returns a pointer to the newly created graph, which
will be represented with the data structures explained in {\sc GB\_\,GRAPH}.
(The external variable |panic_code| is itself defined in
{\sc GB\_\,GRAPH}.)

@d panic(c) @+{@+panic_code=c;@+gb_trouble_code=0;@+return NULL;@+}

@ The \CEE/ file \.{gb\_econ.c} has the following overall shape:

@p
#include "gb_io.h" /* we will use the {\sc GB\_\,IO} routines for input */
#include "gb_flip.h"
 /* we will use the {\sc GB\_\,FLIP} routines for random numbers */
#include "gb_graph.h"
 /* and of course we'll use the {\sc GB\_\,GRAPH} data structures */
@h@#
@<Type declarations@>@;
@<Private variables@>@;
@#
Graph *econ(n,omit,threshold,seed)
  unsigned long n; /* number of vertices desired */
  unsigned long omit; /* number of special vertices to omit */
  unsigned long threshold; /* minimum per-64K-age in arcs leading in */
  long seed; /* random number seed */
{@+@<Local variables@>@;@#
  gb_init_rand(seed);
  init_area(working_storage);
  @<Check the parameters and adjust them for defaults@>;
  @<Set up a graph with |n| vertices@>;
  @<Read \.{econ.dat} and note the binary tree structure@>;
  @<Determine the |n| sectors to use in the graph@>;
  @<Put the appropriate arcs into the graph@>;
  if (gb_close()!=0)
    panic(late_data_fault);
     /* something's wrong with |"econ.dat"|; see |io_errors| */
  gb_free(working_storage);
  if (gb_trouble_code) {
    gb_recycle(new_graph);
    panic(alloc_fault); /* oops, we ran out of memory somewhere back there */
  }
  return new_graph;
}

@ @<Local var...@>=
Graph *new_graph; /* the graph constructed by |econ| */
register long j,k; /* all-purpose indices */
Area working_storage; /* tables needed while |econ| does its thinking */

@ @<Check the param...@>=
if (omit>2) omit=2;
if (n==0 || n>MAX_N-omit) n=MAX_N-omit;
else if (n+omit<3) omit=3-n; /* we need at least one normal sector */
if (threshold>65536) threshold=65536;

@ @<Set up a graph with |n| vertices@>=
new_graph=gb_new_graph(n);
if (new_graph==NULL)
  panic(no_room); /* out of memory before we're even started */
sprintf(new_graph->id,"econ(%lu,%lu,%lu,%ld)",n,omit,threshold,seed);
strcpy(new_graph->util_types,"ZZZZIAIZZZZZZZ");

@* The economic tree.
As we read in the data, we construct a sequential list of nodes,
each of which represents either a micro-sector of the economy (one of
the basic SIC sectors) or a macro-sector (which is the union of two subnodes).
In more technical terms, the nodes form an extended binary tree,
whose external nodes correspond to micro-sectors and whose internal nodes
correspond to macro-sectors. The nodes of the tree appear in preorder.
Subsequently we will do a variety of operations on this binary tree,
proceeding either top-down (from the beginning of the list to the end)
or bottom-up (from the end to the beginning).

Each node is a rather large record, because we will store a complete
vector of sector output data in each node.

@<Type declarations@>=
typedef struct node_struct { /* records for micro- and macro-sectors */
  struct node_struct *rchild; /* pointer to right child of macro-sector */
  char title[44]; /* |"Sector name"| */
  long table[MAX_N+1]; /* outputs from this sector */
  unsigned long total; /* total input to this sector ($=$ total output) */
  long thresh; /* |flow| must exceed |thresh| in arcs to this sector */
  long SIC; /* SIC code number; initially zero in macro-sectors */
  long tag; /* 1 if this node will be a vertex in the graph */
  struct node_struct *link; /* next smallest unexplored sector */
  Arc *SIC_list; /* first item on list of SIC codes */
} node;

@ When we read the given data in preorder, we'll need a stack to remember
what nodes still need to have their |rchild| pointer filled in.
(There is a no need for an \\{lchild} pointer, because the left child
always follows its parent immediately in preorder.)

@<Private v...@>=
static node *stack[NORM_N+NORM_N];
static node **stack_ptr; /* current position in |stack| */
static node *node_block; /* array of nodes, specifies the tree in preorder */
static node *node_index[MAX_N+1]; /* which node has a given SIC code */

@ @<Local v...@>=
register node *p,*pl,*pr; /* current node and its children */
register node *q; /* register for list manipulation */

@ @<Read \.{econ.dat} and note the binary tree structure@>=
node_block=gb_typed_alloc(2*MAX_N-3,node,working_storage);
if (gb_trouble_code) panic(no_room+1); /* no room to copy the data */
if (gb_open("econ.dat")!=0)
  panic(early_data_fault);
   /* couldn't open |"econ.dat"| using GraphBase conventions */
@<Read and store the sector names and SIC numbers@>;
for (k=1; k<=MAX_N; k++)
 @<Read and store the output coefficients for sector |k|@>;

@ The first part of \.{econ.dat} specifies the nodes of the binary
tree in preorder. Each line contains a node name
followed by a colon, and the colon is followed by the SIC number if
that node is a leaf.

The tree is uniquely specified in this way,
because of the nature of preorder. (Think of Polish prefix notation,
in which a formula like `${+}x{+}xx$' means `${+}(x,{+}(x,x))$'; the
parentheses in Polish notation are redundant.)

The two special sector names don't appear in the file; we manufacture
them ourselves.

The program here is careful not to clobber itself in the
presence of arbitrarily garbled data.

@<Read and store the sector names...@>=
stack_ptr=stack;
for (p=node_block; p<node_block+NORM_N+NORM_N-1; p++) {@+register long c;
  gb_string(p->title,':');
  if (strlen(p->title)>43) panic(syntax_error); /* sector name too long */
  if (gb_char()!=':') panic(syntax_error+1); /* missing colon */
  p->SIC=c=gb_number(10);
  if (c==0) /* macro-sector */
    *stack_ptr++=p; /* left child is |p+1|, we'll know |rchild| later */
  else { /* micro-sector; |p+1| will be somebody's right child */
    node_index[c]=p;
    if (stack_ptr>stack) (*--stack_ptr)->rchild=p+1;
  }
  if (gb_char()!='\n') panic(syntax_error+2); /* garbage on the line */
  gb_newline();
}
if (stack_ptr!=stack) panic(syntax_error+3); /* tree malformed */
for (k=NORM_N;k;k--) if (node_index[k]==0)
  panic(syntax_error+4); /* SIC code not mentioned in the tree */
strcpy(p->title,"Adjustments");@+p->SIC=ADJ_SEC;@+node_index[ADJ_SEC]=p;