% data_structure.tex  Dec 2, 2002

\documentstyle[12pt]{article}
\input epsf      
\epsfverbosetrue

\newcommand{\be}{\begin{equation}}
\newcommand{\ee}{\end{equation}}
\newcommand{\bea}{\begin{eqnarray}}
\newcommand{\eea}{\end{eqnarray}}
\newcommand \no {\noindent}
\newcommand \qed{\vrule height5pt width5pt}
% the ``font'' used for types
\newcommand \type {\it}
\newcommand \reals {R}

\def\reff#1{(\ref{#1})}

\newtheorem{definition}{Definition}
\newtheorem{proposition}{Proposition}
\newtheorem{lemma}{Lemma}
\newtheorem{theorem}{Theorem}

\setlength{\textheight}{21cm}
\setlength{\textwidth}{16cm}
\oddsidemargin 0.0in
\evensidemargin 0.0in
\topmargin 0.0in
\pagestyle{plain}

\begin{document}


\title{Data Structures \\
file : data\_structure.tex}

\maketitle


\section{Points}

There are two classes for points on the lattice: {\type point} 
and {\type rpoint}.
The first one is a $d$-tuple of {\type long}'s and the second is a 
$d$-tuple of {\type double}. {\type rpoint} gives the coordinates 
of the point as a point in $\reals^d$. 
{\type rpoint} gives the integer coordinates with respect to a basis 
for the lattice. The bases used are 

square :        $e1=(1,0), \quad  e2=(0,1)$

triangular :    $e1=(1,0), \quad  e2=(-1/2,\sqrt{3}/2)$

hexagonal :     $e1=(1,0), \quad  e2=(-1/2,\sqrt{3}/2)$

cubic :         $e1=(1,0,0), \quad e2=(0,1,0), \quad  e3=(0,0,1)$

hypercubic :    $e1=(1,0,0,0), \quad e2=(0,1,0,0), 
                \quad e3=(0,0,1,0), \quad e4=(0,0,0,1)$  

\no In the pivot algorithm itself we use only {\type point}. 
{\type rpoint} is used in computing some of the random variables. 

\section{Walks}

Walks are represented by the class {\type walk}. This data structure 
is more than just a linear array of points since it is used to 
avoid carrying out the pivots right after thay are accepted. 

{\type long nsteps;} The number of steps in the walk.   

{\type point* steps;} The sites the walk visits. They run from 
steps[0] to steps[nsteps].

{\type long niter;} This is the ``age'' of the walk, i.e., the number 
of iterations of the pivot algorithm that have been applied to it. 
It is in multiples of INNER\_LOOP, typically a million. 

{\type long npivot;} This is the number of pivots that have been 
accepted but not yet applied to the walk. 

{\type long* ptime;}, {\type long* igroup;} and 
{\type   point* shift;} contain the data needed to carry out the pivots. 

MORE MORE MORE MORE MORE MORE MORE 

\section{Excluded region}

We can simulate the walk in the full space or in several different subsets.
The class {\type excluded\_class} specifies the region the walk is 
excluded from. In the case of projecting the 3d walk onto 2d, 
it also specifies the x and y directions for the plane onto which we project.

{\type int region;} region specifies the region the walk is excluded from:

 =0 : no excluded region, full plane 

 =1 : half plane, walk must satisfy y>0

 =2 : cut: walk not allowed to hit positive x-axis

 =3 : quarter: walk not allowed to hit pos x-axis or pos y-axis

{\type rpoint xn,yn;} xn and yn are unit vectors that define the 
x and y directions for the plane we project onto. We don't input xn and 
yn directly. They are defined by three angles 
theta, phi, xphi (one angle in two dims). After the angles are read in, 
xn and yn are computed. This is done in parameters::scan()


\section{Parameters}

The class {\type parameters} specifies a host of parameters that 
determine the walk being simulated and the random variables that will 
be computed. 

\no {\bf parameters that determine the walk to be simulated}


{\type char init\_walk\_fname[101];} name of file from which initial walk is 
read.

{\type  char final\_walk\_fname[101];} name of file to which we periodically 
write the walk. (final is a misnomer.)

{\type  char pivot\_loc\_fname[101];} name of file from which we read 
{\type pivot\_loc} distribution. This is the array that determines the 
probability for picking pivot locations.

{\type  long iseed;} seed for the random number generator. If it is negative
we use the system clock to generate a seed.

{\type  long nsteps;} number of steps in the walk.

{\type  int algorithm;} This specifies the lattice we use. In a few cases 
it also specifies just what algorithm is used for the lattice. The number
refers to the number of lattice symmetries, excluding the identity.

=  7 for sq lattice using all seven lattice symmetries

= 11 for triangular lattice

=  5 for hexagonal lattice 

= 47 cubic lattice

=383 4d hypercubic lattice

=  2 for sq lattice using only two lattice symmetries (reflections in +-45 deg)

=  1 for Manhattan lattice

\no {\bf NB:} In addition to this parameter there is a variable 
ALGORITHM\_NUMBER which must be defined in variable.h. It must agree with 
algorithm. Is the parameter algorithm really needed? 

{\type  int region;} specifies region in which walk is not allowed, 
and how projection is done. For $|region|$ 

=0 : no excluded region, full plane 

=1 : half plane, walk must satisfy y>0

=2 : cut: walk not allowed to hit positive x-axis

=3 : quarter: walk not allowed to hit pos x-axis or pos y-axis

\no If region is negative the projection is done at an angle to the $z$-axis.
$xn$ and $yn$ are unit vectors that define the x and y directions for the
plane we project onto. We don't input $xn$ and $yn$ directly. 
They are defined by one angle $phi$ in two dimensions, 
and three angles, $theta, phi, xphi$.

{\type  int strict\_flag;} =1 for strict self-avoidance, 
=0 for weak self-avoidance. 

{\type  double beta,p;} only used if {\type strict\_flag==0 }. In this case
each self-intersection gets a penalty of $\exp(-\beta/|i-j|^p)$, where 
the intersection is $\omega(i)=\omega(j)$. If $p=0$ we have a penalty of 
$e^{-\beta}$, i.e., the usual weakly self-avoiding walk. For $p>0$ 
we have the ``forgetful weakly self-avoiding walk.'' 

{\type  long nsimplify;} Pivots are not carried out until {\type npivot}
reaches {\type nsimplify}.

{\type  long niter;} Total number of pivot algorithm iterations that will be 
done is {\type niter*INNER\_LOOP} 

{\type  long nrecord;} We write the data to a file and the walk to a file
when the number of iterations is a multiple of {\type nrecord*INNER\_LOOP}

\medskip

\no {\bf parameters that determine the RV's to be sampled}

{\type long nrv;} number of RV's that will be computed.
The index in all the following runs over $0,1,\cdots,nrv-1$.

{\type long rv\_case[MAX\_NRV];}  specifies which RV is sampled
The list of possibilities is documented in the file src/local.h

{\type double s1[MAX\_NRV], double s2[MAX\_NRV], long n1[MAX\_NRV],
n2[MAX\_NRV], rho[MAX\_NRV];} The meaning of these depend on which 
RV is being computed. They are not all used by all RV's.

{\type double len[MAX\_NRV],rpoint center[MAX\_NRV];} More parameters
whose meaning depends on which RV we are computing. 
These parameters should be of order 1 and independent of $N$.
They will be multiplied by $N^\nu$.

The above list of parameters may need to grow as RV's are added. 
The following parameters determine what is computed for the RV's.
This list of parameters should not change as new RV's are added. 

{\type long nmoments[MAX\_NRV];} number of moments of the RV computed.

{\type long nfourier[MAX\_NRV];} number of fourier coefs of the RV computed.
This assumes the RV has range $[0,1]$. RV's that are angles are usually 
rescaled so their range is $[0,1]$. 

{\type double rv\_value\_low[MAX\_NRV]; double rv\_value\_high[MAX\_NRV]; }
We compute the cdf of the RV for values in the interval from 
$rv\_value\_low[i]$ to $rv\_value\_high[i]$.

{\type long nbin[MAX\_NRV];} Number of intervals into which we divide the 
above interval, i.e., the number of ``bins.'' 
bin\_width is (rv\_value\_high-rv\_value\_low)/nbin.

\no {\bf parameters that determine the ``pfunction'''s to be sampled}

  // Following determine the pfunction's that are sampled. 
  // Index in the following runs 0,1,...,npfunc-1
  long npfunc;
  long pfunc\_case[MAX\_NPFUNC];   // specifies which RV is sampled

  // The possible pfunction's are as follows. (This list may need to be added 
  // to as new pfunc's are added.) 
  // for each value of pfunc\_case there are parameters that determine the 
  //   pfunciton
  // pfunc\_case=1: E(theta) is event that walk passes to the right of 
  //   a point with polar coords theta, r where r=plen*$N^\nu$
  //   For three dimensions we project walk onto a plane 
  //   at angle rho wrt x-axis

  // These are the parameters for the pfunction. 
  // This list will grow as new RV's are implemented.

  // following parameters should be of order 1 and independent of N
  // they will be multiplied by $N^\nu$
  double plen[MAX\_NPFUNC];
  double prho[MAX\_NPFUNC];

  // Following determine what is computed for the pfunction
  // This list should be stable as new pfunctions are added 
  long nval[MAX\_NPFUNC]; 
  long ncos\_coef[MAX\_NPFUNC]; 
  double first\_val[MAX\_NPFUNC]; 
  double last\_val[MAX\_NPFUNC]; 

The class {\type derived\_parameters} contains quantities used in 
the simulation that are not directly input, but instead are computed 
from parameters in the class {\type parameters}.

{\type double scale;} equals  $N^\nu$.

{\type excluded\_class excluded;}

\section{Distributions and probabilities} 

The class {\type distribution} contains the cdf of the RV and various other
quantities like moments and fourier coeffecients.

{\type long nmoments;} The number of moments of the RV computed.

{\type double *moments;}  moment[i] is the expected value of $X^i$, $X$ is
the RV. 

{\type long nfourier;} The number of fourier coefs computed.

{\type double *fourier;} fourier[i] is the expected value of cos(2*PI*i*RV).
This probably needs to be changed. I don't know why we only compute the
cos coefs.  

{\type long nbin;} The number of  ``bins'' for the cdf of RV.

{\type double rv\_value\_low; double rv\_value\_high;} We compute the 
cdf of the RV over the domain $[rv\_value\_low, double rv\_value\_high]$.
If the RV has a bounded domain, this should be it. But some RV's have
unbounded domains. 

bin\_width=(rv\_value\_high-rv\_value\_low)/nbin

{\type double *density; }
density[i] is the probability the RV is less than or equal to 
$i*bin\_width$. density is a bad name.  

class mult\_distribution {
// This class contains several distributions and several pfunctions
// member functions simply call the corresponding member function for each
// distribution and pfunction.
  long nrecord; // number of walks sampled 
  long ndistrib; // number of distributions
  distribution dar[MAX\_NRV]; // the distributions
  long npfunc; // number of pfunctions
  pfunction par[MAX\_NRV]; // the pfunctions
}; 

class pfunction{
  // This class is for the probabilities of a family of events that 
  // depend on a single real parameter. The canonical example is the 
  // probability the walk passes to the right of a given point. This is 
  // a function of the angle of the point.      
  // We compute this function at a finite set of points (obviously).
 private: 
 public:
  long nval; // number of values of the parameter at which we compute prob
    // NB this will typically be round number plus 1, e.g., 1001
  double first\_val; // first value at which we compute
  double last\_val; // last value at which we compute
  // index runs 0 to nval-1
  // probs[i] is the probability of the event for parameter value
  // first\_val+i*(last\_val-first\_val)/(nval-1)
  double *probs; 

  long ncos\_coef; // number of coefs in cosine series 
  double *cos\_coef; // coefs in cosine series 
}; // end class pfunction


\section{Fractal dimensions}

class fractal {
// For 2d sets which are fractal in nature
 private: 
  // fractal is a 2d array of size width by height. site[i][j] is 1 
  // iff (i,j) is occupied. (Indices run 0 to width-1, 0 to height-1.
  // This 2d array is actually stored as a linear array. 
  // site[w][h] is site[h*width+w]  
  long width;
  long height;
  int* site;
};



\end{document}

\end 
