gb_games.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\_\,GAMES}

\prerequisites{GB\_\,GRAPH}{GB\_\,IO}
@* Introduction. This GraphBase module contains the |games| subroutine,
which creates a family of undirected graphs based on college football
scores. An example of the use of this procedure can be
found in the demo program {\sc FOOTBALL}.

@(gb_games.h@>=
extern Graph *games();

@ The subroutine call |games|(|n|, |ap0_weight|, |upi0_weight|, |ap1_weight|,
|upi1_weight|, |first_day|, |last_day|, |seed|)
constructs a graph based on the information in \.{games.dat}.
Each vertex of the graph corresponds to one of 120 football teams
at American colleges and universities (more precisely, to the 106 college
football teams of division I-A together with the 14 division I-AA teams
of the Ivy League and the Patriot League).
Each edge of the graph corresponds to one of the 638 games played
between those teams during the 1990 season.

An arc from vertex~|u| to vertex~|v| is assigned a length representing
the number of points scored by |u| when playing~|v|. Thus the graph
isn't really ``undirected,'' although it is true that its arcs are
paired (i.e., that |u| played~|v| if and only if |v| played~|u|).
A truly undirected graph with the same vertices and edges can be obtained
by applying the |complement| routine of {\sc GB\_\,BASIC}.

The constructed graph will have $\min(n,120)$ vertices. If |n| is less
than 120, the |n| teams will be selected by assigning a weight to
each team and choosing the |n| with largest weight, using random
numbers to break ties in case of equal weights. Weights are computed
by the formula
$$ |ap0_weight|\cdot|ap0|+|upi0_weight|\cdot|upi0|
   +|ap1_weight|\cdot|ap1|+|upi1_weight|\cdot|upi1|, $$
where |ap0| and |upi0| are the point scores given to a team in the
Associated Press and United Press International polls at the beginning
of the season, and |ap1| and |upi1| are the similar scores given at
the end of the season. (The \\{ap} scores were obtained by asking 60
sportswriters to choose and rank the top 25 teams, assigning 25 points
to a team ranked 1st and 1 point to a team ranked 25th; thus the
total of each of the \\{ap} scores, summed over all teams,
is 19500. The \\{upi} scores were
obtained by asking football coaches to choose and rank the top 15
teams, assigning 15 points to a team ranked 1st and 1 point to a team
ranked 15th. In the case of \\{upi0}, there were 48 coaches voting,
making 5760 points altogether; but in the case of \\{upi1}, 59 coaches
were polled, yielding a total of 7080 points. The coaches agreed not
to vote for any team that was on probation for violating NCAA rules,
but the sportswriters had no such policy.)

Parameters |first_day| and |last_day| can be used to vary the number of
edges; only games played between |first_day| and |last_day|, inclusive,
will be included in the constructed graph. Day~0 was August~26, 1990,
when Colorado and Tennessee competed in the Disneyland Pigskin Classic.
Day~128 was January~1, 1991, when the final end-of-season bowl games
were played. About half of each team's games were played between day~0 and
day~50. If |last_day=0|, the value of |last_day| is automatically
increased to~128.

As usual in GraphBase routines, you can set |n=0| to get the default
situation where |n| has its maximum value. For example, either
|games(0,0,0,0,0,0,0,0)| or |games(120,0,0,0,0,0,0,0)| produces the full graph;
|games(0,0,0,0,0,50,0,0)| or |games(120,0,0,0,0,50,0,0)|
or |games(120,0,0,0,0,50,128,0)| produces the graph for the last half
of the season. One way to select a subgraph containing the
30 ``best'' teams is to ask for |games(30,0,0,1,2,0,0,0)|, which adds
the votes of the sportswriters to the votes of the coaches
(considering that a coach's first choice is worth 30 points
while a sportswriter's first choice is worth only 25). It turns out
that 67 of the teams did not receive votes in any of the four polls;
the subroutine call |games(53,1,1,1,1,0,0,0)| will pick out the 53 teams
that were selected at least once by some sportswriter or coach, and
|games(67,-1,-1,-1,-1,0,0,0)| will pick out the 67 that were not.
A~random selection of 60 teams can be obtained by calling
|games(60,0,0,0,0,0,0,s)|. Different choices of the seed number~|s|
will produce different selections in a system-independent manner;
any value of |s| between 0 and $2^{31}-1$ is permissible.
If you ask for |games(120,0,0,0,0,0,0,s)| with different choices of~|s|,
you always get the full graph, but the vertices will appear in different
(random) orderings depending on~|s|.

Parameters |ap0_weight|, |upi0_weight|, |ap1_weight|, and |upi1_weight| must be
at most $2^{17}=131072$ in absolute value.

@d MAX_N 120
@d MAX_DAY 128
@d MAX_WEIGHT 131072
@d ap u.I /* Associated Press scores: |(ap0<<16)+ap1| */
@d upi v.I /* United Press International scores |(upi0<<16)+upi1| */

@ Most of the teams belong to a ``conference,'' and they play against
almost every other team that belongs to the same conference. For
example, Stanford and nine other teams belong to the
Pacific Ten conference. Eight of Stanford's eleven games were against
other teams of the Pacific Ten; the other three were played against
Colorado (from the Big Eight), San Jos\'e State (from the Big West)
and Notre Dame (which is independent). The graphs produced by |games|
therefore illustrate ``cliquey'' patterns of social interaction.

Eleven different conferences are included in \.{games.dat}. Utility
field |z.S| of a vertex is set to the name of a team's conference, or to |NULL|
if that team is independent. (Exactly 24 of the I-A football teams
were independent in 1990.) Two teams |u| and |v| belong to the same
conference if and only if |u->conference==v->conference| and
|u->conference!=NULL|.

@d conference z.S

@ Each team has a nickname, which is recorded in utility field |y.S|.
For example, Georgia Tech's team is called the Yellow Jackets.
Six teams (Auburn, Clemson, Memphis State, Missouri, Pacific, and
Princeton) are called the Tigers, and five teams
(Fresno State, Georgia, Louisiana Tech, Mississippi State,
Yale) are called the Bulldogs. But most of the teams have a unique
nickname, and 94 distinct nicknames exist.

A shorthand code for team names is also provided, in the |abbr| field.

@d nickname y.S
@d abbr x.S

@ If |a| points to an arc from |u| to |v|, utility field |a->a.I| contains
the value 3 if |u| was the home team, 1 if |v| was the home team, and 2 if both
teams played on neutral territory. The date of that game, represented
as a integer number of days after August~26, 1990, appears in utility
field |a->b.I|. The arcs in each vertex list |v->arcs| appear in reverse order
of their dates: last game first and first game last.

@d HOME 1
@d NEUTRAL 2 /* this value is halfway between |HOME| and |AWAY| */
@d AWAY 3
@d venue a.I
@d date b.I

@(gb_games.h@>=
#define ap @[u.I@] /* repeat the definitions in the header file */
#define upi @[v.I@]
#define abbr @[x.S@]
#define nickname @[y.S@]
#define conference @[z.S@]
#define HOME 1
#define NEUTRAL 2
#define AWAY 3
#define venue @[a.I@]
#define date @[b.I@]

@ If the |games| routine encounters a problem, it returns |NULL|
(\.{NULL}), after putting a code number into the external variable
|panic_code|. This code number identifies the type of failure.
Otherwise |games| 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\_games.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" /* we will use the {\sc GB\_\,GRAPH} data structures */
#include "gb_sort.h" /* and |gb_linksort| for sorting */
@h@#
@<Type declarations@>@;
@<Private variables@>@;
@<Private functions@>@;
@#
Graph *games(n,ap0_weight,upi0_weight,ap1_weight,upi1_weight,
     first_day,last_day,seed)
  unsigned long n; /* number of vertices desired */
  long ap0_weight; /* coefficient of |ap0| in the weight function */
  long ap1_weight; /* coefficient of |ap1| in the weight function */
  long upi0_weight; /* coefficient of |upi0| in the weight function */
  long upi1_weight; /* coefficient of |upi1| in the weight function */
  long first_day; /* lower cutoff for games to be considered */
  long last_day; /* upper cutoff for games to be considered */
  long seed; /* random number seed */
{@+@<Local variables@>@;@#
  gb_init_rand(seed);
  @<Check that the parameters are valid@>;
  @<Set up a graph with |n| vertices@>;
  @<Read the first part of \.{games.dat} and compute team weights@>;
  @<Determine the |n| teams to use in the graph@>;
  @<Put the appropriate edges into the graph@>;
  if (gb_close()!=0)
    panic(late_data_fault);
      /* something's wrong with |"games.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 |games| */
register long j,k; /* all-purpose indices */

@ @<Check that the parameters are valid@>=
if (n==0 || n>MAX_N) n=MAX_N;
if (ap0_weight>MAX_WEIGHT || ap0_weight<-MAX_WEIGHT ||
    upi0_weight>MAX_WEIGHT || upi0_weight<-MAX_WEIGHT ||@|
    ap1_weight>MAX_WEIGHT || ap1_weight<-MAX_WEIGHT ||
    upi1_weight>MAX_WEIGHT || upi1_weight<-MAX_WEIGHT)
  panic(bad_specs); /* the magnitude of at least one weight is too big */
if (first_day<0) first_day=0;
if (last_day==0 || last_day>MAX_DAY) last_day=MAX_DAY;

@ @<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,"games(%lu,%ld,%ld,%ld,%ld,%ld,%ld,%ld)",
  n,ap0_weight,upi0_weight,ap1_weight,upi1_weight,first_day,last_day,seed);
strcpy(new_graph->util_types,"IIZSSSIIZZZZZZ");

@* Vertices.
As we read in the data, we construct a list of nodes, each of which contains
a team's name, nickname, conference, and weight. After this list
has been sorted by weight, the top |n| entries will be the vertices of the 
new graph.

@<Type decl...@>=
typedef struct node_struct { /* records to be sorted by |gb_linksort| */
  long key; /* the nonnegative sort key (weight plus $2^{30}$) */
  struct node_struct *link; /* pointer to next record */
  char name[24]; /* |"College Name"| */
  char nick[22]; /* |"Team Nickname"| */
  char abb[6]; /* |"ABBR"| */
  long a0,u0,a1,u1; /* team scores in press polls */
  char *conf; /* pointer to conference name */