gb_raman.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\_\,RAMAN}
\let\==\equiv % congruence sign

\prerequisite{GB\_\,GRAPH}
@* Introduction. This GraphBase module contains the |raman| subroutine,
which creates a family of ``Ramanujan graphs'' based on a theory
developed by Alexander Lubotzky, Ralph Phillips, and Peter Sarnak
@^Lubotzky, Alexander@>
@^Phillips, Ralph Saul@>
@^Sarnak, Peter@>
[see {\sl Combinatorica \bf8} (1988), 261--277].

Ramanujan graphs are defined by the following properties:
@^Ramanujan graphs@>
They are connected, undirected graphs in which every vertex has
degree~$k$, and every eigenvalue of the adjacency matrix
is either $\pm k$ or has absolute value $\le2\sqrt{\mathstrut k-1}$.
Such graphs are known to have good expansion properties, small diameter,
and relatively small independent sets; they cannot be colored with
fewer than $k/\bigl(2\sqrt{\mathstrut k-1}\,\bigr)$ colors unless they are
bipartite. The particular examples of Ramanujan graphs constructed here
are based on interesting properties of quaternions with integer coefficients.

An example of the use of this procedure can be found in the demo program
called {\sc GIRTH}.

@(gb_raman.h@>=
extern Graph *raman();

@ The subroutine call |raman(p,q,type,reduce)|
constructs an undirected graph in which each vertex has degree~|p+1|.
The number of vertices is~|q+1| if |type=1|, or~${1\over2}q(q+1)$ if |type=2|,
or ${1\over2}(q-1)q(q+1)$ if |type=3|, or |(q-1)q(q+1)| if
|type=4|. The graph will be bipartite if and only if it has type~4.
Parameters |p| and |q| must be distinct prime numbers,
and |q|~must be odd. Furthermore there are additional restrictions:
If |p=2|, the other parameter |q| must satisfy $q\bmod8\in\{1,3\}$
and $q\bmod13\in\{1,3,4,9,10,12\}$; this rules out about one fourth of
all primes. Moreover, if |type=3| the value of |p| must be a
quadratic residue modulo~$q$; in other words, there must be an
integer~$x$ such that $x^2\=p$ (mod~$q$). If |type=4|, the value of |p|
must not be a quadratic residue.

If you specify |type=0|, the procedure
will choose the largest permissible type (either 3 or~4);
the value of the type selected will
appear as part of the string placed in the resulting graph's |id| field.
For example, if |type=0|, |p=2|, and |q=43|, a type~4 graph will be
generated, because 2 is not a quadratic residue modulo~43. This
graph will have $44\times43\times42=79464$ vertices, each of degree~3.
(Notice that graphs of types 3 and~4 can be quite large even when
|q| is rather small.)

The largest permissible value of |q| is 46337; this is the largest
prime whose square is less than $2^{31}$. Of course you would use
it only for a graph of type~1.

If |reduce| is nonzero, loops and multiple edges will be suppressed.
In this case the degrees of some vertices might turn out to be less than~|p+1|,
in spite of what was said above.

Although type 4 graphs are bipartite, the vertices
are not separated into two blocks as in other bipartite
graphs produced by GraphBase routines.

All edges of the graphs have length 1.

@ If the |raman| 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 |raman| 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;@+}
@d dead_panic(c) {@+gb_free(working_storage);@+panic(c);@+}
@d late_panic(c) {@+gb_recycle(new_graph);@+dead_panic(c);@+}

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

@p
#include "gb_graph.h" /* we will use the {\sc GB\_\,GRAPH} data structures */
@h@#
@<Type declarations@>@;
@<Private variables and routines@>@;
@#
Graph *raman(p,q,type,reduce)
  long p; /* one less than the desired degree; must be prime */
  long q; /* size parameter; must be prime and properly related to |type| */
  unsigned long type; /* selector between different possible constructions */
  unsigned long reduce; /* if nonzero, multiple edges and self-loops won't occur */
{@+@<Local variables@>@;@#
  @<Prepare tables for doing arithmetic modulo~|q|@>;
  @<Choose or verify the |type|, and determine the number |n| of vertices@>;
  @<Set up a graph with |n| vertices, and assign vertex labels@>;
  @<Compute |p+1| generators that will define the graph's edges@>;
  @<Append the edges@>;
  if (gb_trouble_code)
    late_panic(alloc_fault);
       /* oops, we ran out of memory somewhere back there */
  gb_free(working_storage);
  return new_graph;
}

@ @<Local var...@>=
Graph *new_graph; /* the graph constructed by |raman| */
Area working_storage; /* place for auxiliary tables */

@* Brute force number theory. Instead of using routines like Euclid's
algorithm to compute inverses and square roots modulo~|q|, we have
plenty of time to build complete tables, since |q| is smaller than
the number of vertices we will be generating.

We will make three tables: |q_sqr[k]| will contain $k^2$ modulo~|q|;
|q_sqrt[k]| will contain one of the values of $\sqrt{\mathstrut k}$
if $k$ is a quadratic residue; and |q_inv[k]| will contain the multiplicative
inverse of~|k|.

@<Private...@>=
static long *q_sqr; /* squares */
static long *q_sqrt; /* square roots (or $-1$ if not a quadratic residue) */
static long *q_inv; /* reciprocals */

@ @<Prepare tables for doing arithmetic modulo~|q|@>=
if (q<3 || q>46337) panic(very_bad_specs);
  /* |q| is way too small or way too big */
if (p<2) panic(very_bad_specs+1); /* |p| is way too small */
init_area(working_storage);
q_sqr=gb_typed_alloc(3*q,long,working_storage);
if (q_sqr==0) panic(no_room+1);
q_sqrt=q_sqr+q;
q_inv=q_sqrt+q; /* note that |gb_alloc| has initialized everything to zero */
@<Compute the |q_sqr| and |q_sqrt| tables@>;
@<Find a primitive root |a|, modulo |q|, and its inverse |aa|@>;
@<Compute the |q_inv| table@>;

@ @<Compute the |q_sqr| and |q_sqrt| tables@>=
for (a=1; a<q; a++) q_sqrt[a]=-1;
for (a=1,aa=1; a<q; aa=(aa+a+a+1)%q,a++) {
  q_sqr[a]=aa;
  q_sqrt[aa]=q-a; /* the smaller square root will survive */
  q_inv[aa]=-1;
     /* we make |q_inv[aa]| nonzero when |aa| can't be a primitive root */
}

@ @<Local v...@>=
register long a, aa, k; /* primary indices in loops */
long b, bb, c, cc, d, dd; /* secondary indices */
long n; /* the number of vertices */
long n_factor; /* either ${1\over2}(q-1)$ (type~3) or $q-1$ (type 4) */
register Vertex *v; /* the current vertex of interest */

@ Here we implicitly test that |q| is prime, by finding a primitive
root whose powers generate everything. If |q| is not prime, its smallest
divisor will cause the inner loop in this step to terminate with |k>=q|,
because no power of that divisor will be congruent to~1.

@<Find a primitive root |a|, modulo |q|, and its inverse |aa|@>=
for (a=2; ; a++)
  if (q_inv[a]==0) {
    for (b=a,k=1; b!=1&&k<q; aa=b,b=(a*b)%q,k++) q_inv[b]=-1;
    if (k>=q) dead_panic(bad_specs+1); /* |q| is not prime */
    if (k==q-1) break; /* good, |a| is the primitive root we seek */
  }

@ As soon as we have discovered
a primitive root, it is easy to generate all the inverses. (We
could also generate the discrete logarithms if we had a need for them.)

We set |q_inv[0]=q|; this will be our internal representation of $\infty$.

@<Compute the |q_inv| table@>=
for (b=a,bb=aa; b!=bb; b=(a*b)%q,bb=(aa*bb)%q) q_inv[b]=bb,q_inv[bb]=b;
q_inv[1]=1; q_inv[b]=b; /* at this point |b| must equal |q-1| */
q_inv[0]=q;

@ The conditions we stated for validity of |q| when |p=2| are equivalent
to the existence of $\sqrt{-2}$ and $\sqrt{13}$ modulo~|q|, according
to the law of quadratic reciprocity (see, for example, {\sl Fundamental
Algorithms}, exercise 1.2.4--47).

@<Choose or verify the |type|...@>=
if (p==2) {
  if (q_sqrt[13%q]<0 || q_sqrt[q-2]<0)
    dead_panic(bad_specs+2); /* improper prime to go with |p=2| */
}
if ((a=p%q)==0) dead_panic(bad_specs+3); /* |p| divisible by |q| */
if (type==0) type=(q_sqrt[a]>0? 3: 4);
n_factor=(type==3? (q-1)/2: q-1);
switch (type) {
 case 1: n=q+1;@+break;
 case 2: n=q*(q+1)/2;@+break;
 default: if ((q_sqrt[a]>0 && type!=3) || (q_sqrt[a]<0 && type!=4))@/
             dead_panic(bad_specs+4); /* wrong type for |p| modulo |q| */
   if (q>1289) dead_panic(bad_specs+5); /* way too big for types 3, 4 */
   n=n_factor*q*(q+1);
   break;
}
if (p>=(long)(0x3fffffff/n)) dead_panic(bad_specs+6); /* $(p+1)n\ge2^{30}$ */

@* The vertices. Graphs of type 1 have vertices from the
set $\{0,1,\ldots,q-1,\infty\}$, namely the integers modulo~|q| with
an additional ``infinite'' element thrown in. The idea is to
operate on these quantities by adding constants, and/or multiplying by
constants, and/or taking reciprocals, modulo~|q|.

Graphs of type 2 have vertices that are unordered pairs of
distinct elements from that same $(q+1)$-element set.

Graphs of types 3 and 4 have vertices that are $2\times2$ matrices
having nonzero determinants modulo~|q|. The determinants of type~3 matrices
are, in fact, nonzero quadratic residues. We consider two matrices to be
equivalent if one is obtained from the other by multiplying all entries
by a constant (modulo~|q|); therefore we will normalize all the matrices
so that the second row is either $(0,1)$ or has the form $(1,x)$ for
some~$x$. The total number of equivalence classes of type~4 matrices obtainable
in this way is $(q+1)q(q-1)$, because we can choose the second row in
$q+1$ ways, after which there are two cases: Either the second row is
$(0,1)$, and we can select the upper right corner element arbitrarily
and choose the upper left corner element nonzero; or the second row is $(1,x)$,
and we can select the upper left corner element arbitrarily and then choose
an upper right corner element to make the determinant nonzero. For type~3
the counting is similar, except that ``nonzero'' becomes ``nonzero
quadratic residue,'' hence there are exactly half as many choices.

It is easy to verify that the equivalence classes of matrices that
correspond to vertices in these graphs of types 3 and~4 are closed
under matrix multiplication. Therefore the vertices can be regarded as the
elements of finite groups. The type~3 group for a given |q| is often
called the linear fractional group $LF(2,{\bf F}_q)$, or the
projective special linear group $PSL(2,{\bf F}_q)$, or the linear
simple group $L_2(q)$; it can also be regarded as the group of
$2\times2$ matrices with determinant~1 (mod~$q$), when the matrix $A$
is considered equivalent to $-A$. (This group is a simple group for
all primes |q>2|.) The type~4 group is officially known as the
projective general linear group of degree~2 over the field of |q|~elements,
$PGL(2,{\bf F}_q)$.