Generalized Domino-Shuffling
\vspace{.1in} The problem of counting tilings of a plane region using specified tiles can often be recast as the problem of counting (perfect) matchings of some subgraph of an Aztec diamond graph $A_n$, or more generally calculating the sum of the weights of all the matchings, where the weight of a matching is equal to the product of the (pre-assigned) weights of the constituent edges (assumed to be non-negative). This article presents efficient algorithms that work in this context to solve three problems: finding the sum of the weights of the matchings of a weighted Aztec diamond graph $A_n$; computing the probability that a randomly-chosen matching of $A_n$ will include a particular edge (where the probability of a matching is proportional to its weight); and generating a matching of $A_n$ at random. The first of these algorithms is equivalent to a special case of Mihai Ciucu's cellular complementation algorithm \cite{Ci2} and can be used to solve many of the same problems. The second of the three algorithms is a generalization of not-yet-published work of Alexandru Ionescu, and can be employed to prove an identity governing a three-variable generating function whose coefficients are all the edge-inclusion probabilities; this formula has been used \cite{CEP} as the basis for asymptotic formulas for these probabilities, but a proof of the generating function identity has not hitherto been published. %%FIX Will I give the proof of the identity? The third of the three algorithms is a generalization of the domino-shuffling algorithm presented in \cite{EKLP}; it enables one to generate random ``diabolo-tilings of fortresses'' and thereby to make intriguing inferences about their asymptotic behavior. \vspace{.1in}
pst-node.tex
%% BEGIN pst-node.tex
%% Generated on <1994/6/7> from `pst-node.doc'.
%% For use with the PostScript header file `pst-node.pro'.
%%
\def\fileversion{93a/b,94beta-97 patch 2}
\def\filedate{1997/07/30}
%%
%% pst-node.tex: Node macros for PSTricks.
%% See the PSTricks read-me file and the User's Guide for documentation.
%%
%% COPYRIGHT 1993, by Timothy Van Zandt, tvz@Princeton.EDU
%%
%% Copying of part or all of any file in the pstricks.tex package
%% is allowed under the following conditions only:
%% (1) You may freely distribute unchanged copies of the files. Please
%% include the documentation when you do so.
%% (2) You may modify a renamed copy of any file, but only for personal
%% use or use within an organization.
%% (3) You may copy fragments from the files, for personal use or for use
%% in a macro package for distribution, as long as credit is given
%% where credit is due.
%%
%% You are NOT ALLOWED to take money for the distribution or use of
%% these files or modified versions or fragments thereof, except for
%% a nominal charge for copying etc.
%%
\message{ v\fileversion, \filedate}
\csname PSTnodesLoaded\endcsname
\let\PSTnodesLoaded\endinput
\ifx\PSTricksLoaded\endinput\else\input pstricks.tex\fi\relax
\edef\TheAtCode{\the\catcode`\@}
\catcode`\@=11
\pstheader{pst-node.pro}
\def\pst@nodedict{tx@NodeDict begin }
\def\pst@zapspace#1 #2{%
#1%
\ifx#2\@empty\else\expandafter\pst@zapspace\fi
#2}
\def\pst@getnode#1#2{%
\pst@expandafter\pst@@getnode{#1},,\@nil#2}
\def\pst@@getnode#1,#2,#3\@nil#4{%
\ifx\@empty#3\@empty
\edef#4{/N@\pst@zapspace#1 \@empty\space}%
\else
\pst@cntg=#1\relax
\pst@cnth=#2\relax
\edef#4{/N@M-\ifnum\psmatrixcnt=\z@ 1\else\the\psmatrixcnt\fi
-\the\pst@cntg-\the\pst@cnth\space}%
\fi}
\def\tx@NewNode{NewNode }
\def\pst@newnode#1#2#3#4{%
\leavevmode
\pst@getnode{#1}\pst@thenode
\pst@Verb{%
\pst@nodedict
{#3}
\ifx\psk@name\relax false \else \psk@name true \fi
\pst@thenode
#2
{#4}
\tx@NewNode
end}%
\global\let\psk@name\relax
\pstree@nodehook
\global\let\pstree@nodehook\relax}
\let\pstree@nodehook\relax
\newif\ifnodealign
\def\psset@nodealign#1{\@nameuse{nodealign#1}}
\psset@nodealign{false}
\def\pst@nodealign{%
\pst@dimg=\ht\pst@hbox
\advance\pst@dimg-\dp\pst@hbox
\divide\pst@dimg2
\lower\pst@dimg}
\def\tx@InitPnode{InitPnode }
\def\pnode{\@ifnextchar({\pnode@}{\pnode@(0,0)}}
\def\pnode@(#1)#2{%
\pst@@getcoor{#1}%
\pst@newnode{#2}{10}{\pst@coor}{\tx@InitPnode}%
\ignorespaces}
\def\tx@InitCnode{InitCnode }
\def\cnode{\pst@object{cnode}}
\def\cnode@i{\@ifnextchar({\cnode@ii}{\cnode@ii(0,0)}}
\def\cnode@ii(#1)#2#3{%
\leavevmode
\hbox{%
\use@par
\pst@@getcoor{#1}%
\pssetlength\pst@dimc{#2}%
\pst@dimg=\psk@dimen\pslinewidth
\advance\pst@dimc-\pst@dimg
\advance\pst@dimc.5\pslinewidth
\ifnodealign
\kern\pst@dimc
\vrule width\z@ height \pst@dimc depth \pst@dimc
\fi
\pscircle@do(#1){#2}%
\pst@newnode{#3}{11}{\pst@coor \pst@number\pst@dimc}{\tx@InitCnode}%
% DG/SR modification begin - Jul. 30, 1997
%\ifnodealign \kern\pst@dimc\egroup \fi}%
\ifnodealign\kern\pst@dimc\fi}%
% DG/SR modification end
\ignorespaces}
\def\Cnode{\pst@object{Cnode}}
\def\Cnode@i{\@ifnextchar({\Cnode@ii}{\Cnode@ii(0,0)}}
\def\Cnode@ii(#1)#2{\cnode@ii(#1){\psk@radius}{#2}}%
\def\cnodeput{\pst@object{cnodeput}}
\def\cnodeput@i{\@ifnextchar({\cnodeput@iii}{\cnodeput@ii}}
\def\cnodeput@ii#1{%
\addto@par{rot={#1}}%
\@ifnextchar({\cnodeput@iii}{\cnodeput@iii(\z@,\z@)}}
\def\cnodeput@iii(#1)#2{%
\pst@killglue
\@fixedradiusfalse
\def\pst@nodehook{\cnodeput@iv{#2}}%
\pst@makebox{\cput@v{#1}}}
\def\cnodeput@iv#1{%
\pst@newnode{#1}{11}{\pscirclebox@iv \pst@number\pslinewidth add}%
{\tx@InitCnode}%
\global\let\pst@nodehook\relax}
\def\Cnodeput{\pst@object{Cnodeput}}
\def\Cnodeput@i{\@ifnextchar({\Cnodeput@iii}{\Cnodeput@ii}}
\def\Cnodeput@ii#1{%
\addto@par{rot={#1}}%
\@ifnextchar({\Cnodeput@iii}{\Cnodeput@iii(\z@,\z@)}}
\def\Cnodeput@iii(#1)#2{%
\pst@killglue
\@fixedradiustrue
\def\pst@nodehook{\Cnodeput@iv{#2}}%
\pst@makebox{\cput@iv{#1}}}
\def\Cnodeput@iv#1{%
\pst@newnode{#1}{11}{%
\pst@number{\wd\pst@hbox} 2 div \pst@number\pst@dima % x y
\pst@number\pst@dimb \pst@number\pslinewidth \psk@dimen .5 sub mul sub }% r
{\tx@InitCnode}%
\global\let\pst@nodehook\relax}
\def\circlenode{\pst@object{circlenode}}
\def\circlenode@i#1{\pst@makebox{\circlenode@ii{#1}}}
\def\circlenode@ii#1{%
\begingroup
\pst@useboxpar
\setbox\pst@hbox=\hbox{%
\cnodeput@iv{#1}%
\pscirclebox@iii
\box\pst@hbox}%
\ifnodealign \psboxseptrue \fi
\ifpsboxsep \pscirclebox@sep \fi
\leavevmode
\ifnodealign\pst@nodealign\fi
\box\pst@hbox
\endgroup}
\def\Circlenode{\pst@object{Circlenode}}
\def\Circlenode@i#1{\pst@makebox{\Circlenode@ii{#1}}}
\def\Circlenode@ii#1{%
\begingroup
\pst@useboxpar
\pst@dima=\ht\pst@hbox
\advance\pst@dima\dp\pst@hbox
\divide\pst@dima\tw@
\pssetlength\pst@dimb\psk@radius
\setbox\pst@hbox=\hbox{%
\Cnodeput@iv{#1}%
\pscircle(.5\wd\pst@hbox,\pst@dima){\pst@dimb}%
\box\pst@hbox}%
\ifnodealign \psboxseptrue \fi
\ifpsboxsep \psCirclebox@sep \fi
\leavevmode
\ifnodealign\pst@nodealign\fi
\box\pst@hbox
\endgroup}
\def\tx@GetRnodePos{GetRnodePos }
\def\tx@InitRnode{InitRnode }
\def\rnode{\@ifnextchar[{\rnode@i}{\def\pst@par{}\rnode@ii}}
\def\rnode@i[#1]{\def\pst@par{ref=#1}\rnode@ii}
\def\rnode@ii#1{\pst@makebox{\rnode@iii\rnode@iv{#1}}}
\def\rnode@iii#1#2{%
% Modification D.G. Jan 97
\leavevmode
\begingroup
#1%
\if@star\pst@starbox\fi
\ifnodealign\lower\pst@dimb\fi
\hbox{%
\pst@newnode{#2}{16}{%
\pst@number{\ht\pst@hbox}%
\pst@number{\dp\pst@hbox}%
\pst@number{\wd\pst@hbox}%
\pst@number\pst@dima
\pst@number\pst@dimb}%
{\tx@InitRnode}%
\box\pst@hbox}%
\endgroup}
\def\rnode@iv{%
\pst@dima=\psk@xref\wd\pst@hbox
\ifx\psk@yref\relax
\pst@dimb=\z@
\else
\pst@dimb=\ht\pst@hbox
\advance\pst@dimb\dp\pst@hbox
\pst@dimb=\psk@yref\pst@dimb
\advance\pst@dimb-\dp\pst@hbox
\fi}
\def\psset@href#1{\pst@checknum{#1}\psk@href}
\psset@href{0}
\def\psset@vref#1{\def\psk@vref{#1}}
\psset@vref{.7ex}
\def\Rnode{\pst@object{Rnode}}
\def\Rnode@i#1{\pst@makebox{\rnode@iii\Rnode@ii{#1}}}
\def\Rnode@ii{%
% Changed according pst-beta.bug December 3, 1993
% (\begingroup removed by D.G. as it seems to doesn't work any more)
% \Rnode doesn't process the optional parameter changes.
%\begingroup
\use@par
\pst@dima=\psk@href\wd\pst@hbox
\advance\pst@dima\wd\pst@hbox
\divide\pst@dima 2
\pssetlength\pst@dimb{\psk@vref}}
\def\tx@DiaNodePos{DiaNodePos }
\def\dianode{\pst@object{dianode}}
\def\dianode@i#1{\pst@makebox{\dianode@ii{#1}}}
\def\dianode@ii#1{%
\begingroup
\pst@useboxpar
\psdiabox@iii
\setbox\pst@hbox=\hbox{%
\pst@newnode{#1}{14}{}{%
/X \pst@number\pst@dima def
/Y \pst@number\pst@dimb def
/w \pst@number\pst@dimc 2 mul def
/h \pst@number\pst@dimd 2 mul def
/NodePos { \tx@DiaNodePos } def}%
\box\pst@hbox}%
\ifnodealign\psboxseptrue\fi
\ifpsboxsep\psdiabox@sep\fi
\ifnodealign\lower\pst@dimb\fi
\box\pst@hbox
\endgroup}
\def\tx@TriNodePos{TriNodePos }
\def\tx@InitTriNode{InitTriNode }
\def\trinode{\pst@object{trinode}}
\def\trinode@i#1{\pst@makebox{\trinode@ii{#1}}}
\def\trinode@ii#1{%
\begingroup
\pst@useboxpar
\pstribox@iii
\setbox\pst@hbox=\hbox{%
\pst@newnode{#1}{14}{}{%
\pst@number\pst@dimc
\pst@number\pst@dimd
\ifodd\psk@trimode
exch
\pst@number\pst@dima
\else
\pst@number\pst@dimb
\fi
\psk@trimode
\pst@number{\wd\pst@hbox}%
\pst@number{\ht\pst@hbox}%
\pst@number{\dp\pst@hbox}%
\tx@InitTriNode}%
\box\pst@hbox}%
\ifnodealign\psboxseptrue\fi
\ifpsboxsep\pstribox@sep\fi
\ifnodealign\lower\pst@tempa\fi
\box\pst@hbox
\endgroup}
\def\tx@OvalNodePos{OvalNodePos }
\def\ovalnode{\pst@object{ovalnode}}
\def\ovalnode@i#1{\pst@makebox{\ovalnode@ii{#1}}}
\def\ovalnode@ii#1{%
\begingroup
\pst@useboxpar
\psovalbox@iii
\setbox\pst@hbox=\hbox{%
\pst@newnode{#1}{14}{}{%
/X \pst@number\pst@dima def
/Y \pst@number\pst@dimb def
/w \pst@number\pst@dimc def
/h \pst@number\pst@dimd def
/NodePos { \tx@OvalNodePos } def}%
\unhbox\pst@hbox}%
\ifnodealign\psboxseptrue\fi
\ifpsboxsep\psovalbox@sep\fi
\ifnodealign\lower\pst@dimb\fi
\box\pst@hbox
\endgroup}
\def\dotnode{\pst@object{dotnode}}
\def\dotnode@i{\@ifnextchar({\dotnode@ii}{\dotnode@ii(\z@,\z@)}}
\def\dotnode@ii(#1)#2{%
\leavevmode
\hbox{%
\use@par
\pst@@getcoor{#1}%
\pst@getdotsize
\pstree@nodehook
\ifnodealign
\pst@dima=\pst@dimg
\kern\pst@dima
\vrule width\z@ height \pst@dimh depth \pst@dimh
\fi
\pst@newnode{#2}{14}{}{%
\pst@coor
/Y ED /X ED
/w \pst@number\pst@dimg def
/h \pst@number\pst@dimh def
/NodePos { \tx@OvalNodePos } def}%
\psdot@ii(#1)%
\ifnodealign\kern\pst@dima\fi}%
\ignorespaces}
\def\psset@framesize#1{\pst@expandafter\psset@@framesize{#1} \@nil}
\def\psset@@framesize#1 #2\@nil{%
\pssetlength\pst@dimg{#1}%
\divide\pst@dimg2
\edef\psk@framewidth{\pst@number\pst@dimg}%
\ifx\@empty#2\@empty
\let\psk@frameheight\psk@framewidth
\else
\pssetlength\pst@dimg{#2}%
\divide\pst@dimg2
\edef\psk@frameheight{\pst@number\pst@dimg}%
\fi}
\psset@framesize{10pt}
\def\fnode{\pst@object{fnode}}
\def\fnode@i{\@ifnextchar({\fnode@ii}{\fnode@ii(\z@,\z@)}}
\def\fnode@ii(#1)#2{%
\leavevmode
\pst@killglue
\hbox{%
\use@par
\begin@ClosedObj
\ifnodealign
\kern\psk@framewidth\p@
\vrule width\z@ height \psk@frameheight\p@ depth \psk@frameheight\p@
\edef\pst@coor{0 0 }%
\else
\pst@@getcoor{#1}%
\fi
\pst@newnode{#2}{14}{}{%
\pst@coor
/Y ED /X ED
/d \psk@dimen .5 sub CLW mul neg def
/r \psk@framewidth d add def
/l r neg def
/u \psk@frameheight d add def
/d u neg def
/NodePos { \tx@GetRnodePos } def}%
\addto@pscode{%
/x2 \psk@framewidth CLW \psk@dimen mul sub def
/y2 \psk@frameheight CLW \psk@dimen mul sub def
\pst@coor 2 copy
y2 sub /y1 ED
x2 sub /x1 ED
y2 add /y2 ED
x2 add /x2 ED
\psk@cornersize
1 index 0 eq { pop pop \tx@Rect } { \tx@OvalFrame } ifelse}%
\def\pst@linetype{2}%
\showpointsfalse
\end@ClosedObj
\ifnodealign\kern\psk@framewidth\p@\fi}%
\ignorespaces}
\def\psset@nodesepA#1{%
\pst@getlength{#1}\psk@nodesepA
\def\psk@nodeseptypeA{0 }}
\def\psset@nodesepB#1{%
\pst@getlength{#1}\psk@nodesepB
\def\psk@nodeseptypeB{0 }}
\def\psset@nodesep#1{%
\pst@getlength{#1}\psk@nodesepA
\let\psk@nodesepB\psk@nodesepA
\def\psk@nodeseptypeA{0 }%
\def\psk@nodeseptypeB{0 }}
\psset@nodesep{0pt}
\def\psset@XnodesepA#1{%
\pst@getlength{#1}\psk@nodesepA
\def\psk@nodeseptypeA{1 }}
\def\psset@XnodesepB#1{%
\pst@getlength{#1}\psk@nodesepB
\def\psk@nodeseptypeB{1 }}
\def\psset@Xnodesep#1{%
\pst@getlength{#1}\psk@nodesepA
\let\psk@nodesepB\psk@nodesepA
\def\psk@nodeseptypeA{1 }%
\def\psk@nodeseptypeB{1 }}
\def\psset@YnodesepA#1{%
\pst@getlength{#1}\psk@nodesepA
\def\psk@nodeseptypeA{2 }}
\def\psset@YnodesepB#1{%
\pst@getlength{#1}\psk@nodesepB
\def\psk@nodeseptypeB{2 }}
\def\psset@Ynodesep#1{%
\pst@getlength{#1}\psk@nodesepA
\let\psk@nodesepB\psk@nodesepA
\def\psk@nodeseptypeA{2 }%
\def\psk@nodeseptypeB{2 }}
\def\psset@armA#1{%
\pst@getlength{#1}\psk@armA
\def\psk@armtypeA{0 }}
\def\psset@armB#1{%
\pst@getlength{#1}\psk@armB
\def\psk@armtypeB{0 }}
\def\psset@arm#1{%
\pst@getlength{#1}\psk@armA
\let\psk@armB\psk@armA
\def\psk@armtypeA{0 }%
\def\psk@armtypeB{0 }}
\psset@arm{10pt}
\def\psset@XarmA#1{%
\pst@getlength{#1}\psk@armA
\def\psk@armtypeA{1 }}
\def\psset@XarmB#1{%
\pst@getlength{#1}\psk@armB
\def\psk@armtypeB{1 }}
\def\psset@Xarm#1{%
\pst@getlength{#1}\psk@armA
\let\psk@armB\psk@armA
\def\psk@armtypeA{1 }%
\def\psk@armtypeB{1 }}
\def\psset@YarmA#1{%
\pst@getlength{#1}\psk@armA
\def\psk@armtypeA{2 }}
\def\psset@YarmB#1{%
\pst@getlength{#1}\psk@armB
\def\psk@armtypeB{2 }}
\def\psset@Yarm#1{%
\pst@getlength{#1}\psk@armA
\let\psk@armB\psk@armA
\def\psk@armtypeA{2 }%
\def\psk@armtypeB{2 }}
\def\psset@offsetA#1{\pst@getlength{#1}\psk@offsetA}
\def\psset@offsetB#1{\pst@getlength{#1}\psk@offsetB}
\def\psset@offset#1{\psset@offsetA{#1}\let\psk@offsetB\psk@offsetA}
\psset@offset{0pt}
\def\psset@angleA#1{\pst@getangle{#1}\psk@angleA}
\def\psset@angleB#1{\pst@getangle{#1}\psk@angleB}%
\def\psset@angle#1{%
\pst@getangle{#1}\psk@angleA
\let\psk@angleB\psk@angleA}
\psset@angle{0}
\def\psset@arcangleA#1{\pst@getangle{#1}\psk@arcangleA}
\def\psset@arcangleB#1{\pst@getangle{#1}\psk@arcangleB}%
\def\psset@arcangle#1{%
\pst@getangle{#1}\psk@arcangleA
\let\psk@arcangleB\psk@arcangleA}
\psset@arcangle{8}
\def\psset@ncurvA#1{\pst@checknum{#1}\psk@ncurvA}
\def\psset@ncurvB#1{\pst@checknum{#1}\psk@ncurvB}%
\def\psset@ncurv#1{\psset@ncurvA{#1}\let\psk@ncurvB\psk@ncurvA}
\psset@ncurv{.67}
\def\tx@GetCenter{GetCenter }
\def\tx@XYPos{XYPos }
\def\tx@GetEdge{GetEdge }
\def\tx@AddOffset{AddOffset }
\def\tx@GetEdgeA{GetEdgeA }
\def\tx@GetEdgeB{GetEdgeB }
\def\tx@GetArmA{GetArmA }
\def\tx@GetArmB{GetArmB }
\def\check@arrow#1#2{%
\check@@arrow#2-\@nil
\if@pst
\addto@par{arrows=#2}%
\def\next{#1}%
\else
\def\next{#1{#2}}%
\fi
\next}
\def\check@@arrow#1-#2\@nil{%
\ifx\@nil#2\@nil\@pstfalse\else\@psttrue\fi}
\def\tx@InitNC{InitNC }
\def\nc@object#1#2#3#4#5{%
\csname begin@#1Obj\endcsname
\showpointsfalse
\pst@getnode{#2}\pst@tempa
\pst@getnode{#3}\pst@tempb
\gdef\npos@default{#4 }%
\addto@pscode{%
/NCLW CLW def
\pst@nodedict
\psk@offsetA
\psk@offsetB neg
\psk@nodesepA
\psk@nodesepB
\psk@nodeseptypeA
\psk@nodeseptypeB
\pst@tempa
\pst@tempb
\tx@InitNC { #5 } if
end}%
\def\use@pscode{%
\pst@Verb{gsave \tx@STV newpath \pst@code\space grestore}%
\gdef\pst@code{}}%
\csname end@#1Obj\endcsname
\pst@shortput}
\def\npos@default{.5 }
\def\pc@object#1{%
\@ifnextchar({\pc@@object#1}{\pst@getarrows{\pc@@object#1}}}
\def\pc@@object#1(#2)(#3){%
\pnode(#2){@@A}\pnode(#3){@@B}%
#1{@@A}{@@B}}
\def\tx@LPutLine{LPutLine }
\def\tx@LPutLines{LPutLines }
\def\tx@BezierMidpoint{BezierMidpoint }
\def\tx@HPosBegin{HPosBegin }
\def\tx@HPosEnd{HPosEnd }
\def\tx@HPutLine{HPutLine }
\def\tx@HPutLines{HPutLines }
\def\tx@VPosBegin{VPosBegin }
\def\tx@VPosEnd{VPosEnd }
\def\tx@VPutLine{VPutLine }
\def\tx@VPutLines{VPutLines }
\def\tx@HPutCurve{HPutCurve }
\def\tx@NCCoor{NCCoor }
\def\tx@NCLine{NCLine }
\def\ncline{\pst@object{ncline}}
\def\ncline@i{\check@arrow{\ncline@ii}}
\def\ncline@ii#1#2{\nc@object{Open}{#1}{#2}{.5}{\tx@NCLine}}
\def\pcline{\pst@object{pcline}}
\def\pcline@i{\pc@object\ncline@ii}
\def\ncLine{\pst@object{ncLine}}
\def\ncLine@i{\check@arrow{\ncLine@ii}}
\def\ncLine@ii#1#2{\nc@object{Open}{#1}{#2}{.5}%
{\tx@NCLine /LPutPos { xB xA yB yA \tx@LPutLine } def}}
\def\tx@NCLines{NCLines }
\def\nclines{\pst@object{nclines}}
\def\nclines@i{\check@arrow\nclines@ii}
\def\nclines@ii#1#2{%
\begingroup
\use@par
\def\pst@aftercoors{\nclines@iii{#1}{#2}}%
\def\pst@coors{}%
\pst@@getcoors}
\def\nclines@iii#1#2{%
\nc@object{Open}{#1}{#2}{.5}{%
tx@Dict begin \psline@iii pop end
mark \pst@coors \tx@NCLines}%
\endgroup
\ignorespaces}
\def\tx@NCCurve{NCCurve }
\def\nccurve{\pst@object{nccurve}}
\def\nccurve@i{\check@arrow{\nccurve@ii}}
\def\nccurve@ii#1#2{\nc@object{Open}{#1}{#2}{.5}{%
/AngleA \psk@angleA\space def /AngleB \psk@angleB\space def
\psk@ncurvB\space \psk@ncurvA\space
\tx@NCCurve}}
\def\pccurve{\pst@object{pccurve}}
\def\pccurve@i{\pc@object\nccurve@ii}
\def\ncarc{\pst@object{ncarc}}
\def\ncarc@i{\check@arrow{\ncarc@ii}}
\def\ncarc@ii#1#2{\nc@object{Open}{#1}{#2}{.5}{%
yB yA sub xB xA sub \tx@Atan dup
\psk@arcangleA\space add /AngleA ED
\psk@arcangleB\space sub 180 add /AngleB ED
\psk@ncurvB\space \psk@ncurvA\space
\tx@NCCurve}}
\def\pcarc{\pst@object{pcarc}}
\def\pcarc@i{\pc@object\ncarc@ii}
\def\tx@NCAngles{NCAngles }
\def\ncangles{\pst@object{ncangles}}
\def\ncangles@i{\check@arrow{\ncangles@ii}}
\def\ncangles@ii#1#2{%
\nc@object{Open}{#1}{#2}{1.5}{\ncangles@iii \tx@NCAngles}}
\def\ncangles@iii{%
tx@Dict begin \psline@iii pop end
/AngleA \psk@angleA def
/AngleB \psk@angleB def
/ArmA \psk@armA def
/ArmB \psk@armB def
/ArmTypeA \psk@armtypeA def
/ArmTypeB \psk@armtypeB def }
\def\pcangles{\pst@object{pcangles}}
\def\pcangles@i{\pc@object\ncangles@ii}
\def\tx@NCAngle{NCAngle }
\def\ncangle{\pst@object{ncangle}}
\def\ncangle@i{\check@arrow{\ncangle@ii}}
\def\ncangle@ii#1#2{%
\nc@object{Open}{#1}{#2}{1.5}{\ncangles@iii \tx@NCAngle}}
\def\pcangle{\pst@object{pcangle}}
\def\pcangle@i{\pc@object\ncangle@ii}
\def\tx@NCBar{NCBar }
\def\ncbar{\pst@object{ncbar}}
\def\ncbar@i{\check@arrow{\ncbar@ii}}
\def\ncbar@ii#1#2{\nc@object{Open}{#1}{#2}{1.5}{%
\ncangles@iii /AngleB \psk@angleA def \tx@NCBar}}
\def\pcbar{\pst@object{pcbar}}
\def\pcbar@i{\pc@object\ncbar@ii}
\def\tx@NCDiag{NCDiag }
\def\ncdiag{\pst@object{ncdiag}}
\def\ncdiag@i{\check@arrow{\ncdiag@ii}}
\def\ncdiag@ii#1#2{%
\nc@object{Open}{#1}{#2}{1.5}{\ncangles@iii \tx@NCDiag}}
\def\pcdiag{\pst@object{pcdiag}}
\def\pcdiag@i{\pc@object\ncdiag@ii}
\def\tx@NCDiagg{NCDiagg }
\def\ncdiagg{\pst@object{ncdiagg}}
\def\ncdiagg@i{\check@arrow{\ncdiagg@ii}}
\def\ncdiagg@ii#1#2{%
\nc@object{Open}{#1}{#2}{.5}{\ncangles@iii \tx@NCDiagg}}
\def\pcdiagg{\pst@object{pcdiagg}}
\def\pcdiagg@i{\pc@object\ncdiagg@ii}
\def\tx@NCLoop{NCLoop }
\def\psset@loopsize#1{\pst@getlength{#1}\psk@loopsize}
\psset@loopsize{1cm}
\def\ncloop{\pst@object{ncloop}}
\def\ncloop@i{\check@arrow{\ncloop@ii}}
\def\ncloop@ii#1#2{%
\nc@object{Open}{#1}{#2}{2.5}%
{\ncangles@iii /loopsize \psk@loopsize def \tx@NCLoop}}
\def\pcloop{\pst@object{pcloop}}
\def\pcloop@i{\pc@object\ncloop@ii}
\def\tx@NCCircle{NCCircle }
\def\nccircle{\pst@object{nccircle}}
\def\nccircle@i{\check@arrow{\nccircle@ii}}
\def\nccircle@ii#1#2{%
\pssetlength\pst@dima{#2}%
\nc@object{Open}{#1}{#1}{.5}{%
/AngleA \psk@angleA def
/r \pst@number\pst@dima def
\tx@NCCircle \psarc@v end}}
\def\tx@NCBox{NCBox }
\def\ncbox{\pst@object{ncbox}}
\def\ncbox@i{\check@arrow{\ncbox@ii}}
\def\ncbox@ii#1#2{%
\def\pst@linetype{2}%
\nc@object{Closed}{#1}{#2}{.5}{%
tx@Dict begin \psline@iii pop end
\psk@boxheight \psk@boxdepth
\tx@NCBox}}
\def\pcbox{\pst@object{pcbox}}
\def\pcbox@i{\pc@object\ncbox@ii}
\def\tx@NCArcBox{NCArcBox }
\def\psset@boxheight#1{\pst@getlength{#1}\psk@boxheight}
\def\psset@boxdepth#1{\pst@getlength{#1}\psk@boxdepth}
\def\psset@boxsize#1{%
\psset@boxheight{#1}%
\let\psk@boxdepth\psk@boxheight}
\psset@boxsize{.4cm}
\def\ncarcbox{\pst@object{ncarcbox}}
\def\ncarcbox@i{\check@arrow{\ncarcbox@ii}}
\def\ncarcbox@ii#1#2{%
\def\pst@linetype{1}%
\nc@object{Closed}{#1}{#2}{.5}{%
\psk@arcangleA \psk@boxheight \psk@boxdepth \pst@number\pslinearc
\tx@NCArcBox}}
\def\pcarcbox{\pst@object{pcarcbox}}
\def\pcarcbox@i{\pc@object\ncarcbox@ii}
\def\tx@Tfan{Tfan }
% Changed according pst-beta.bug December 3, 1993
% nrot=:<angle> does not work when : is active.
\begingroup
\catcode`\:=13
\gdef\pst@activerot{\def:{\string:}}
\endgroup
\def\psset@nrot#1{%
\begingroup
\pst@activerot
\pst@expandafter{\@ifnextchar:{\psset@@nrot}{\psset@@rot}}{#1}\@nil
\global\let\pst@tempg\psk@rot
\endgroup
\let\psk@nrot\pst@tempg}
\def\psset@@nrot:#1\@nil{%
\psset@@rot#1\@nil
\edef\psk@rot{NAngle \ifx\psk@rot\@empty\else\psk@rot add \fi}}
\psset@nrot{0}
\def\tx@LPutCoor{LPutCoor }
\def\tx@LPut{LPut }
\def\psset@npos#1{%
\def\pst@tempa{#1}%
\ifx\pst@tempa\@empty
\def\psk@npos{\npos@default}%
\else
\pst@checknum{#1}\psk@npos
\fi}
\psset@npos{}
\def\ncput{\pst@object{ncput}}
\def\ncput@i{\pst@killglue\pst@makebox{\ncput@ii}}
\def\ncput@ii{%
\begingroup
\use@par
\if@star\pst@starbox\fi
\pst@makesmall\pst@hbox
\pst@rotate\psk@nrot\pst@hbox
\ncput@iii
\endgroup
\pst@shortput}
\def\ncput@iii{%
\leavevmode
\hbox{%
\pst@Verb{%
\pst@nodedict
/t \psk@npos def
\tx@LPut
end
\tx@PutBegin}%
\box\pst@hbox
\pst@Verb{\tx@PutEnd}}}
\def\naput{\pst@object{naput}}
\def\naput@i{\pst@killglue\pst@makebox{\naput@ii{NAngle 90 add}}}
\def\naput@ii#1{%
\begingroup
\use@par
\if@star\pst@starbox\fi
\def\psk@refangle{#1 }%
\let\psk@rot\psk@nrot
\uput@vii
{exch pop add a \tx@PtoC h1 add exch w1 add exch }%
{tx@Dict /NCLW known { NCLW add } if }%
\ncput@iii
\endgroup
\pst@shortput}
\def\nbput{\pst@object{nbput}}
\def\nbput@i{\pst@killglue\pst@makebox{\naput@ii{NAngle 90 sub}}}
\def\psset@tpos#1{%
\pst@checknum{#1}\psk@tpos
\ifdim\psk@tpos \p@<\z@
\def\psk@tpos{.5}%
\@pstrickserr{Bad `tpos' value: `#1'. Must be 0<tpos<1}\@epha
\else
\ifdim\psk@tpos \p@>\p@
\def\psk@tpos{.5}%
\@pstrickserr{Bad `tpos' value: `#1'. Must be 0<tpos<1}\@epha
\fi
\fi}
\psset@tpos{.5}
\def\tvput{\pst@object{tvput}}
\def\tvput@i{\pst@makebox{\psput@tput{H}{1}}}
\def\tlput{\pst@object{tlput}}
\def\tlput@i{\pst@makebox{\psput@tput{H}{true}}}
\def\trput{\pst@object{trput}}
\def\trput@i{\pst@makebox{\psput@tput{H}{false}}}
\def\thput{\pst@object{thput}}
\def\thput@i{\pst@makebox{\psput@tput{V}{1}}}
\def\taput{\pst@object{taput}}
\def\taput@i{\pst@makebox{\psput@tput{V}{true}}}
\def\tbput{\pst@object{tbput}}
\def\tbput@i{\pst@makebox{\psput@tput{V}{false}}}
\def\tx@HPutAdjust{HPutAdjust }
\def\tx@VPutAdjust{VPutAdjust }
\def\psput@tput#1#2{%
\begingroup
\use@par
\pst@tputmakesmall
\leavevmode
\hbox{%
\pst@Verb{%
\pst@nodedict
/t \psk@tpos \pst@tposflip def
tx@NodeDict /HPutPos known
{ #1PutPos }
{ CP /Y ED /X ED /NAngle 0 def /NCLW 0 def }
ifelse
/Sin NAngle sin def
/Cos NAngle cos def
/s \pst@number\pslabelsep NCLW add def
/l \pst@number\pst@dima def
/r \pst@number\pst@dimb def
/h \pst@number\pst@dimc def
/d \pst@number\pst@dimd def
\ifnum1=0#2\else
/flag #2 def
\csname tx@#1PutAdjust\endcsname
\fi
\tx@LPutCoor
end
\tx@PutBegin}%
\box\pst@hbox
\pst@Verb{\tx@PutEnd}}%
\endgroup
\pst@shortput}
\def\pst@tposflip{}
\def\pst@tputmakesmall{%
\pst@dima=\wd\pst@hbox
\divide\pst@dima 2
\pst@dimg=\psk@href\pst@dimg
\pst@dimb\pst@dima
\advance\pst@dima\pst@dimg % leftsize
\advance\pst@dimb-\pst@dimg % rightsize
\pst@dimd=\psk@vref\relax
\pst@dimc=\ht\pst@hbox
\advance\pst@dimc-\pst@dimd % height
\advance\pst@dimd\dp\pst@hbox % depth
\setbox\pst@hbox=\hbox to\z@{%
\kern-\pst@dima\vbox to\z@{\vss\box\pst@hbox\vskip-\pst@dimd}\hss}}
\def\MakeShortNab#1#2{%
  \def\pst@shortput@nab{%
    \def\pst@tempg{\next}%
    \ifx#1\next
      \let\pst@tempg\naput
    \else
      \ifx#2\next
        \let\pst@tempg\nbput
      \else
        \ifx\@sptoken\next
          \let\pst@tempg\pst@shortput
        \fi
      \fi
    \fi
    \pst@tempg}}
\MakeShortNab{^}{_}
\def\MakeShortTablr#1#2#3#4{%
  \def\pst@shortput@tablr{%
    \def\pst@tempg{\next}%
    \ifx#1\next
      \let\pst@tempg\taput
    \else
      \ifx#2\next
        \let\pst@tempg\tbput
      \else
        \ifx#3\next
          \let\pst@tempg\tlput
        \else
          \ifx#4\next
            \let\pst@tempg\trput
          \else
            \ifx\@sptoken\next
              \let\pst@tempg\pst@shortput
            \fi
          \fi
        \fi
      \fi
    \fi
    \pst@tempg}}
\MakeShortTablr{^}{_}{<}{>}
\def\MakeShortTab#1#2{%
  \def\pst@shortput@tab{%
    \def\pst@tempg{\next}%
    \ifx#1\next
      \def\pst@tempg{%
        \@nameuse{%
          t\ifodd\psk@treemode\ifpstreeflip b\else a\fi
          \else\ifpstreeflip r\else l\fi\fi put}}%
    \else
      \ifx#2\next
        \def\pst@tempg{%
          \@nameuse{%
            t\ifodd\psk@treemode\ifpstreeflip a\else b\fi
            \else\ifpstreeflip l\else r\fi\fi put}}%
      \else
        \ifx\@sptoken\next
          \let\pst@tempg\pst@shortput
        \fi
      \fi
    \fi
    \pst@tempg}}
\MakeShortTab{^}{_}
\def\psset@shortput#1{%
\def\pst@tempg{#1}%
\ifx\pst@tempg\@none
\let\pst@shortput\ignorespaces
\else
\@ifundefined{pst@shortput@#1}%
{\@pstrickserr{Bad short put: `#1'}\@ehpa}%
{\edef\pst@shortput{\noexpand\afterassignment\expandafter\noexpand
\csname pst@shortput@#1\endcsname\noexpand\let\noexpand\next}}%
\fi}
\psset@shortput{none}
\def\lput{\def\pst@par{}\pst@ifstar{\@ifnextchar[{\lput@i}{\lput@ii}}}
\def\lput@i[#1]{\addto@par{ref=#1}\lput@ii}
\def\lput@ii{\@ifnextchar({\lput@iv}{\lput@iii}}
\def\lput@iii#1{\addto@par{nrot=#1}\@ifnextchar({\lput@iv}{\ncput@i}}
\def\lput@iv(#1){\addto@par{npos=#1}\ncput@i}
\def\mput{\def\pst@par{}\pst@ifstar{\@ifnextchar[{\mput@i}{\ncput@i}}}
\def\mput@i[#1]{\addto@par{ref=#1}\ncput@i}
\def\Lput{\def\pst@par{}\pst@ifstar{\@ifnextchar[{\Lput@ii}{\Lput@i}}}
\def\Lput@i#1{\addto@par{labelsep=#1}\Lput@ii}
\def\Lput@ii[#1]{\addto@par{ref={#1}}\@ifnextchar({\Lput@iv}{\Lput@iii}}
\def\Lput@iii#1{\addto@par{nrot={#1}}\@ifnextchar({\Lput@iv}{\Lput@v}}
\def\Lput@iv(#1){\addto@par{npos=#1}\Lput@v}
\def\Lput@v{\pst@killglue\pst@makebox{\Lput@vi}}
\def\Lput@vi{%
\begingroup
\use@par
\if@star\pst@starbox\fi
\Rput@vi
\pst@makesmall\pst@hbox
\pst@rotate\psk@nrot\pst@hbox
\ncput@iii
\endgroup
\pst@shortput}
\def\Mput{\def\pst@par{}\pst@ifstar{\@ifnextchar[{\Mput@ii}{\Mput@i}}}
\def\Mput@i#1{\addto@par{labelsep=#1}\Mput@ii}
\def\Mput@ii[#1]{\addto@par{ref={#1}}\Lput@v}
\def\aput@#1{\def\pst@par{}\pst@ifstar{\@ifnextchar[{\aput@i#1}{\aput@ii#1}}}
\def\aput@i#1[#2]{\addto@par{labelsep=#2}\aput@ii#1}
\def\aput@ii#1{\@ifnextchar({\aput@iv#1}{\aput@iii#1}}
\def\aput@iii#1#2{\addto@par{nrot=#2}\@ifnextchar({\aput@iv#1}{#1}}
\def\aput@iv#1(#2){\addto@par{npos=#2}#1}
\def\aput{\aput@\naput@i}
\def\bput{\aput@\nbput@i}
\def\Aput{\def\pst@par{}\pst@ifstar{\@ifnextchar[{\Aput@i}{\naput@i}}}
\def\Aput@i[#1]{\addto@par{labelsep=#1}\naput@i}
\def\Bput{\def\pst@par{}\pst@ifstar{\@ifnextchar[{\Bput@i}{\nbput@i}}}
\def\Bput@i[#1]{\addto@par{labelsep=#1}\nbput@i}
\def\node@coor#1;#2\@nil{%
\pst@getnode{#1}\pst@tempg
\edef\pst@coor{%
\pst@nodedict
tx@NodeDict \pst@tempg known
{ \pst@tempg load \tx@GetCenter }
{ 0 0 }
ifelse
end }}
\def\Node@coor[#1]#2;#3\@nil{%
\begingroup
\psset{#1}%
\@ifnextchar\bgroup{\Node@@@coor}{\Node@@coor}#2\@nil
\endgroup
\let\pst@coor\pst@tempg}
\def\Node@@coor#1\@nil{%
\pst@getnode{#1}\pst@tempg
\xdef\pst@tempg{%
\pst@nodedict
tx@NodeDict \pst@tempg known
{ \psk@nodesepA \psk@angleA
\pst@tempg load \psk@nodeseptypeA \tx@GetEdge
\psk@offsetA \psk@angleA \tx@AddOffset
\pst@tempg load \tx@GetCenter
3 -1 roll add 3 1 roll add exch }
{ CP }
ifelse
end }}%
\def\Node@@@coor#1{%
\pst@@getcoor{#1}%
\def\psk@angleA{%
\pst@tempg load \tx@GetCenter \pst@coor
3 -1 roll sub 3 1 roll sub neg \tx@Atan}%
\Node@@coor}
\def\nput{\pst@object{nput}}
\def\nput@i#1#2{\pst@killglue\pst@makebox{\nput@ii{#1}{#2}}}
\def\nput@ii#1#2{%
\begingroup
\use@par
\psset@refangle{#1}%
\let\psk@angleA\psk@refangle
\edef\psk@nodesepA{\pst@number\pslabelsep}%
\def\psk@nodeseptypeA{0 }%
\pslabelsep\z@
\uput@vi
\Node@@coor#2\@nil
\let\pst@coor\pst@tempg
\leavevmode
\psput@special\pst@hbox
\endgroup
\ignorespaces}
\newcount\psrow
\newcount\pscol
\newcount\psmatrixcnt
\newskip\psrowsep
\newskip\pscolsep
\def\psset@colsep#1{\pssetlength\pscolsep{#1}}
\def\psset@rowsep#1{\pssetlength\psrowsep{#1}}
\psset@colsep{1.5cm}
\psset@rowsep{1.5cm}
\newif\ifpsmatrix
% Modification Denis GIROU (CNRS/IDRIS - France) - &lt;Denis.Girou@idris.fr&gt; -  5 Sep. 1996
% Workaround for problem with \psspan with LaTeX 2e
% (still correct in compatibility mode)
% This workaround is not beautiful, and can perhaps introduce problems
% in other contexts, but I haven't a better one...
%
% modified again by S Rahtz
% 1997/03/25; dont use \newcount\mscount\def\iterate{}
\let\mscount\@multicnt
\def\psmatrix{%
\begingroup
{\ifnum0=`}\fi % Don't want to expand any &.
\@ifnextchar[{\psmatrix@i}{\ifnum0=`{\fi}{}\psmatrix@ii}}
\def\psmatrix@i[#1]{%
\ifnum0=`{\fi}{}%
\psset{#1}%
\psmatrix@ii}
\def\psmatrix@ii{%
\KillGlue
\edef\psm@beginmath{%
\ifmmode$\m@th\ifinner\textstyle\else\displaystyle\fi\fi}%
\edef\psm@endmath{\ifmmode$\fi}%
\let\\\psm@cr
\advance\psmatrixcnt 1
\def\psm@thenode{M-\the\psmatrixcnt-\the\psrow-\the\pscol}%
\tabskip\z@
\psrow1
\pscol\z@
\psset@shortput{tablr}%
\leavevmode
\vbox\bgroup\halign\bgroup&%
\begingroup
\global\advance\pscol 1
\csname psrowhook\romannumeral\psrow\endcsname
\csname pscolhook\romannumeral\pscol\endcsname
\psm@beginnode##\psm@endnode\endgroup
\cr}
\def\endpsmatrix{%
\crcr\egroup\unskip\egroup
\endgroup}
\def\psm@cr{{\ifnum0=`}\fi\@ifnextchar[{\psm@@cr}{\psm@@@cr{}}}
\def\psm@@cr[#1]{\psm@@@cr{\vskip#1\relax}}
\def\psm@@@cr#1{%
\ifnum0=`{\fi}{}\cr
\noalign{%
\global\advance\psrow 1
\global\pscol\z@
\vskip\psrowsep
#1}}
\def\psm@beginnode{%
\@ifnextchar\psm@endnode
{\let\psm@endnode@i\relax\setbox\pst@hbox=\hbox{}}%
{\pst@object{psm@beginnode}}}
\def\psm@beginnode@i{%
\setbox\pst@hbox=\hbox\bgroup
\psm@beginmath
\begingroup
\ignorespaces}
\def\psm@endnode@i{%
\unskip
\endgroup
\psm@endmath
\egroup
\use@par
\@psttrue}
\def\psm@endnode{%
\@pstfalse
\psm@endnode@i
\ifnum\pscol>1 \hskip\pscolsep \fi
\psk@mnodesize
\hfil
\nodealigntrue
\if@pst
\csname mnode@\psk@mnode\endcsname
\else
\csname mnode@\psk@emnode\endcsname
\fi
\psk@mcol
\psk@@mnodesize}
\def\psspan#1{\mscount#1\relax\loop\ifnum\mscount>\@ne \sp@n\repeat}
\def\psset@name#1{\pst@getnode{#1}\psk@name}
\let\psk@name\relax
\def\psset@mcol#1{%
\ifx r#1\relax
\let\psk@mcol\relax
\else
\ifx l#1\relax
\let\psk@mcol\hfill
\else
\let\psk@mcol\hfil
\fi
\fi}
\psset@mcol{c}
\def\psset@mnodesize#1{%
\pssetlength\pst@dimg{#1}%
\ifdim\pst@dimg<\z@
\let\psk@mnodesize\relax
\let\psk@@mnodesize\relax
\else
\edef\psk@mnodesize{\noexpand\hbox to\number\pst@dimg sp\noexpand\bgroup}%
\let\psk@@mnodesize\egroup
\fi}
\psset@mnodesize{-1pt}
\def\mnode@R{\rnode@iii\Rnode@ii{\psm@thenode}}
\def\mnode@r{\rnode@iii\rnode@iv{\psm@thenode}}
\def\mnode@oval{\ovalnode@ii{\psm@thenode}}
\def\mnode@tri{\trinode@ii{\psm@thenode}}
\def\mnode@dia{\dianode@ii{\psm@thenode}}
\def\mnode@C{{\nodealigntrue\cnode@ii(\z@,\z@){\psk@radius}{\psm@thenode}}}
\def\mnode@f{{\nodealigntrue\fnode@ii(\z@,\z@){\psm@thenode}}}
\def\mnode@circle{\circlenode@ii{\psm@thenode}}
\def\mnode@p{\pnode(\z@,\z@){\psm@thenode}}
% DG/SR modification begin - Jul. 22, 1997
\def\mnode@dot{\dotnode@ii(\z@,\z@){\psm@thenode}}
% DG/SR modification end
\def\mnode@none{\box\pst@hbox}
\def\psset@mnode#1{%
\@ifundefined{mnode@#1}%
{\@pstrickserr{\string\psmatrix\space node `#1' not defined.}\@ehpa}%
{\edef\psk@mnode{#1}}}
\def\psset@emnode#1{%
\@ifundefined{mnode@#1}%
{\@pstrickserr{\string\psmatrix\space node `#1' not defined.}\@ehpa}%
{\edef\psk@emnode{#1}}}
\psset@mnode{R}
\psset@emnode{none}
%%%% FROM pst-coil.tex
\def\nccoil{\pst@object{nccoil}}
\def\nccoil@i{\check@arrow{\nccoil@ii}}
\def\nccoil@ii#1#2{\nc@object{Open}{#1}{#2}{.5}{%
\tx@NCCoor
tx@Dict begin
\psk@coilwidth \pscoilheight
\psk@coilarmA \psk@coilarmB
\psk@coilaspect \psk@coilinc
\pst@coildict \tx@Coil end
end}}
\def\nczigzag{\pst@object{nczigzag}}
\def\nczigzag@i{\check@arrow{\nczigzag@ii}}
\def\nczigzag@ii#1#2{\nc@object{Open}{#1}{#2}{.5}{%
\tx@NCCoor
tx@Dict begin
\pscoilheight
\psk@coilwidth
\psk@coilarmA
\psk@coilarmB
\pst@coildict \tx@ZigZag end
\psline@iii
\tx@Line
end}}
\catcode`\@=\TheAtCode\relax
\endinput
%%
%% END pst-node.tex


pstricks.tex
%% BEGIN: pstricks.tex
%% Generated on <1994/6/16> from `pstricks.doc'.
%% For use with the PostScript header file `pstricks.pro'.
%%
\def\fileversion{93a/b-97 patch 3}
\def\filedate{1997/07/11}
%%
%% pstricks.tex: Main input file for the PSTricks package.
%% PostScript macros for Generic TeX.
%% See the PSTricks read-me file and the User's Guide for documentation.
%%
%% COPYRIGHT 1993, by Timothy Van Zandt, tvz@Princeton.EDU
%%
%% Copying of part or all of any file in the pstricks.tex package
%% is allowed under the following conditions only:
%% (1) You may freely distribute unchanged copies of the files. Please
%% include the documentation when you do so.
%% (2) You may modify a renamed copy of any file, but only for personal
%% use or use within an organization.
%% (3) You may copy fragments from the files, for personal use or for use
%% in a macro package for distribution, as long as credit is given
%% where credit is due.
%%
%% You are NOT ALLOWED to take money for the distribution or use of
%% these files or modified versions or fragments thereof, except for
%% a nominal charge for copying etc.
%%
\csname PSTricksLoaded\endcsname
\let\PSTricksLoaded\endinput
\edef\PstAtCode{\the\catcode`\@}
\catcode`\@=11\relax
\expandafter\ifx\csname @latexerr\endcsname\relax
\long\def\@ifundefined#1#2#3{\expandafter\ifx\csname
#1\endcsname\relax#2\else#3\fi}
\def\@namedef#1{\expandafter\def\csname #1\endcsname}
\def\@nameuse#1{\csname #1\endcsname}
\def\@eha{%
Your command was ignored.^^J
Type \space I <command> <return> \space to replace
it with another command,^^J
or \space <return> \space to continue without it.}
\def\@spaces{\space\space\space\space}
\def\typeout#1{\immediate\write\@unused{#1}}
\alloc@7\write\chardef\sixt@@n\@unused
\def\@empty{}
\def\@gobble#1{}
\def\@nnil{\@nil}
\def\@ifnextchar#1#2#3{%
\let\@tempe#1\def\@tempa{#2}\def\@tempb{#3}\futurelet\@tempc\@ifnch}
\def\@ifnch{%
\ifx\@tempc\@sptoken
\let\@tempd\@xifnch
\else
\ifx\@tempc\@tempe \let\@tempd\@tempa \else \let\@tempd\@tempb \fi
\fi
\@tempd}
\begingroup
\def\:{\global\let\@sptoken= } \:
\def\:{\@xifnch} \expandafter\gdef\: {\futurelet\@tempc\@ifnch}
\endgroup
\fi
\typeout{`PSTricks' v\fileversion\space\space <\filedate> (tvz)}
\def\@pstrickserr#1#2{%
\begingroup
\newlinechar`\^^J
\edef\pst@tempc{#2}%
\expandafter\errhelp\expandafter{\pst@tempc}%
\typeout{%
PSTricks error. \space See User's Guide for further information.^^J
\@spaces\@spaces\@spaces\@spaces
Type \space H <return> \space for immediate help.}%
\errmessage{#1}%
\endgroup}
\def\@ehpa{%
Your command was ignored. Default value substituted.^^J
Type \space <return> \space to procede.}
\def\@ehpb{%
Your command was ignored. Will recover best I can.^^J
Type \space <return> \space to procede.}
\def\@ehpc{%
You better fix this before proceding.^^J
See the PSTricks User's Guide or ask your system administrator for help.^^J
Type \space X <return> \space to quit.}
\def\pst@misplaced#1{\@pstrickserr{Misplaced \string#1 command}\@ehpb}
\newdimen\pst@dima
\newdimen\pst@dimb
\newdimen\pst@dimc
\newdimen\pst@dimd
\newdimen\pst@dimg
\newdimen\pst@dimh
\newbox\pst@hbox
\newbox\pst@boxg
\newcount\pst@cnta
\newcount\pst@cntb
\newcount\pst@cntc
\newcount\pst@cntd
\newcount\pst@cntg
\newcount\pst@cnth
\newif\if@pst
\newtoks\pst@toks
\newif\if@star
\def\pst@ifstar#1{%
\@ifnextchar*{\@startrue\def\next*{#1}\next}{\@starfalse#1}}
\def\pst@expandafter#1#2{%
\def\next{#1}%
\edef\@tempa{#2}%
\ifx\@tempa\@empty
\@pstrickserr{Unexpected empty argument!}\@ehpb
\def\@tempa{\@empty}%
\fi
\expandafter\next\@tempa}
\def\pst@dimtonum#1#2{\edef#2{\pst@@dimtonum#1}}
\def\pst@@dimtonum#1{\expandafter\pst@@@dimtonum\the#1}
{\catcode`\p=12 \catcode`\t=12 \global\@namedef{pst@@@dimtonum}#1pt{#1}}
\def\pst@pyth#1#2#3{%
\ifdim#1>#2\pst@@pyth#1#2#3\else\pst@@pyth#2#1#3\fi}
\def\pst@@pyth#1#2#3{%
\ifdim4#1>9#2%
#3=#1\advance#3 .2122#2%
\else
#3=.8384#1\advance#3 .5758#2%
\fi}
\def\pst@divide#1#2#3{%
\pst@@divide{#1}{#2}%
\pst@dimtonum\pst@dimg{#3}}
\def\pst@@divide#1#2{%
\pst@dimg=#1\relax
\pst@dimh=#2\relax
\pst@cntg=\pst@dimh
\pst@cnth=67108863
\pst@@@divide\pst@@@divide\pst@@@divide\pst@@@divide
\divide\pst@dimg\pst@cntg}
\def\pst@@@divide{%
\ifnum
\ifnum\pst@dimg<\z@-\fi\pst@dimg<\pst@cnth
\multiply\pst@dimg\sixt@@n
\else
\divide\pst@cntg\sixt@@n
\fi}
\def\pst@configerr#1{%
\@pstrickserr{\string#1 not defined in pstricks.con}\@ehpc}
% % \begin{macrocode}
\def\pstVerb#1{\pst@configerr\pstVerb}
\def\pstverb#1{\pst@configerr\pstverb}
\def\pstverbscale{\pst@configerr\pstverbscale}
\def\pstrotate{\pst@configerr\pstrotate}
\def\pstheader#1{\pst@configerr\pstheader}
\def\pstdriver{\pst@configerr\pstdriver}
\@ifundefined{pstcustomize}%
{\def\pstcustomize{\endinput\let\pstcustomize\relax}}{}
\input pstricks.con
\newif\ifPSTricks
\PSTrickstrue
\def\PSTricksOff{%
\def\pstheader##1{}%
\def\pstverb##1{}%
\def\pstVerb##1{}%
\PSTricksfalse}
\@ifundefined{pst@def}{\def\pst@def#1<#2>{\@namedef{tx@#1}{#2 }}}{}
\@ifundefined{pst@ATH}{\def\pst@ATH<#1>{}}{}
\pstheader{pstricks.pro}
\def\pst@dict{tx@Dict begin }
\def\pst@theheaders{pstricks.pro}
\def\pst@Verb#1{\pstVerb{\pst@dict #1 end}}
\def\tx@Atan{Atan }
\def\tx@Div{Div }
\def\tx@NET{NET }
\def\tx@Pyth{Pyth }
\def\tx@PtoC{PtoC }
\def\tx@PathLength@{PathLength@ }
\def\tx@PathLength{PathLength }
\pst@dimg=\pstunit\relax
\ifdim\pst@dimg=1bp
\def\pst@stp{.996264 dup scale}
\else
\edef\pst@stp{1 \pst@@dimtonum\pst@dimg\space div dup scale}
\fi
\def\tx@STP{STP }
\def\tx@STV{STV }
\def\pst@number#1{\pst@@dimtonum#1\space}
\def\pst@checknum#1#2{%
\edef\next{#1}%
\ifx\next\@empty
\let\pst@num\z@
\else
\expandafter\pst@@checknum\next..\@nil
\fi
\ifnum\pst@num=\z@
\@pstrickserr{Bad number: `#1'. 0 substituted.}\@ehpa
\def#2{0 }%
\else
\edef#2{\ifnum\pst@num=\tw@-\fi\the\pst@cntg.%
\expandafter\@gobble\the\pst@cnth\space}%
\fi}
\def\pst@@checknum{%
\@ifnextchar-%
{\let\pst@num\tw@\expandafter\pst@@@checknum\@gobble}%
{\let\pst@num\@ne\pst@@@checknum}}
\def\pst@@@checknum#1.#2.#3\@nil{%
\afterassignment\pst@@@@checknum\pst@cntg=0#1\relax\@nil
\afterassignment\pst@@@@checknum\pst@cnth=1#2\relax\@nil}
\def\pst@@@@checknum#1\relax\@nil{%
\ifx\@nil#1\@nil\else\let\pst@num\z@\fi}
\def\pst@getnumii#1 #2 #3\@nil{%
\pst@checknum{#1}\pst@tempg
\pst@checknum{#2}\pst@temph}
\def\pst@getnumiii#1 #2 #3 #4\@nil{%
\pst@checknum{#1}\pst@tempg
\pst@checknum{#2}\pst@temph
\pst@checknum{#3}\pst@tempi}
\def\pst@getnumiv#1 #2 #3 #4 #5\@nil{%
\pst@checknum{#1}\pst@tempg
\pst@checknum{#2}\pst@temph
\pst@checknum{#3}\pst@tempi
\pst@checknum{#4}\pst@tempj}
\def\pst@getdimnum#1 #2 #3\@nil{%
\pssetlength\pst@dimg{#1}%
\pst@checknum{#2}\pst@tempg}
\def\pst@getscale#1#2{%
\pst@expandafter\pst@getnumii{#1 #1} {} {} {}\@nil
\@psttrue
\ifdim\pst@tempg\p@=\z@
\@pstrickserr{Bad scaling argument `#1'}\@ehpa
\def\pst@tempg{1 }%
\@pstfalse
\fi
\ifdim\pst@temph\p@=\z@
\if@pst\@pstrickserr{Bad scaling argument `#1'}\@ehpa\fi
\def\pst@temph{1 }%
\fi
\edef#2{\pst@tempg\space \pst@temph\space scale }%
\ifdim\pst@tempg\p@=\p@ \ifdim\pst@temph\p@=\p@
\def#2{}%
\fi\fi}
\def\pst@getint#1#2{%
\pst@cntg=#1\relax
\edef#2{\the\pst@cntg\space}}
\begingroup
\catcode`\{=12
\catcode`\}=12
\catcode`\[=1
\catcode`\]=2
\gdef\pslbrace[{ ]
\gdef\psrbrace[} ]
\endgroup
\def\@newcolor#1#2{%
\expandafter\edef\csname #1\endcsname{\noexpand\pst@color{#2}}%
\expandafter\edef\csname color@#1\endcsname{#2}%
\ignorespaces}
\def\pst@color#1{%
\def\pst@currentcolor{#1}\pstVerb{#1}\aftergroup\pst@endcolor}
\def\pst@endcolor{\pstVerb{\pst@currentcolor}}
\def\pst@currentcolor{0 setgray}
\def\altcolormode{%
\def\pst@color##1{%
\pstVerb{gsave ##1}\aftergroup\pst@endcolor}%
\def\pst@endcolor{\pstVerb{\pst@grestore}}}
\def\pst@grestore{%
currentpoint
matrix currentmatrix
currentfont
grestore
setfont
setmatrix
moveto}
\def\pst@usecolor#1{\csname color@#1\endcsname\space}
\def\newgray#1#2{%
\pst@checknum{#2}\pst@tempg
\@newcolor{#1}{\pst@tempg setgray}}
\def\newrgbcolor#1#2{%
\pst@expandafter\pst@getnumiii{#2} {} {} {} {}\@nil
\@newcolor{#1}{\pst@tempg \pst@temph \pst@tempi setrgbcolor}}
\def\newhsbcolor#1#2{%
\pst@expandafter\pst@getnumiii{#2} {} {} {} {}\@nil
\@newcolor{#1}{\pst@tempg \pst@temph \pst@tempi sethsbcolor}}
\def\newcmykcolor#1#2{%
\pst@expandafter\pst@getnumiv{#2} {} {} {} {} {}\@nil
\@newcolor{#1}{\pst@tempg \pst@temph \pst@tempi \pst@tempj setcmykcolor}}
\newgray{black}{0}
\newgray{darkgray}{.25}
\newgray{gray}{.5}
\newgray{lightgray}{.75}
\newgray{white}{1}
\newrgbcolor{red}{1 0 0}
\newrgbcolor{green}{0 1 0}
\newrgbcolor{blue}{0 0 1}
\newrgbcolor{yellow}{1 1 0}
\newrgbcolor{cyan}{0 1 1}
\newrgbcolor{magenta}{1 0 1}
\def\psset#1{\@psset#1,\@nil\ignorespaces}
\def\@psset#1,{%
\@@psset#1==\@nil
\@ifnextchar\@nil{\@gobble}{\@psset}}
\def\@@psset#1=#2=#3\@nil{%
\@ifundefined{psset@#1}%
{\@pstrickserr{Graphics parameter `#1' not defined.}\@ehpa}%
{\@nameuse{psset@#1}{#2}}}%
\def\psset@style#1{%
\@ifundefined{pscs@#1}%
{\@pstrickserr{Custom style `#1' undefined}\@ehpa}%
{\@nameuse{pscs@#1}}}
\def\newpsstyle#1#2{\@namedef{pscs@#1}{\psset{#2}}}
\def\@none{none}
\def\pst@getcolor#1#2{%
\@ifundefined{color@#1}%
{\@pstrickserr{Color `#1' not defined}\@eha}%
{\edef#2{#1}}}
\newdimen\psunit \psunit 1cm
\newdimen\psxunit \psxunit 1cm
\newdimen\psyunit \psyunit 1cm
\let\psrunit\psunit
\def\pstunit@off{\let\@psunit\ignorespaces\ignorespaces}
\def\pssetlength#1#2{%
\let\@psunit\psunit
\afterassignment\pstunit@off
#1 #2\@psunit}
\def\psaddtolength#1#2{%
\let\@psunit\psunit
\afterassignment\pstunit@off
\advance#1 #2\@psunit}
\def\pssetxlength#1#2{%
\let\@psunit\psxunit
\afterassignment\pstunit@off
#1 #2\@psunit}
\def\pssetylength#1#2{%
\let\@psunit\psyunit
\afterassignment\pstunit@off
#1 #2\@psunit}
\def\psset@unit#1{%
\pssetlength\psunit{#1}%
\psxunit=\psunit
\psyunit=\psunit}
\def\psset@runit#1{\pssetlength\psrunit{#1}}
\def\psset@xunit#1{\pssetxlength\psxunit{#1}}
\def\psset@yunit#1{\pssetylength\psyunit{#1}}
\def\pst@getlength#1#2{%
\pssetlength\pst@dimg{#1}%
\edef#2{\pst@number\pst@dimg}}
\def\pst@@getlength#1#2{%
\pssetlength\pst@dimg{#1}%
\edef#2{\number\pst@dimg sp}}
\def\pst@getcoor#1#2{\pst@@getcoor{#1}\let#2\pst@coor}
\def\pst@coor{0 0 }
\def\pst@getcoors#1#2{%
\def\pst@aftercoors{\addto@pscode{#1 \pst@coors }#2}%
\def\pst@coors{}%
\pst@@getcoors}
\def\pst@@getcoors(#1){%
\pst@@getcoor{#1}%
\edef\pst@coors{\pst@coor\pst@coors}%
\@ifnextchar({\pst@@getcoors}{\pst@aftercoors}}
\def\pst@getangle#1#2{\pst@@getangle{#1}\let#2\pst@angle}
\def\pst@angle{0 }
\def\cartesian@coor#1,#2,#3\@nil{%
\pssetxlength\pst@dimg{#1}%
\pssetylength\pst@dimh{#2}%
\edef\pst@coor{\pst@number\pst@dimg \pst@number\pst@dimh}}
\def\NormalCoor{%
\def\pst@@getcoor##1{\pst@expandafter\cartesian@coor{##1},\relax,\@nil}%
\def\pst@@getangle##1{%
\pst@checknum{##1}\pst@angle
\edef\pst@angle{\pst@angle \pst@angleunit}}%
\def\psput@##1{\pst@@getcoor{##1}\leavevmode\psput@cartesian}}
\NormalCoor
\def\degrees{\@ifnextchar[{\@degrees}{\def\pst@angleunit{}}}
\def\@degrees[#1]{%
\pst@checknum{#1}\pst@tempg
\edef\pst@angleunit{360 \pst@tempg div mul }%
\ignorespaces}
\def\radians{\def\pst@angleunit{57.2956 mul }}
\def\pst@angleunit{}
\def\SpecialCoor{%
\def\pst@@getcoor##1{%
\begingroup
\pst@activecoor
\xdef\pst@tempg{##1}%
\endgroup
\expandafter\special@coor\pst@tempg||\@nil}%
\def\pst@@getangle##1{%
\begingroup
\pst@activecoor
\xdef\pst@tempg{##1}%
\endgroup
\expandafter\special@angle\pst@tempg\@empty)\@nil}%
\def\psput@##1{\pst@@getcoor{##1}\leavevmode\psput@special}}
\begingroup
\catcode`\|=13
\catcode`\;=13
\catcode`\!=13
\gdef\pst@activecoor{%
\def|{\string|}%
\def;{\string;}%
\def!{\string!}}
\endgroup
\def\special@coor#1|#2|#3\@nil{%
\ifx#3|\relax
\mixed@coor{#1}{#2}%
\else
\special@@coor#1;;\@nil
\fi}
\def\special@@coor#1{%
\ifcat#1a\relax
\def\next{\node@coor#1}%
\else
\ifx#1[\relax
\def\next{\Node@coor[}%
\else
\ifx#1!\relax
\def\next{\raw@coor}%
\else
\def\next{\special@@@coor#1}%
\fi
\fi
\fi
\next}
\def\special@@@coor#1;#2;#3\@nil{%
\ifx#3;\relax
\polar@coor{#1}{#2}%
\else
\cartesian@coor#1,\relax,\@nil
\fi}
\def\mixed@coor#1#2{%
\begingroup
\specialcoor@ii#1;;\@nil
\let\pst@tempa\pst@coor
\specialcoor@ii#2;;\@nil
\xdef\pst@tempg{\pst@tempa pop \pst@coor exch pop }%
\endgroup
\let\pst@coor\pst@tempg}
\def\polar@coor#1#2{%
\pssetlength\pst@dimg{#1}%
\pst@@getangle{#2}%
\edef\pst@coor{\pst@number\pst@dimg \pst@angle \tx@PtoC}}
\def\raw@coor#1;#2\@nil{%
\edef\pst@coor{%
#1 \pst@number\psyunit mul exch \pst@number\psxunit mul exch }}
\def\node@coor#1\@nil{%
\@pstrickserr{You must load `pst-node.tex' to use node coordinates.}\@ehps
\def\pst@coor{0 0 }}
\def\Node@coor{\node@coor}
\def\special@angle#1#2)#3\@nil{%
\ifx!#1\relax
\edef\pst@angle{#2 \pst@angleunit}%
\else
\ifx(#1\relax
\pst@@getcoor{#2}%
\edef\pst@angle{\pst@coor exch \tx@Atan}%
\else
\pst@checknum{#1#2}\pst@angle
\edef\pst@angle{\pst@angle \pst@angleunit}%
\fi
\fi}
\def\Cartesian{%
\def\cartesian@coor##1,##2,##3\@nil{%
\pssetxlength\pst@dimg{##1}%
\pssetylength\pst@dimh{##2}%
\edef\pst@coor{\pst@number\pst@dimg \pst@number\pst@dimh}}%
\@ifnextchar({\Cartesian@}{}}
\def\Cartesian@(#1,#2){%
\pssetxlength\psxunit{#1}%
\pssetylength\psyunit{#2}%
\ignorespaces}
\def\Polar{%
\def\psput@cartesian{\psput@special}%
\def\cartesian@coor##1,##2,##3\@nil{\polar@coor{##1}{##2}}}%
\def\psset@origin#1{%
\pst@@getcoor{#1}%
\edef\psk@origin{\pst@coor \tx@NET }}
\def\psk@origin{}
\newif\ifswapaxes
\def\psset@swapaxes#1{%
\@nameuse{@pst#1}%
\if@pst
\def\psk@swapaxes{-90 rotate -1 1 scale }%
\else
\def\psk@swapaxes{}%
\fi}
\psset@swapaxes{false}
\newif\ifshowpoints
\def\psset@showpoints#1{\@nameuse{showpoints#1}}
\psset@showpoints{false}
\let\pst@setrepeatarrowsflag\relax
\def\psset@border#1{%
\pst@getlength{#1}\psk@border
\pst@setrepeatarrowsflag}
\psset@border{0pt}
\def\psset@bordercolor#1{\pst@getcolor{#1}\psbordercolor}
\psset@bordercolor{white}
\newif\ifpsdoubleline
\def\psset@doubleline#1{%
\@nameuse{psdoubleline#1}%
\pst@setrepeatarrowsflag}
\psset@doubleline{false}
\def\psset@doublesep#1{\def\psdoublesep{#1}}
\psset@doublesep{1.25\pslinewidth}
\def\psset@doublecolor#1{\pst@getcolor{#1}\psdoublecolor}
\psset@doublecolor{white}
\newif\ifpsshadow
\def\psset@shadow#1{%
\@nameuse{psshadow#1}%
\pst@setrepeatarrowsflag}
\psset@shadow{false}
\def\psset@shadowsize#1{\pst@getlength{#1}\psk@shadowsize}
\psset@shadowsize{3pt}
\def\psset@shadowangle#1{\pst@getangle{#1}\psk@shadowangle}
\psset@shadowangle{-45}
\def\psset@shadowcolor#1{\pst@getcolor{#1}\psshadowcolor}
\psset@shadowcolor{darkgray}
\def\pst@repeatarrowsflag{\z@}
\def\pst@setrepeatarrowsflag{%
\edef\pst@repeatarrowsflag{%
\ifdim\psk@border\p@>\z@ 1\else\ifpsdoubleline 1\else
\ifpsshadow 1\else \z@\fi\fi\fi}}
\def\psls@none{}
\newdimen\pslinewidth
\def\psset@linewidth#1{\pssetlength\pslinewidth{#1}}
\psset@linewidth{.8pt}
\def\psset@linecolor#1{\pst@getcolor{#1}\pslinecolor}
\psset@linecolor{black}
\def\psls@solid{0 setlinecap stroke }
\def\pst@missing{%
\z@
\@pstrickserr{Missing number or dimension. 0 substituted}\@ehpa}
\def\psset@dash#1{%
\pst@expandafter\psset@@dash{#1} {\pst@missing} {\pst@missing} {}\@nil
\edef\psk@dash{\pst@number\pst@dimg \pst@number\pst@dimh}}
\def\psset@@dash#1 #2 #3\@nil{%
\pssetlength\pst@dimg{#1}%
\pssetlength\pst@dimh{#2}}
\psset@dash{5pt 3pt}
\newif\ifpsdashadjust
\def\psset@dashadjust#1{\@nameuse{psdashadjust#1}}
\psset@dashadjust{true}
\def\psls@dashed{%
\ifpsdashadjust
\psk@dash \pst@linetype\space \tx@DashLine
\else
[ \psk@dash ] 0 setdash stroke
\fi}
\def\tx@DashLine{DashLine }
\def\psset@dotsep#1{\pst@getlength{#1}\psk@dotsep}
\psset@dotsep{3pt}
\def\psls@dotted{%
\ifpsdashadjust
\psk@dotsep \pst@linetype\space \tx@DotLine
\else
[ 0 \psk@dotsep CLW add ] 0 setdash 1 setlinecap stroke
\fi}
\def\tx@DotLine{DotLine }
\def\psset@linestyle#1{%
\@ifundefined{psls@#1}%
{\@pstrickserr{Line style `#1' not defined}\@eha}%
{\edef\pslinestyle{#1}}}
\psset@linestyle{solid}
\def\psfs@none{}
\def\psset@fillcolor#1{\pst@getcolor{#1}\psfillcolor}
\psset@fillcolor{white}
\def\psfs@solid{\pst@fill{\pst@usecolor\psfillcolor fill}}
\def\psset@hatchwidth#1{\pst@getlength{#1}\psk@hatchwidth}
\psset@hatchwidth{.8pt}
\def\psset@hatchsep#1{\pst@getlength{#1}\psk@hatchsep}
\psset@hatchsep{4pt}
\def\psset@hatchcolor#1{\pst@getcolor{#1}\pshatchcolor}
\psset@hatchcolor{black}
\def\psset@hatchangle#1{\pst@getangle{#1}\psk@hatchangle}
\psset@hatchangle{45}
\def\pst@linefill{%
\psk@hatchangle rotate
\psk@hatchwidth SLW
\pst@usecolor\pshatchcolor
\psk@hatchsep \tx@LineFill}
\def\psfs@vlines{\pst@fill\pst@linefill}
\@namedef{psfs@vlines*}{\psfs@solid \psfs@vlines}
\def\psfs@hlines{\pst@fill{90 rotate \pst@linefill}}
\@namedef{psfs@hlines*}{\psfs@solid \psfs@hlines}
\def\psfs@crosshatch{\psfs@vlines \psfs@hlines}
\@namedef{psfs@crosshatch*}{\psfs@solid \psfs@vlines \psfs@hlines}
\def\tx@LineFill{LineFill }
\def\psset@fillstyle#1{%
\edef\pst@tempg{#1}\def\pst@temph{none}%
\ifx\pst@tempg\pst@temph
\let\psk@fillstyle\relax
\else
\@ifundefined{psfs@#1}%
{\@pstrickserr{Undefined fill style: `#1'}\@eha}%
{\edef\psk@fillstyle{\expandafter\noexpand\csname psfs@#1\endcsname}}%
\fi}
\def\psset@addfillstyle#1{%
\@ifundefined{psfs@#1}%
{\@pstrickserr{Undefined fill style: `#1'}\@eha}%
{\edef\psk@fillstyle{%
\expandafter\noexpand\psk@fillstyle
\expandafter\noexpand\csname psfs@#1\endcsname}}}
\psset@fillstyle{none}
\def\psset@arrows#1{%
\begingroup
\pst@activearrows
\xdef\pst@tempg{#1}%
\endgroup
\expandafter\psset@@arrows\pst@tempg\@empty-\@empty\@nil
\if@pst\else
\@pstrickserr{Bad arrows specification: #1}\@ehpa
\fi}
\def\psset@@arrows#1-#2\@empty#3\@nil{%
\@psttrue
\def\next##1,#1-##2,##3\@nil{\def\pst@tempg{##2}}%
\expandafter\next\pst@arrowtable,#1-#1,\@nil
\@ifundefined{psas@\pst@tempg}%
{\@pstfalse\def\psk@arrowA{}}%
{\let\psk@arrowA\pst@tempg}%
\@ifundefined{psas@#2}%
{\@pstfalse\def\psk@arrowB{}}%
{\def\psk@arrowB{#2}}}
\def\psk@arrowA{}
\def\psk@arrowB{}
\def\pst@arrowtable{,<->,<<->>,>-<,>>-<<,(-),[-]}
\begingroup
\catcode`\<=13
\catcode`\>=13
\catcode`\|=13
\gdef\pst@activearrows{\def<{\string<}\def>{\string>}\def|{\string|}}
\endgroup
\def\tx@BeginArrow{BeginArrow }
\def\tx@EndArrow{EndArrow }
\def\psset@arrowscale#1{\pst@getscale{#1}\psk@arrowscale}
\psset@arrowscale{1}
\def\psset@arrowsize#1{%
\pst@expandafter\pst@getdimnum{#1} 0 {} {}\@nil
\edef\psk@arrowsize{\pst@number\pst@dimg \pst@tempg}}
\psset@arrowsize{1.5pt 2}
\def\psset@arrowlength#1{\pst@checknum{#1}\psk@arrowlength}
\psset@arrowlength{1.4}
\def\psset@arrowinset#1{\pst@checknum{#1}\psk@arrowinset}%
\psset@arrowinset{.4}
\def\tx@Arrow{Arrow }
\@namedef{psas@>}{%
false \psk@arrowinset \psk@arrowlength \psk@arrowsize \tx@Arrow}
\@namedef{psas@>>}{%
false \psk@arrowinset \psk@arrowlength \psk@arrowsize \tx@Arrow
0 h T
gsave
newpath
false \psk@arrowinset \psk@arrowlength \psk@arrowsize \tx@Arrow
CP
grestore
CP newpath moveto
2 copy
L
stroke
moveto}
\@namedef{psas@<}{%
true \psk@arrowinset \psk@arrowlength \psk@arrowsize \tx@Arrow}
\@namedef{psas@<<}{%
true \psk@arrowinset \psk@arrowlength \psk@arrowsize \tx@Arrow
CP newpath moveto 0 a neg L stroke 0 h neg T
false \psk@arrowinset \psk@arrowlength \psk@arrowsize \tx@Arrow}
\def\psset@tbarsize#1{%
\pst@expandafter\pst@getdimnum{#1} 0 {} {}\@nil
\edef\psk@tbarsize{\pst@number\pst@dimg \pst@tempg}}
\psset@tbarsize{2pt 5}
\def\tx@Tbar{Tbar }
\@namedef{psas@|}{\psk@tbarsize \tx@Tbar}
\@namedef{psas@|*}{0 CLW -2 div T \psk@tbarsize \tx@Tbar}
\@namedef{psas@>|}{%
\psk@tbarsize \tx@Tbar
0 CLW 2 div T
newpath
false \psk@arrowinset \psk@arrowlength \psk@arrowsize \tx@Arrow}
\@namedef{psas@>|*}{%
0 CLW -2 div T
\psk@tbarsize \tx@Tbar
0 CLW 2 div T
newpath
false \psk@arrowinset \psk@arrowlength \psk@arrowsize \tx@Arrow}
\edef\pst@arrowtable{\pst@arrowtable,|<*->|*,|<->|}
\def\psset@bracketlength#1{\pst@checknum{#1}\psk@bracketlength}
\psset@bracketlength{.15}
\def\tx@Bracket{Bracket }
\@namedef{psas@]}{\psk@bracketlength \psk@tbarsize \tx@Bracket}
\def\psset@rbracketlength#1{\pst@checknum{#1}\psk@rbracketlength}
\psset@rbracketlength{.15}
\def\tx@RoundBracket{RoundBracket }
\@namedef{psas@)}{\psk@rbracketlength \psk@tbarsize \tx@RoundBracket}
\def\psas@c{1 \psas@@c}
\def\psas@cc{0 CLW 2 div T 1 \psas@@c}
\def\psas@C{2 \psas@@c}
\def\psas@@c{%
setlinecap
0 0 moveto
0 CLW 2 div L
stroke
0 0 moveto}
\def\psas@{}
\psset@arrows{-}
\def\tx@SD{SD }
\def\tx@EndDot{EndDot }
\def\psas@oo{{\pst@usecolor\psfillcolor true} true \psk@dotsize \tx@EndDot}
\def\psas@o{{\pst@usecolor\psfillcolor true} false \psk@dotsize \tx@EndDot}
\@namedef{psas@**}{{false} true \psk@dotsize \tx@EndDot}
\@namedef{psas@*}{{false} false \psk@dotsize \tx@EndDot}
\def\pst@par{}
\def\addto@par#1{%
\ifx\pst@par\@empty
\def\pst@par{#1}%
\else
\expandafter\def\expandafter\pst@par\expandafter{\pst@par,#1}%
\fi}
\def\addbefore@par#1{%
\ifx\pst@par\@empty
\def\pst@par{#1}%
\else
\toks@{#1}%
\pst@toks\expandafter{\pst@par}%
\edef\pst@par{\the\toks@,\the\pst@toks}%
\fi}
\def\use@par{%
\ifx\pst@par\@empty\else
\expandafter\@psset\pst@par,\@nil
\def\pst@par{}%
\fi}
\def\pst@object#1{%
\pst@ifstar{%
\@ifnextchar[%
{\pst@@object{#1}}%
{\def\pst@par{}\@nameuse{#1@i}}}}
\def\pst@@object#1[#2]{%
\def\pst@par{#2}%
\@ifnextchar+{\@nameuse{#1@i}}{\@nameuse{#1@i}}}
\def\newpsobject#1#2#3{%
\@ifundefined{#2@i}%
{\@pstrickserr{Graphics object `#2' not defined}\@eha}{%
\@namedef{#1}{\pst@object{#1}}%
\@namedef{#1@i}{\addbefore@par{#3}\@nameuse{#2@i}}}%
\ignorespaces}
\def\pst@getarrows#1{\@ifnextchar({#1}{\pst@@getarrows{#1}}}
\def\pst@@getarrows#1#2{\addto@par{arrows=#2}#1}
\def\begin@ClosedObj{%
\leavevmode
\pst@killglue
\begingroup
\use@par
\solid@star
\ifpsdoubleline \pst@setdoublesep \fi
\init@pscode}
\def\end@ClosedObj{%
\ifpsshadow \pst@closedshadow \fi
\ifdim\psk@border\p@>\z@ \pst@addborder \fi
\psk@fillstyle
\pst@stroke
\ifpsdoubleline \pst@doublestroke \fi
\ifshowpoints
% Modification Denis GIROU (CNRS/IDRIS - France) - &lt;Denis.Girou@idris.fr&gt; -  4 Mar. 1995
%\addto@pscode{Points aload length 2 div cvi /N ED \psdots@iii}%
\pst@OpenShowPoints
% End modification D.G.
\fi
\use@pscode
\endgroup
\ignorespaces}
\def\begin@OpenObj{%
\begin@ClosedObj
\let\pst@linetype\pst@arrowtype
\pst@addarrowdef}
\def\begin@AltOpenObj{%
\begin@ClosedObj
\def\pst@repeatarrowsflag{\z@}%
\def\pst@linetype{0}}
\def\end@OpenObj{%
\ifpsshadow \pst@openshadow \fi
\ifdim\psk@border\p@>\z@ \pst@addborder \fi
\psk@fillstyle
\pst@stroke
\ifpsdoubleline \pst@doublestroke \fi
\ifnum\pst@repeatarrowsflag>\z@ \pst@repeatarrows \fi
\ifshowpoints \pst@OpenShowPoints \fi
\use@pscode
\endgroup
\ignorespaces}
\def\begin@SpecialObj{%
\leavevmode
\pst@killglue
\begingroup
\use@par
\init@pscode}
\def\end@SpecialObj{%
\use@pscode
\endgroup
\ignorespaces}
\def\pst@code{}%
\def\init@pscode{%
\addto@pscode{%
\pst@number\pslinewidth SLW
\pst@usecolor\pslinecolor}}
\def\addto@pscode#1{\xdef\pst@code{\pst@code#1\space}}
\def\use@pscode{%
\pstverb{%
\pst@dict
\tx@STP
\pst@newpath
\psk@origin
\psk@swapaxes
\pst@code
end}%
\gdef\pst@code{}}
\def\pst@newpath{newpath }
\def\pst@@killglue{\unskip\ifdim\lastskip>\z@\expandafter\pst@@killglue\fi}
\def\KillGlue{\let\pst@killglue\pst@@killglue}
\def\DontKillGlue{\let\pst@killglue\relax}
\DontKillGlue
\def\solid@star{%
\if@star
\pslinewidth=\z@
\psdoublelinefalse
\def\pslinestyle{none}%
\def\psk@fillstyle{\psfs@solid}%
\let\psfillcolor\pslinecolor
\fi}
\def\pst@setdoublesep{%
\pst@getlength\psdoublesep\psdoublesep
\pslinewidth=2\pslinewidth
\advance\pslinewidth\psdoublesep\p@
\let\pst@setdoublesep\relax}
\def\tx@Shadow{Shadow }
\def\pst@closedshadow{%
\addto@pscode{%
gsave
\psk@shadowsize \psk@shadowangle \tx@PtoC
\tx@Shadow
\pst@usecolor\psshadowcolor
gsave fill grestore
stroke
grestore
gsave
\pst@usecolor\psfillcolor
gsave fill grestore
stroke
grestore}}
\def\pst@openshadow{%
\addto@pscode{%
gsave
\psk@shadowsize \psk@shadowangle \tx@PtoC
\tx@Shadow
\pst@usecolor\psshadowcolor
\ifx\psk@fillstyle\relax\else
gsave fill grestore
\fi
stroke}%
\pst@repeatarrows
\addto@pscode{grestore}
\ifx\psk@fillstyle\relax\else
\addto@pscode{%
gsave
\pst@usecolor\psfillcolor
gsave fill grestore
stroke
grestore}
\fi}
\def\pst@addborder{%
\addto@pscode{%
gsave
\psk@border 2 mul
CLW add SLW
\pst@usecolor\psbordercolor
stroke
grestore}}
\def\pst@stroke{%
\ifx\pslinestyle\@none\else
\addto@pscode{%
gsave
\pst@number\pslinewidth SLW
\pst@usecolor\pslinecolor
\@nameuse{psls@\pslinestyle}
grestore}%
\fi}
\def\pst@fill#1{\addto@pscode{gsave #1 grestore}}%
\def\pst@doublestroke{%
\addto@pscode{%
gsave
\psdoublesep SLW
\pst@usecolor\psdoublecolor
stroke
grestore}}
\def\pst@arrowtype{%
\ifx\psk@arrowB\@empty 0 \else -2 \fi
\ifx\psk@arrowA\@empty 0 \else -1 \fi
add}
\def\pst@addarrowdef{%
\addto@pscode{%
/ArrowA {
\ifx\psk@arrowA\@empty
\pst@oplineto
\else
\pst@arrowdef{A}
moveto
\fi
} def
/ArrowB {
\ifx\psk@arrowB\@empty \else \pst@arrowdef{B} \fi
} def}}
\def\pst@arrowdef#1{%
\ifnum\pst@repeatarrowsflag>\z@
/Arrow#1c [ 6 2 roll ] cvx def Arrow#1c
\fi
\tx@BeginArrow
\psk@arrowscale
\@nameuse{psas@\@nameuse{psk@arrow#1}}
\tx@EndArrow}
\def\pst@repeatarrows{%
\addto@pscode{%
gsave
\ifx\psk@arrowA\@empty\else
ArrowAc ArrowA pop pop
\fi
\ifx\psk@arrowB\@empty\else
ArrowBc ArrowB pop pop pop pop
\fi
grestore}}
\def\pst@OpenShowPoints{%
\addto@pscode{%
gsave
\psk@dotsize
\@nameuse{psds@\psk@dotstyle}
newpath
Points aload length 2 div 2 sub cvi /N ED
N 0 ge
{ \ifx\psk@arrowA\@empty
Dot
\else
pop pop
\fi
N { Dot } repeat
\ifx\psk@arrowB\@empty
Dot
\else
pop pop
\fi }
{ N 2 mul { pop } repeat }
ifelse
grestore}}
\def\pscustom{\pst@object{pscustom}}
\long\def\pscustom@i#1{%
\begin@SpecialObj
\solid@star
\let\pst@ifcustom\iftrue
\let\begin@ClosedObj\begin@CustomObj
\let\end@ClosedObj\endgroup
\def\begin@OpenObj{\begin@CustomObj\pst@addarrowdef}%
\let\end@OpenObj\endgroup
\let\begin@AltOpenObj\begin@CustomObj
\def\begin@SpecialObj{%
\begingroup
\pst@misplaced{special graphics object}%
\def\addto@pscode####1{}
\let\end@SpecialObj\endgroup}%
\def\@multips(##1)(##2)##3##4{\pst@misplaced\multips}%
\def\psclip##1{\pst@misplaced\psclip}%
\def\pst@repeatarrowsflag{\z@}%
\let\pst@setrepeatarrowsflag\relax
\showpointsfalse
\let\showpointstrue\relax
\def\pst@linetype{\pslinetype}%
\let\psset@liftpen\psset@@liftpen
\psset@liftpen{\z@}%
\def\pst@cp{/currentpoint load stopped pop }%
\def\pst@oplineto{/lineto load stopped { moveto } if }%
\def\pst@optcp##1##2{%
\ifnum##1=\z@\def##2{/currentpoint load stopped { 0 0 } if }\fi}%
\let\caddto@pscode\addto@pscode
\def\cuse@par##1{{\use@par##1}}%
\the\pst@customdefs
\setbox\pst@hbox=\hbox{#1}%
\psk@fillstyle
\pst@stroke
\end@SpecialObj}
\def\begin@CustomObj{%
\begingroup
\use@par
\addto@pscode{%
\pst@number\pslinewidth SLW
\pst@usecolor\pslinecolor}}
\def\pst@oplineto{moveto }
\def\pst@cp{}
\def\pst@optcp#1#2{}
\def\psset@liftpen#1{}
\def\psset@@liftpen#1{%
\ifcase#1\relax
\def\psk@liftpen{\z@}%
\def\pst@cp{/currentpoint load stopped pop }%
\def\pst@oplineto{/lineto load stopped { moveto } if }%
\or
\def\psk@liftpen{1}%
\def\pst@cp{}%
\def\pst@oplineto{/lineto load stopped { moveto } if }%
\or
\def\psk@liftpen{2}%
\def\pst@cp{}%
\def\pst@oplineto{moveto }%
\fi}
\psset@liftpen{0}
\def\psk@liftpen{-1}
\def\psset@linetype#1{%
\pst@getint{#1}\pslinetype
\ifnum\pst@dimg<-3
\@pstrickserr{linetype must be greater than -3}\@ehpa
\def\pslinetype{0}%
\fi}
\psset@linetype{0}
\def\caddto@pscode#1{%
\@pstrickserr{Command can only be used in \string\pscustom}\@ehpa}
\let\cuse@par\caddto@pscode
\def\tx@MSave{%
/msavemtrx
[ tx@Dict /msavemtrx known { msavemtrx aload pop } if CM ]
def }
\def\tx@MRestore{%
tx@Dict /msavemtrx known { length 0 gt } { false } ifelse
{ /msavematrx [ msavematrx aload pop setmatrix ] def }
if }
\newtoks\pst@customdefs
\pst@customdefs{%
\def\newpath{\addto@pscode{newpath}}%
\def\moveto(#1){\pst@@getcoor{#1}\addto@pscode{\pst@coor moveto}}%
\def\closepath{\addto@pscode{closepath}}%
\def\gsave{\begingroup\addto@pscode{gsave}}%
\def\grestore{\endgroup\addto@pscode{grestore}}%
% DG/SR modification begin - May 12, 1997
%\def\translate(#1){\pst@@getcoor{#1}\addto@pscode{\pst@coor moveto}}%
\def\translate(#1){\pst@@getcoor{#1}\addto@pscode{\pst@coor translate}}%
% DG/SR modification end
\def\rotate#1{\pst@@getangle{#1}\addto@pscode{\pst@angle rotate}}%
\def\scale#1{\pst@getscale{#1}\pst@tempg\addto@pscode{\pst@tempg}}%
\def\msave{\addto@pscode{\tx@MSave}}%
\def\mrestore{\addto@pscode{\tx@MRestore}}%
\def\swapaxes{\addto@pscode{-90 rotate -1 1 scale}}%
\def\stroke{\pst@object{stroke}}%
\def\fill{\pst@object{fill}}%
\def\openshadow{\pst@object{openshadow}}%
\def\closedshadow{\pst@object{closedshadow}}%
\def\movepath(#1){\pst@@getcoor{#1}\addto@pscode{\pst@coor tx@Shadow}}%
\def\lineto{\pst@onecoor{lineto}}%
\def\rlineto{\pst@onecoor{rlineto}}%
\def\curveto{\pst@threecoor{curveto}}%
\def\rcurveto{\pst@threecoor{rcurveto}}%
\def\code#1{\addto@pscode{#1}}%
\def\coor(#1){\pst@@getcoor{#1}\addto@pscode\pst@coor\@ifnextchar({\coor}{}}%
\def\rcoor{\pst@getcoors{}{}}%
\def\dim#1{\pssetlength\pst@dimg{#1}\addto@pscode{\pst@number\pst@dimg}}%
\def\setcolor#1{%
\@ifundefined{color@#1}{}{\addto@pscode{\use@color{#1}}}}%
\def\arrows#1{{\psset@arrows{#1}\pst@addarrowdef}}%
\let\file\pst@rawfile
} % END \pst@customdefs
\def\closedshadow@i{\cuse@par\pst@closedshadow}
\def\openshadow@i{\cuse@par\pst@openshadow}
\def\stroke@i{\cuse@par\pst@stroke}%
\def\fill@i{\cuse@par\psk@fillstyle}%
\def\pst@onecoor#1(#2){%
\pst@@getcoor{#2}%
\addto@pscode{\pst@coor #1}}
\def\pst@threecoor#1(#2)#3(#4)#5(#6){%
\begingroup
\pst@getcoor{#2}\pst@tempa
\pst@getcoor{#4}\pst@tempb
\pst@getcoor{#6}\pst@tembc
\addto@pscode{\pst@tempa \pst@tempb \pst@tempc #1}%
\endgroup}
\def\pst@rawfile#1{%
\begingroup
\def\do##1{\catcode`##1=12\relax}"
\dospecials
\catcode`\%=14
\pst@@rawfile{#1}%
\endgroup}
\def\pst@@rawfile#1{%
\immediate\openin1 #1
\ifeof1
\@pstrickserr{File `#1' not found}\@ehpa
\else
\immediate\read1 to \pst@tempg
\loop
\ifeof1 \@pstfalse\else\@psttrue\fi
\if@pst
\addto@pscode\pst@tempg
\immediate\read1 to \pst@tempg
\repeat
\fi
\immediate\closein1\relax}
\def\tx@NArray{NArray }
\def\tx@NArray{NArray }
\def\tx@Line{Line }
\def\tx@Arcto{Arcto }
\def\tx@CheckClosed{CheckClosed }
\def\tx@Polygon{Polygon }
\def\psset@gangle#1{\pst@getangle{#1}\psk@gangle}
\psset@gangle{0}
\def\tx@Diamond{Diamond }
\def\psdiamond{\pst@object{psdiamond}}
\def\psdiamond@i(#1){%
\@ifnextchar({\psdiamond@ii(#1)}{\psdiamond@ii(0,0)(#1)}}
\def\psdiamond@ii(#1)(#2){%
\begin@ClosedObj
\pst@getcoor{#1}\pst@tempa
\pst@getcoor{#2}\pst@tempb
\addto@pscode{%
\psline@iii
pop
\psk@dimen
\pst@tempb
\psk@gangle
\pst@tempa
\tx@Diamond}%
\def\pst@linetype{4}%
\end@ClosedObj}
\def\tx@Triangle{Triangle }
\def\pstriangle{\pst@object{pstriangle}}
\def\pstriangle@i(#1){%
\@ifnextchar({\pstriangle@ii(#1)}{\pstriangle@ii(0,0)(#1)}}
\def\pstriangle@ii(#1)(#2){%
\begin@ClosedObj
\pst@getcoor{#1}\pst@tempa
\pst@getcoor{#2}\pst@tempb
\addto@pscode{%
\psline@iii
pop
\psk@dimen
\pst@tempb
\psk@gangle
\pst@tempa
\tx@Triangle}%
\def\pst@linetype{2}%
\end@ClosedObj}
\def\tx@CCA{CCA }
\def\tx@CCA{CCA }
\def\tx@CC{CC }
\def\tx@IC{IC }
\def\tx@BOC{BOC }
\def\tx@NC{NC }
\def\tx@EOC{EOC }
\def\tx@BAC{BAC }
\def\tx@NAC{NAC }
\def\tx@EAC{EAC }
\def\tx@OpenCurve{OpenCurve }
\def\tx@AltCurve{AltCurve }
\def\tx@ClosedCurve{ClosedCurve }
\def\psset@curvature#1{%
\edef\pst@tempg{#1 }%
\expandafter\psset@@curvature\pst@tempg * * * \@nil}
\def\psset@@curvature#1 #2 #3 #4\@nil{%
\pst@checknum{#1}\pst@tempg
\pst@checknum{#2}\pst@temph
\pst@checknum{#3}\pst@tempi
\edef\psk@curvature{\pst@tempg \pst@temph \pst@tempi}}
\psset@curvature{1 .1 0}
\def\pscurve{\pst@object{pscurve}}
\def\pscurve@i{%
\pst@getarrows{%
\begin@OpenObj
\pst@getcoors[\pscurve@ii}}
\def\pscurve@ii{%
\addto@pscode{%
\pst@cp
\psk@curvature\space /c ED /b ED /a ED
\ifshowpoints true \else false \fi
\tx@OpenCurve}%
\end@OpenObj}
\def\psecurve{\pst@object{psecurve}}
\def\psecurve@i{%
\pst@getarrows{%
\begin@OpenObj
\pst@getcoors[\psecurve@ii}}
\def\psecurve@ii{%
\addto@pscode{%
\psk@curvature\space /c ED /b ED /a ED
\ifshowpoints true \else false \fi
\tx@AltCurve}%
\end@OpenObj}
\def\psccurve{\pst@object{psccurve}}
\def\psccurve@i{%
\begin@ClosedObj
\pst@getcoors[\psccurve@ii}
\def\psccurve@ii{%
\addto@pscode{%
\psk@curvature\space /c ED /b ED /a ED
\ifshowpoints true \else false \fi
\tx@ClosedCurve}%
\def\pst@linetype{1}%
\end@ClosedObj}
\def\psset@dotsize#1{%
\pst@expandafter\pst@getdimnum{#1} 0 {} {}\@nil
\edef\psk@@dotsize{\pst@number\pst@dimg}%
\let\psk@@@dotsize\pst@tempg
\edef\psk@dotsize{%
/DS \psk@@dotsize \psk@@@dotsize CLW mul add 2 div def }}
\psset@dotsize{2pt 2}
\def\psset@dotscale#1{%
\pst@getscale{#1}\psk@dotscale
\ifx\psk@dotscale\@empty
\def\psk@xdotscale{1 }%
\def\psk@ydotscale{1 }%
\else
\let\psk@xdotscale\pst@tempg
\let\psk@ydotscale\pst@temph
\fi}
\psset@dotscale{1}
\def\pst@Getangle#1#2{%
\pst@getangle{#1}\pst@tempg
\def\pst@temph{0. }%
\ifx\pst@tempg\pst@temph
\def#2{}%
\else
\edef#2{\pst@tempg\space rotate }%
\fi}
\def\psset@dotangle#1{%
\pst@getangle{#1}\psk@@dotangle
\ifdim\psk@@dotangle\p@=\z@
\let\psk@dotangle\@empty
\else
\edef\psk@dotangle{\psk@@dotangle rotate }
\fi}
\psset@dotangle{0}
\def\pst@getdotsize{%
\pst@dimg=\psk@@@dotsize\pslinewidth
\advance\pst@dimg\psk@@dotsize\p@
\pst@dimh=\psk@ydotscale\pst@dimg
\pst@dimg=\psk@xdotscale\pst@dimg
\divide\pst@dimh 2
\divide\pst@dimg 2\relax}
\def\psdot{\pst@object{psdot}}
\def\psdot@i{\@ifnextchar({\psdot@ii}{\psdot@ii(\z@,\z@)}}
\def\psdot@ii(#1){%
\begin@SpecialObj
\pst@@getcoor{#1}%
\addto@pscode{%
\psk@dotsize
\@nameuse{psds@\psk@dotstyle}%
\pst@coor Dot}%
\end@SpecialObj}
\def\psdots{\pst@object{psdots}}
\def\psdots@i{%
\begin@SpecialObj
\pst@getcoors[\psdots@ii}
\def\psdots@ii{%
\addto@pscode{false \tx@NArray \psdots@iii}%
\end@SpecialObj}
\def\psdots@iii{%
\psk@dotsize
\@nameuse{psds@\psk@dotstyle}
newpath
n { transform floor .5 add exch floor .5 add exch itransform Dot } repeat}
\def\tx@SQ{SQ }
\def\tx@ST{ST }
\def\tx@SP{SP }
\def\pst@gdot#1{/Dot { gsave T \psk@dotangle \psk@dotscale #1 grestore } def }
\@namedef{psds@*}{\pst@gdot{0 0 DS \tx@SD}}
\@namedef{psds@o}{%
/r2 DS CLW sub def
\pst@gdot{0 0 DS \tx@SD \pst@usecolor\psfillcolor 0 0 r2 \tx@SD}}
\@namedef{psds@square*}{%
/r1 DS .886 mul def
\pst@gdot{r1 \tx@SQ}}
\@namedef{psds@square}{%
/r1 DS .886 mul def /r2 r1 CLW sub def
\pst@gdot{r1 \tx@SQ \pst@usecolor\psfillcolor r2 \tx@SQ}}
\@namedef{psds@triangle*}{%
/y1 DS .778 mul neg def /x1 y1 1.732 mul neg def
\pst@gdot{x1 y1 \tx@ST}}
\@namedef{psds@triangle}{%
/y1 DS .778 mul neg def /x1 y1 1.732 mul neg def
/y2 y1 CLW add def /x2 y2 1.732 mul neg def
\pst@gdot{x1 y1 \tx@ST \pst@usecolor\psfillcolor x2 y2 \tx@ST}}
\@namedef{psds@pentagon*}{%
/r1 DS 1.149 mul def
\pst@gdot{r1 \tx@SP}}
\@namedef{psds@pentagon}{%
DS .93 mul dup 1.236 mul /r1 ED CLW sub 1.236 mul /r2 ED
\pst@gdot{r1 \tx@SP \pst@usecolor\psfillcolor r2 \tx@SP}}
\@namedef{psds@+}{%
/DS DS 1.253 mul def
\pst@gdot{DS 0 moveto DS neg 0 L stroke 0 DS moveto 0 DS neg L stroke}}
\@namedef{psds@|}{%
\psk@tbarsize CLW mul add 2 div /DS ED
\pst@gdot{0 DS moveto 0 DS neg L stroke}}
\def\psset@dotstyle#1{%
\@ifundefined{psds@#1}%
{\@pstrickserr{Dot style `#1' not defined}\@eha}%
{\edef\psk@dotstyle{#1}}}
\psset@dotstyle{*}
\def\tx@FontDot{FontDot }
\def\newpsfontdot#1[#2]#3#4{%
\@namedef{psds@#1}{%
/#3 \psk@@dotangle [#2] \tx@FontDot
% DG/SR modification begin - July 9, 1997
%/Dot { moveto #4 show } bind def }}
/Dot { moveto #4 \psk@dotscale show } bind def }}
% DG/SR modification end
\def\newpsfontdotH#1[#2]#3#4#5{%
\@namedef{psds@#1}{%
/#3 \psk@@dotangle [#2] \tx@FontDot
/Dot {
moveto
\iftrue
gsave \pst@usecolor\psfillcolor #5 show grestore
\fi
% DG/SR modification begin - July 9, 1997
%#4 show
#4 \psk@dotscale show
% DG/SR modification end
} bind def }}
\pstheader{pst-dots.pro}
\newpsfontdot{*}%
[1.0 0.0 0.0 1.0 0.0 0.0]{PSTricksDotFont}{(b)}
\newpsfontdotH{o}%
[1.0 0.0 0.0 1.0 0.0 0.0]{PSTricksDotFont}{(c)}{(b)}
\newpsfontdotH{Bo}%
[1.0 0.0 0.0 1.0 0.0 0.0]{PSTricksDotFont}{(C)}{(b)}
\newpsfontdotH{triangle}%
[1.0 0.0 0.0 1.0 0.0 0.0]{PSTricksDotFont}{(t)}{(u)}
\newpsfontdotH{Btriangle}%
[1.0 0.0 0.0 1.0 0.0 0.0]{PSTricksDotFont}{(T)}{(u)}
\newpsfontdot{triangle*}%
[1.0 0.0 0.0 1.0 0.0 0.0]{PSTricksDotFont}{(u)}
\newpsfontdotH{square}%
[1.0 0.0 0.0 1.0 0.0 0.0]{PSTricksDotFont}{(s)}{(r)}
\newpsfontdotH{Bsquare}%
[1.0 0.0 0.0 1.0 0.0 0.0]{PSTricksDotFont}{(S)}{(r)}
\newpsfontdot{square*}%
[1.0 0.0 0.0 1.0 0.0 0.0]{PSTricksDotFont}{(r)}
\newpsfontdotH{pentagon}%
[1.0 0.0 0.0 1.0 0.0 0.0]{PSTricksDotFont}{(p)}{(q)}
\newpsfontdotH{Bpentagon}%
[1.0 0.0 0.0 1.0 0.0 0.0]{PSTricksDotFont}{(P)}{(q)}
\newpsfontdot{pentagon*}%
[1.0 0.0 0.0 1.0 0.0 0.0]{PSTricksDotFont}{(q)}
% Modification Denis GIROU (CNRS/IDRIS - France) <Denis.Girou@idris.fr> - 18 Mar. 1997
%\newpsfontdot{diamond*}%
%[1.9 0.0 0.0 1.9 -0.4598 -0.70775]{Symbol}{<E0>}
%\newpsfontdot{diamond}%
%[2.3 0.0 0.0 2.3 -0.8533 -0.5336]{Symbol}{<A8>}
\newpsfontdot{diamond}%
[1.9 0.0 0.0 1.9 -0.4598 -0.70775]{Symbol}{<E0>}
\newpsfontdot{diamond*}%
[2.3 0.0 0.0 2.3 -0.8533 -0.5336]{Symbol}{<A8>}
\newpsfontdot{oplus}%
[1.44928 0.0 0.0 1.44928 -0.562319 -0.478261]{Symbol}{<C5>}
\newpsfontdot{otimes}%
[1.44928 0.0 0.0 1.44928 -0.562319 -0.475362]{Symbol}{<C4>}
\newpsfontdot{x}%
[1.8 0.0 0.0 1.8 -0.495 -0.4788]{Symbol}{<B4>}
\newpsfontdot{+}%
[2.3 0.0 0.0 2.3 -0.6486 -0.5819]{Times-Roman}{<2B>}
\newpsfontdot{asterisk}%
[2.43309 0.0 0.0 2.43309 -0.609489 -1.14477]{Times-Roman}{<2A>}
\newpsfontdot{B+}%
[2.3 0.0 0.0 2.3 -0.6555 -0.5819]{Times-Bold}{<2B>}
\newpsfontdot{Basterisk}%
[2.29358 0.0 0.0 2.29358 -0.576835 -1.08486]{Times-Bold}{<2A>}
\newpsfontdot{|}%
[1.98413 0.0 0.0 1.98413 -0.258929 -0.712302]{Helvetica}{(|)}
\newpsfontdot{B|}%
[1.98413 0.0 0.0 1.98413 -0.277778 -0.712302]{Helvetica-Bold}{(|)}
\iffalse
\newpsfontdot{*}%
[2.77778 0.0 0.0 2.77778 -0.638889 -0.813889]{Symbol}{<B7>}
\newpsfontdot{o}%
[3.33333 0.0 0.0 3.33333 -0.666667 -1.78167]{Symbol}{<B0>}
\newpsfontdot{Bo}%
[4.69484 0.0 0.0 4.69484 -0.78169 -2.97418]{Times-Bold}{<CA>}
\fi
\newdimen\pslinearc
\def\psset@linearc#1{\pssetlength\pslinearc{#1}}
\psset@linearc{0pt}
\def\psline{\pst@object{psline}}
\def\psline@i{%
\pst@getarrows{%
\begin@OpenObj
\pst@getcoors[\psline@ii}}
\def\psline@ii{%
\addto@pscode{\pst@cp \psline@iii \tx@Line}%
\end@OpenObj}
\def\psline@iii{%
\ifdim\pslinearc>\z@
/r \pst@number\pslinearc def
/Lineto { \tx@Arcto } def
\else
/Lineto /lineto load def
\fi
\ifshowpoints true \else false \fi}
\def\qline(#1)(#2){%
\def\pst@par{}%
\begin@SpecialObj
\def\pst@linetype{0}%
\pst@getcoor{#1}\pst@tempa
\pst@@getcoor{#2}%
\addto@pscode{%
\pst@tempa moveto \pst@coor L
\@nameuse{psls@\pslinestyle}}%
\end@SpecialObj}
\def\pspolygon{\pst@object{pspolygon}}
\def\pspolygon@i{%
\begin@ClosedObj
\def\pst@cp{}%
\pst@getcoors[\pspolygon@ii}
\def\pspolygon@ii{%
\addto@pscode{\psline@iii \tx@Polygon}%
\def\pst@linetype{1}%
\end@ClosedObj}
\def\psset@framearc#1{\pst@checknum{#1}\psk@framearc}
\psset@framearc{0}
\def\psset@cornersize#1{%
\pst@expandafter\psset@@cornersize{#1}\@nil}
\def\psset@@cornersize#1#2\@nil{%
\if #1a\relax
\def\psk@cornersize{\pst@number\pslinearc false }%
\else
\def\psk@cornersize{\psk@framearc true }%
\fi}
\psset@cornersize{relative}
\def\tx@Rect{Rect }
\def\tx@OvalFrame{OvalFrame }
\def\tx@Frame{Frame }
\def\psset@dimen#1{%
\pst@expandafter\psset@@dimen{#1}\@nil}
\def\psset@@dimen#1#2\@nil{%
\if #1o\relax
\def\psk@dimen{.5 }%
\else
\if #1m\relax
\def\psk@dimen{0 }%
\else
\if #1i\relax
\def\psk@dimen{-.5 }%
\fi
\fi
\fi}
\psset@dimen{outer}
\def\psframe{\pst@object{psframe}}
\def\psframe@i(#1){%
\@ifnextchar({\psframe@ii(#1)}{\psframe@ii(0,0)(#1)}}
\def\psframe@ii(#1)(#2){%
\begin@ClosedObj
\pst@getcoor{#1}\pst@tempa
\pst@@getcoor{#2}%
\addto@pscode{\psk@cornersize \pst@tempa \pst@coor \psk@dimen \tx@Frame}%
\def\pst@linetype{2}%
\showpointsfalse
\end@ClosedObj}
\def\tx@BezierNArray{BezierNArray }
\def\tx@OpenBezier{OpenBezier }
\def\tx@ClosedBezier{ClosedBezier }
\def\tx@BezierShowPoints{BezierShowPoints }
\def\psbezier{\pst@object{psbezier}}
\def\psbezier@i{%
\pst@getarrows{%
\begin@OpenObj
\pst@getcoors[\psbezier@ii}}
\def\psbezier@ii{%
\addto@pscode{%
% Modification DG/SR - 28 April 1997 (Pb. inside \pscustom)
%\pst@cp
% Modification DG/SR - end
\ifshowpoints true \else false \fi
\tx@OpenBezier
\ifshowpoints \tx@BezierShowPoints \fi}%
\end@OpenObj}
\def\pscbezier{\pst@object{pscbezier}}
\def\pscbezier@i{%
\begin@ClosedObj
\pst@getcoors[\pscbezier@ii}
\def\pscbezier@ii{%
\addto@pscode{%
\ifshowpoints true \else false \fi
\tx@ClosedBezier
\ifshowpoints \tx@BezierShowPoints \fi}%
\chardef\pst@linetype=1
\end@ClosedObj}
\def\tx@Parab{Parab }
\def\parabola{\pst@object{parabola}}
\def\parabola@i{\pst@getarrows\parabola@ii}
\def\parabola@ii#1(#2)#3(#4){%
\begin@OpenObj
\pst@getcoor{#2}\pst@tempa
\pst@@getcoor{#4}%
\addto@pscode{\pst@tempa \pst@coor \tx@Parab}%
\end@OpenObj}
\def\psset@gridwidth#1{\pst@getlength{#1}\psk@gridwidth}
\psset@gridwidth{.8pt}
\def\psset@griddots#1{%
\pst@cntg=#1\relax
\edef\psk@griddots{\the\pst@cntg}}
\psset@griddots{0}
\def\psset@gridcolor#1{\pst@getcolor{#1}\psgridcolor}
\psset@gridcolor{black}
\def\psset@subgridwidth#1{\pst@getlength{#1}\psk@subgridwidth}
\psset@subgridwidth{.4pt}
\def\psset@subgridcolor#1{\pst@getcolor{#1}\pssubgridcolor}
\psset@subgridcolor{gray}
\def\psset@subgriddots#1{%
\pst@cntg=#1\relax\edef\psk@subgriddots{\the\pst@cntg}}
\psset@subgriddots{0}
\def\psset@subgriddiv#1{%
\pst@cntg=#1\relax\edef\psk@subgriddiv{\the\pst@cntg}}
\psset@subgriddiv{5}
\def\psset@gridlabels#1{\pst@getlength{#1}\psk@gridlabels}
\psset@gridlabels{10pt}
\def\psset@gridlabelcolor#1{\pst@getcolor{#1}\psgridlabelcolor}
\psset@gridlabelcolor{black}
\def\tx@Grid{Grid }
\def\psgrid{\pst@object{psgrid}}
\def\psgrid@i{\@ifnextchar(%
{\psgrid@ii}{\expandafter\psgrid@iv\pic@coor}}
\def\psgrid@ii(#1){\@ifnextchar(%
{\psgrid@iii(#1)}{\psgrid@iv(0,0)(0,0)(#1)}}
\def\psgrid@iii(#1)(#2){\@ifnextchar(%
{\psgrid@iv(#1)(#2)}{\psgrid@iv(#1)(#1)(#2)}}
\def\psgrid@iv(#1)(#2)(#3){%
\begin@SpecialObj
\pst@getcoor{#1}\pst@tempa
\pst@getcoor{#2}\pst@tempb
\pst@@getcoor{#3}%
\ifnum\psk@subgriddiv>1
\addto@pscode{gsave
\psk@subgridwidth SLW \pst@usecolor\pssubgridcolor
\pst@tempb \pst@coor \pst@tempa
\pst@number\psxunit \pst@number\psyunit
\psk@subgriddiv\space \psk@subgriddots\space
{} 0 \tx@Grid grestore}%
\fi
\addto@pscode{gsave
\psk@gridwidth SLW \pst@usecolor\psgridcolor
\pst@tempb \pst@coor \pst@tempa
\pst@number\psxunit \pst@number\psyunit
1 \psk@griddots\space { \pst@usecolor\psgridlabelcolor }
\psk@gridlabels \tx@Grid grestore}%
\end@SpecialObj}
\newif\ifpsmathbox
\psmathboxtrue
\def\pst@mathflag{\z@}
\newtoks\everypsbox
\let\pst@thisbox\relax
\long\def\pst@makenotverbbox#1#2{%
\edef\pst@mathflag{%
\ifpsmathbox\ifmmode\ifinner 1\else 2\fi\else \z@\fi\else \z@\fi}%
\setbox\pst@hbox=\hbox{%
\ifcase\pst@mathflag\or$\m@th\textstyle\or$\m@th\displaystyle\fi
{\pst@thisbox\the\everypsbox#2}%
\ifnum\pst@mathflag>\z@$\fi}%
#1}
\def\pst@makeverbbox#1{%
\def\pst@afterbox{#1}%
\edef\pst@mathflag{%
\ifpsmathbox\ifmmode\ifinner 1\else 2\fi\else \z@\fi\else \z@\fi}%
\afterassignment\pst@beginbox
\setbox\pst@hbox\hbox}
\def\pst@beginbox{%
\ifcase\pst@mathflag\or$\m@th\or$\m@th\displaystyle\fi
\bgroup\aftergroup\pst@endbox
\pst@thisbox
\the\everypsbox}
\def\pst@endbox{%
\ifnum\pst@mathflag>\z@$\fi
\egroup
\pst@afterbox}
\def\pst@makebox{\pst@@makebox}
\def\psverbboxtrue{\def\pst@@makebox{\pst@makeverbbox}}
\def\psverbboxfalse{\def\pst@@makebox{\pst@makenotverbbox}}
\psverbboxfalse
\def\pst@longbox{%
\def\pst@makebox{%
\gdef\pst@makebox{\pst@@makebox}%
\pst@makelongbox}}
\def\pst@makelongbox#1{%
\def\pst@afterbox{#1}%
\edef\pst@mathflag{%
\ifpsmathbox\ifmmode\ifinner 1\else 2\fi\else \z@\fi\else \z@\fi}%
\setbox\pst@hbox\hbox\bgroup
\aftergroup\pst@afterbox
\ifcase\pst@mathflag\or$\m@th\or$\m@th\displaystyle\fi
\begingroup
\pst@thisbox
\the\everypsbox}
\def\pst@endlongbox{%
\endgroup
\ifnum\pst@mathflag>\z@$\fi
\egroup}
\def\pslongbox#1#2{%
\@namedef{#1}{\pst@longbox#2}%
\@namedef{end#1}{\pst@endlongbox}}
\newdimen\psframesep
\def\psset@framesep#1{\pssetlength\psframesep{#1}}
\psset@framesep{3pt}
\newif\ifpsboxsep
\def\psset@boxsep#1{\@nameuse{psboxsep#1}}
\psset@boxsep{true}
\def\pst@useboxpar{%
\use@par
\if@star
\let\pslinecolor\psfillcolor
\solid@star
\let\solid@star\relax
\fi
\ifpsdoubleline \pst@setdoublesep \fi}
\def\psframebox{\pst@object{psframebox}}
\def\psframebox@i{\pst@makebox\psframebox@ii}
\def\psframebox@ii{%
\begingroup
\pst@useboxpar
\pst@dima=\pslinewidth
\advance\pst@dima by \psframesep
\pst@dimc=\wd\pst@hbox\advance\pst@dimc by \pst@dima
\pst@dimb=\dp\pst@hbox\advance\pst@dimb by \pst@dima
\pst@dimd=\ht\pst@hbox\advance\pst@dimd by \pst@dima
\setbox\pst@hbox=\hbox{%
\ifpsboxsep\kern\pst@dima\fi
\begin@ClosedObj
\addto@pscode{%
\psk@cornersize
\pst@number\pst@dima neg
\pst@number\pst@dimb neg
\pst@number\pst@dimc
\pst@number\pst@dimd
.5
\tx@Frame}%
\def\pst@linetype{2}%
\showpointsfalse
\end@ClosedObj
\box\pst@hbox
\ifpsboxsep\kern\pst@dima\fi}%
\ifpsboxsep\dp\pst@hbox=\pst@dimb\ht\pst@hbox=\pst@dimd\fi
\leavevmode\box\pst@hbox
\endgroup}
\def\psdblframebox{\pst@object{psdblframebox}}
\def\psdblframebox@i{\addto@par{doubleline=true}\psframebox@i}
\def\psclip#1{%
\leavevmode
\begingroup
\begin@psclip
\begingroup
\def\use@pscode{%
\pstVerb{%
\pst@dict
/mtrxc CM def
CP CP T
\tx@STV
\psk@origin
\psk@swapaxes
newpath
\pst@code
clip
newpath
mtrxc setmatrix
moveto
0 setgray
end}%
\gdef\pst@code{}}%
\def\@multips(##1)(##2)##3##4{\pst@misplaced\multips}%
\def\nc@object##1##2##3##4{\pst@misplaced{node connection}}%
\hbox to\z@{#1}%
\endgroup
\def\endpsclip{%
\end@psclip
\endgroup}%
\ignorespaces}
\def\endpsclip{\pst@misplaced\endpsclip}
\let\begin@psclip\relax
\def\end@psclip{\pstVerb{currentpoint initclip moveto}}
\def\AltClipMode{%
\def\end@psclip{\pstVerb{\pst@grestore}}%
\def\begin@psclip{\pstVerb{gsave}}}
\def\clipbox{\@ifnextchar[{\clipbox@}{\clipbox@[\z@]}}
% Modification Denis GIROU (CNRS/IDRIS - France) <Denis.Girou@idris.fr> -  3 Apr. 1997
% From paulus@immd5.informatik.uni-erlangen.de (Dietrich Paulus) - 3 Apr 1997
%\def\clipbox@[#1]{\pst@makebox\clipbox@@{#1}}
\def\clipbox@[#1]{\pst@makebox{\clipbox@@{#1}}}
\def\clipbox@@#1{%
\pssetlength\pst@dimg{#1}%
\leavevmode\hbox{%
\begin@psclip
\pst@Verb{%
CM \tx@STV CP T newpath
/a \pst@number\pst@dimg def
/w \pst@number{\wd\pst@hbox}a add def
/d \pst@number{\dp\pst@hbox}a add neg def
/h \pst@number{\ht\pst@hbox}a add def
a neg d moveto
a neg h L
w h L
w d L
closepath
clip
newpath
0 0 moveto
setmatrix}%
\unhbox\pst@hbox
\end@psclip}}
\def\psshadowbox{\pst@object{psshadowbox}}
\def\psshadowbox@i{\pst@makebox\psshadowbox@ii}
\def\psshadowbox@ii{%
\begingroup
\pst@useboxpar
\psshadowtrue
\psboxseptrue
\def\psk@shadowangle{-45 }%
\setbox\pst@hbox=\hbox{\psframebox@ii}%
\pst@dimh=\psk@shadowsize\p@
\pst@dimh=.7071\pst@dimh
\pst@dimg=\dp\pst@hbox
\advance\pst@dimg\pst@dimh
\dp\pst@hbox=\pst@dimg
\pst@dimg=\wd\pst@hbox
\advance\pst@dimg\pst@dimh
\wd\pst@hbox=\pst@dimg
\leavevmode
\box\pst@hbox
\endgroup}
\def\pscirclebox{\pst@object{pscirclebox}}
\def\pscirclebox@i{\pst@makebox\pscirclebox@ii}
\def\pscirclebox@ii{%
\begingroup
\pst@useboxpar
\setbox\pst@hbox=\hbox{%
\pst@nodehook
\pscirclebox@iii
\box\pst@hbox}%
\ifpsboxsep \pscirclebox@sep \fi
\leavevmode
\box\pst@hbox
\endgroup}
\def\pscirclebox@iii{%
\if@star
\pslinewidth\z@
\pstverb{\pst@dict \tx@STP \pst@usecolor\psfillcolor
newpath \pscirclebox@iv \tx@SD end}%
\else
\begin@ClosedObj
\def\pst@linetype{4}\showpointsfalse
\addto@pscode{%
\pscirclebox@iv CLW 2 div add 0 360 arc closepath}%
\end@ClosedObj
\fi}
\def\pscirclebox@iv{%
\pst@number{\wd\pst@hbox}2 div
\pst@number{\ht\pst@hbox}\pst@number{\dp\pst@hbox}add 2 div
2 copy \pst@number{\dp\pst@hbox}sub 4 2 roll
\tx@Pyth \pst@number\psframesep add }
\def\pscirclebox@sep{%
\pst@dimb=\ht\pst@hbox
\advance\pst@dimb\dp\pst@hbox
\divide\pst@dimb 2
\pst@dima=.5\wd\pst@hbox
\pst@pyth\pst@dima\pst@dimb\pst@dimc
\advance\pst@dimc\pslinewidth
\advance\pst@dimc\psframesep
\advance\pst@dimb-\pst@dimc
\setbox\pst@hbox=\hbox to2\pst@dimc{%
\hss
\vbox{\kern-\pst@dimb\box\pst@hbox}%
\hss}%
\advance\pst@dimb-\dp\pst@hbox
\dp\pst@hbox=-\pst@dimb}
\let\pst@nodehook\relax
\def\psCirclebox{\pst@object{psCirclebox}}
\def\psCirclebox@i{\pst@makebox\psCirclebox@ii}
\def\psCirclebox@ii{%
\begingroup
\pst@useboxpar
\pst@dima=\ht\pst@hbox
\advance\pst@dima\dp\pst@hbox
\divide\pst@dima\tw@
\pssetlength\pst@dimb\psk@radius
\setbox\pst@hbox=\hbox{%
\pst@nodehook
\pscircle(.5\wd\pst@hbox,\pst@dima){\pst@dimb}%
\box\pst@hbox}%
\ifpsboxsep \psCirclebox@sep \fi
\leavevmode
\box\pst@hbox
\endgroup}
\def\psCirclebox@sep{%
\pst@dimc=\pst@dimb
\advance\pst@dimb-\pst@dima
\advance\pst@dima\pst@dimc
\setbox\pst@hbox=\hbox to\tw@\pst@dimc{%
\hss
\vrule width \z@ depth \pst@dimb height \pst@dima
\box\pst@hbox
\hss}}%
\def\psovalbox{\pst@object{psovalbox}}
\def\psovalbox@i{\pst@makebox{\psovalbox@ii}}
\def\psovalbox@ii{%
\begingroup
\pst@useboxpar
\psovalbox@iii
\ifpsboxsep\psovalbox@sep\fi
\leavevmode
\box\pst@hbox
\endgroup}
\def\psovalbox@iii{%
\psovalbox@iv
\setbox\pst@hbox=\hbox{%
\begin@ClosedObj
\addto@pscode{%
0 360
\pst@number\pst@dimc CLW 2 div sub
\pst@number\pst@dimd CLW 2 div sub
\pst@number\pst@dima
\pst@number\pst@dimb
\tx@Ellipse
closepath}%
\def\pst@linetype{2}%
\end@ClosedObj
\unhbox\pst@hbox}}
\def\psovalbox@iv{%
\pst@dimc=\pslinewidth\advance\pst@dimc\psframesep
\pst@dimd=\ht\pst@hbox\advance\pst@dimd\dp\pst@hbox
\pst@dima=.5\wd\pst@hbox
\pst@dimb=.5\pst@dimd\advance\pst@dimb-\dp\pst@hbox
\pst@dimd=.707\pst@dimd
\advance\pst@dimd\pst@dimc
\advance\pst@dimc.707\wd\pst@hbox}
\def\psovalbox@sep{%
\setbox\pst@hbox\hbox to 2\pst@dimc{\hss\unhbox\pst@hbox\hss}%
\pst@dimg=\pst@dimd
\advance\pst@dimg-\pst@dimb
\dp\pst@hbox=\pst@dimg
\advance\pst@dimd\pst@dimb
\ht\pst@hbox=\pst@dimd}
\def\psdiabox{\pst@object{psdiabox}}
\def\psdiabox@i{\pst@makebox{\psdiabox@ii}}
\def\psdiabox@ii{%
\begingroup
\pst@useboxpar
\psdiabox@iii
\ifpsboxsep\psdiabox@sep\fi
\leavevmode
\box\pst@hbox
\endgroup}
\def\psdiabox@iv{%
\pst@dimg=.707\pslinewidth
\advance\pst@dimg.707\psframesep
\pst@dima=\wd\pst@hbox
\divide\pst@dima 2
\pst@dimc=\pst@dima
\advance\pst@dimc\pst@dimg
\pst@dimd=\ht\pst@hbox
\advance\pst@dimd\dp\pst@hbox
\divide\pst@dimd 2
\pst@dimb=\pst@dimd
\advance\pst@dimb-\dp\pst@hbox
\advance\pst@dimd\pst@dimg}
\def\psdiabox@iii{%
\psdiabox@iv
\setbox\pst@hbox=\hbox{%
\begin@ClosedObj
\addto@pscode{%
\psline@iii
pop
.5
\pst@number\pst@dimc 2 mul \pst@number\pst@dimd 2 mul
0
\pst@number\pst@dima \pst@number\pst@dimb
\tx@Diamond}%
\def\pst@linetype{4}%
\end@ClosedObj
\box\pst@hbox}}
\def\psdiabox@sep{%
\setbox\pst@hbox\hbox to 4\pst@dimc{\hss\unhbox\pst@hbox\hss}%
\multiply\pst@dimd 2
\advance\pst@dimd\pst@dimb
\ht\pst@hbox\pst@dimd
\advance\pst@dimd-2\pst@dimb
\dp\pst@hbox\pst@dimd}
\def\psset@trimode#1{\pst@expandafter\psset@@trimode{#1}\@empty\@empty\@nil}
\def\psset@@trimode#1#2#3\@nil{%
\let\pst@tempg#1\relax
\ifx\pst@tempg*%
\let\psk@@trimode\@empty
\let\pst@tempg#2\relax
\else
\let\psk@@trimode\relax
\fi
\edef\psk@trimode{%
\ifx R\pst@tempg 1 \else\ifx D\pst@tempg 2
\else\ifx L\pst@tempg 3 \else 0 \fi\fi\fi}}
\psset@trimode{U}
\def\pstribox{\pst@object{pstribox}}
\def\pstribox@i{\pst@makebox{\pstribox@ii}}
\def\pstribox@ii{%
\begingroup
\pst@useboxpar
\pstribox@iii
\ifpsboxsep\pstribox@sep\fi
\leavevmode
\box\pst@hbox
\endgroup}
\def\pstribox@iii{%
\pstribox@iv
\setbox\pst@hbox=\hbox{%
\begin@ClosedObj
\addto@pscode{%
\psline@iii
pop
.5
\pst@number\pst@dimc \pst@number\pst@dimd
\ifodd\psk@trimode exch \fi
\psk@trimode -90 mul
\pst@number\pst@dima \pst@number\pst@dimb
\tx@Triangle}%
\def\pst@linetype{2}%
\end@ClosedObj
\box\pst@hbox}}
\def\pstribox@iv{%
\pst@dimh=\pslinewidth
\advance\pst@dimh\psframesep
\pst@dimg=\ht\pst@hbox
\advance\pst@dimg-\dp\pst@hbox
\divide\pst@dimg 2
\edef\pst@tempa{\number\pst@dimg sp}% For use by nodes.
\ifodd\psk@trimode
\pst@dimb\pst@dimg
\else
\pst@dima=\wd\pst@hbox
\divide\pst@dima 2
\fi
\ifcase\psk@trimode
\pst@dimb=-\dp\pst@hbox
\advance\pst@dimb-\pst@dimh
\or
\pst@dima=-\pst@dimh
\or
\pst@dimb=\ht\pst@hbox
\advance\pst@dimb\pst@dimh
\or
\pst@dima=\wd\pst@hbox
\advance\pst@dima\pst@dimh
\fi
\pst@dimd=\dp\pst@hbox
\advance\pst@dimd\ht\pst@hbox
\ifx\psk@@trimode\relax
\pst@dimc=\wd\pst@hbox
\advance\pst@dimc\ifodd\psk@trimode 1.447\else 1.789\fi\pst@dimh
\multiply\pst@dimc 2
\advance\pst@dimd\ifodd\psk@trimode 1.789\else 1.447\fi\pst@dimh
\multiply\pst@dimd 2
\else
\ifodd\psk@trimode
\advance\pst@dimd 1.1547\wd\pst@hbox
\advance\pst@dimd 3.4641\pst@dimh
\pst@dimc=.866\pst@dimd
\else
\advance\pst@dimd .866\wd\pst@hbox %.866=(sqrt(3)/2)
\advance\pst@dimd 3\pst@dimh
\pst@dimc=1.1547\pst@dimd % 1.1547=(2/sqrt(3))
\fi
\fi}
\def\pstribox@sep{%
\ifodd\psk@trimode
\advance\pst@dimb.5\pst@dimd
\ht\pst@hbox=\pst@dimb
\advance\pst@dimd-\pst@dimb
\dp\pst@hbox=\pst@dimd
\else
\setbox\pst@hbox\hbox to \pst@dimc{\hss\unhbox\pst@hbox\hss}%
\global\pst@dimg=.5\pst@dimc
\fi
\ifcase\psk@trimode
\dp\pst@hbox-\pst@dimb
\advance\pst@dimd\pst@dimb
\ht\pst@hbox\pst@dimd
\or
\pst@dimg=.5\wd\pst@hbox
\global\advance\pst@dimg-\pst@dima
\setbox\pst@hbox\hbox to \pst@dimc{\kern-\pst@dima\box\pst@hbox\hss}%
\or
\ht\pst@hbox\pst@dimb
\advance\pst@dimd-\pst@dimb
\dp\pst@hbox\pst@dimd
\or
\pst@dimg=\pst@dimc
\advance\pst@dimg-\pst@dima
\global\advance\pst@dimg.5\wd\pst@hbox
\setbox\pst@hbox\hbox to \pst@dimc{%
\hss\box\pst@hbox\kern\psframesep\kern\pslinewidth}%
\fi}
\def\psset@arcsepA#1{\pst@getlength{#1}\psk@arcsepA}
\def\psset@arcsepB#1{\pst@getlength{#1}\psk@arcsepB}
\def\psset@arcsep#1{%
\psset@arcsepA{#1}\let\psk@arcsepB\psk@arcsepA}
\psset@arcsep{0}
\def\tx@ArcArrow{ArcArrow }
\def\psarc{\pst@object{psarc}}
\def\psarc@i{%
\@ifnextchar({\psarc@iii}{\psarc@ii}}
\def\psarc@ii#1{\addto@par{arrows=#1}%
\@ifnextchar({\psarc@iii}{\psarc@iii(0,0)}}
\def\psarc@iii(#1)#2#3#4{%
\begin@OpenObj
\pst@getangle{#3}\pst@tempa
\pst@getangle{#4}\pst@tempb
\pst@@getcoor{#1}%
\pssetlength\pst@dima{#2}%
\addto@pscode{\psarc@iv \psarc@v}%
\gdef\psarc@type{0}%
\showpointsfalse
\end@OpenObj}
\def\psarc@iv{%
\pst@coor /y ED /x ED
/r \pst@number\pst@dima def
/c 57.2957 r \tx@Div def
/angleA
\pst@tempa
\psk@arcsepA c mul 2 div
\ifcase \psarc@type add \or sub \fi
def
/angleB
\pst@tempb
\psk@arcsepB c mul 2 div
\ifcase \psarc@type sub \or add \fi
def
\ifshowpoints\psarc@showpoints\fi
\ifx\psk@arrowA\@empty
\ifnum\psk@liftpen=2
r angleA \tx@PtoC
y add exch x add exch
moveto
\fi
\fi}
\def\psarc@v{%
x y r
angleA
\ifx\psk@arrowA\@empty\else
{ ArrowA CP }
{ \ifcase\psarc@type add \or sub \fi }
\tx@ArcArrow
\fi
angleB
\ifx\psk@arrowB\@empty\else
{ ArrowB }
{ \ifcase\psarc@type sub \or add \fi }
\tx@ArcArrow
\fi
\ifcase\psarc@type arc \or arcn \fi}
\def\psarc@type{0}
\def\psarc@showpoints{%
gsave
newpath
x y moveto
x y r \pst@tempa \pst@tempb
\ifcase\psarc@type arc \or arcn \fi
closepath
CLW 2 div SLW
[ \psk@dash\space ] 0 setdash stroke
grestore }
\def\psarcn{\pst@object{psarcn}}
\def\psarcn@i{\def\psarc@type{1}\psarc@i}
\def\pscircle{\pst@object{pscircle}}
\def\pscircle@i{\@ifnextchar({\pscircle@do}{\pscircle@do(0,0)}}
\def\pscircle@do(#1)#2{%
\if@star
{\use@par\qdisk(#1){#2}}%
\else
\begin@ClosedObj
\pst@@getcoor{#1}%
\pssetlength\pst@dimc{#2}%
\def\pst@linetype{4}%
\addto@pscode{%
\pst@coor
\pst@number\pst@dimc
\psk@dimen CLW mul sub
0 360 arc
closepath}%
\showpointsfalse
\end@ClosedObj
\fi
\ignorespaces}
\def\qdisk(#1)#2{%
\def\pst@par{}%
\begin@SpecialObj
\pst@@getcoor{#1}%
\pssetlength\pst@dimg{#2}%
\addto@pscode{\pst@coor \pst@number\pst@dimg \tx@SD}%
\end@SpecialObj}
\def\psset@radius#1{\pst@@getlength{#1}\psk@radius}
\psset@radius{.25cm}
\def\psCircle{\pst@object{psCircle}}
\def\psCircle@i{\@ifnextchar({\psCircle@ii}{\psCircle@ii(0,0)}}
\def\psCircle@ii(#1){\pscircle@do(#1){\psk@radius}}
\def\pswedge{\pst@object{pswedge}}
\def\pswedge@i{\@ifnextchar({\pswedge@ii}{\pswedge@ii(0,0)}}
\def\pswedge@ii(#1)#2#3#4{%
\begin@ClosedObj
\pssetlength\pst@dimc{#2}
\pst@getangle{#3}\pst@tempa
\pst@getangle{#4}\pst@tempb
\pst@@getcoor{#1}%
\def\pst@linetype{1}%
\addto@pscode{%
\pst@coor
2 copy
moveto
\pst@number\pst@dimc \psk@dimen CLW mul sub % Adjusted radius
\pst@tempa \pst@tempb
arc
closepath}%
\showpointsfalse
\end@ClosedObj}
\def\tx@Ellipse{Ellipse }
\def\psellipse{\pst@object{psellipse}}
\def\psellipse@i(#1){\@ifnextchar(%
{\psellipse@ii(#1)}{\psellipse@ii(0,0)(#1)}}
\def\psellipse@ii(#1)(#2){%
\begin@ClosedObj
\pst@getcoor{#1}\pst@tempa
\pst@@getcoor{#2}%
\addto@pscode{%
0 360
\pst@coor
\ifdim\psk@dimen\p@=\z@\else
\psk@dimen CLW mul
dup 4 -1 roll sub neg 3 1 roll sub
\fi
\pst@tempa
\tx@Ellipse
closepath}%
\def\pst@linetype{2}%
\end@ClosedObj}
\def\multips{\@ifnextchar({\def\pst@par{}\multips@ii}{\multips@i}}
\def\multips@i#1{\def\pst@par{rot=#1}\multips@ii}
\def\multips@ii(#1){\@ifnextchar({\multips@iii(#1)}{\multips@iii(\z@,\z@)(#1)}}
\long\def\multips@iii(#1)(#2)#3#4{%
\begingroup
\use@par
\pst@getcoor{#1}\pst@tempa
\pst@@getcoor{#2}%
\pst@cnta=#3\relax
\init@pscode
\addto@pscode{%
\pst@tempa T \the\pst@cnta\space \pslbrace
gsave \ifx\psk@rot\@empty\else\psk@rot rotate \fi}%
\hbox to\z@{%
\def\init@pscode{%
\addto@pscode{%
gsave
\pst@number\pslinewidth SLW
\pst@usecolor\pslinecolor}}%
\def\use@pscode{\addto@pscode{grestore}}%
\def\psclip##1{\pst@misplaced\psclip}%
\def\nc@object##1##2##3##4{\pst@misplaced{node connection}}%
#4}%
\addto@pscode{grestore \pst@coor T \psrbrace repeat}%
\leavevmode
\use@pscode
\endgroup
\ignorespaces}
\def\scalebox#1{\pst@makebox{\@scalebox{#1}}}
\def\@scalebox#1{%
\begingroup
\pst@getscale{#1}\pst@tempa
\let\pst@tempc\pst@tempg
\let\pst@tempd\pst@temph
\@@scalebox
\endgroup}
\def\@@scalebox{%
\leavevmode
\hbox{%
\ifdim\pst@tempd\p@<\z@
\pst@dimg=\pst@tempd\ht\pst@hbox
\pst@dimh=\pst@tempd\dp\pst@hbox
\dp\pst@hbox=-\pst@dimg
\ht\pst@hbox=-\pst@dimh
\else
\ht\pst@hbox=\pst@tempd\ht\pst@hbox
\dp\pst@hbox=\pst@tempd\dp\pst@hbox
\fi
\pst@dima=\pst@tempc\wd\pst@hbox
\ifdim\pst@dima<\z@\kern-\pst@dima\fi
\pst@Verb{CP CP translate \pst@tempa \tx@NET}%
\hbox to \z@{\box\pst@hbox\hss}%
\pst@Verb{%
CP CP translate
1 \pst@tempc div 1 \pst@tempd div scale
\tx@NET}%
\ifdim\pst@dima>\z@\kern\pst@dima\fi}}
\pslongbox{Scalebox}{\scalebox}
\def\scaleboxto(#1,#2){\pst@makebox{\@scaleboxto(#1,#2)}}
\def\@scaleboxto(#1,#2){%
\begingroup
\pssetlength\pst@dima{#1}%
\pssetlength\pst@dimb{#2}%
\ifdim\pst@dima=\z@\else
\pst@divide{\pst@dima}{\wd\pst@hbox}\pst@tempc
\edef\pst@tempc{\pst@tempc\space}%
\fi
\ifdim\pst@dimb=\z@
\ifdim\pst@dima=\z@
\@pstrickserr{%
\string\scaleboxto\space dimensions cannot both be zero}\@ehpa
\def\pst@tempa{}%
\def\pst@tempc{1 }%
\def\pst@tempd{1 }%
\else
\let\pst@tempd\pst@tempc
\fi
\else
\pst@dimc=\ht\pst@hbox
\advance\pst@dimc\dp\pst@hbox
\pst@divide{\pst@dimb}{\pst@dimc}\pst@tempd
\edef\pst@tempd{\pst@tempd\space}%
\ifdim\pst@dima=\z@ \let\pst@tempc\pst@tempd \fi
\fi
\edef\pst@tempa{\pst@tempc \pst@tempd scale }%
\@@scalebox
\endgroup}
\pslongbox{Scaleboxto}{\scaleboxto}
\def\tx@Rot{Rot }
\def\rotateleft{\pst@makebox{\@rotateleft\pst@hbox}}
\def\@rotateleft#1{%
\leavevmode\hbox{\hskip\ht#1\hskip\dp#1\vbox{\vskip\wd#1%
\pst@Verb{90 \tx@Rot}
\vbox to \z@{\vss\hbox to \z@{\box#1\hss}\vskip\z@}%
\pst@Verb{-90 \tx@Rot}}}}
\def\rotateright{\pst@makebox{\@rotateright\pst@hbox}}
\def\@rotateright#1{%
\hbox{\hskip\ht#1\hskip\dp#1\vbox{\vskip\wd#1%
\pst@Verb{-90 \tx@Rot}
\vbox to \z@{\hbox to \z@{\hss\box#1}\vss}%
\pst@Verb{90 \tx@Rot}}}}
\def\rotatedown{\pst@makebox{\@rotatedown\pst@hbox}}
\def\@rotatedown#1{%
\hbox{\hskip\wd#1\vbox{\vskip\ht#1\vskip\dp#1%
\pst@Verb{180 \tx@Rot}%
\vbox to \z@{\hbox to \z@{\box#1\hss}\vss}%
\pst@Verb{-180 \tx@Rot}}}}
\pslongbox{Rotateleft}{\rotateleft}
\pslongbox{Rotateright}{\rotateright}
\pslongbox{Rotatedown}{\rotatedown}
\def\pst@starbox{%
\setbox\pst@hbox\hbox{\psframebox*[boxsep=false]{\unhbox\pst@hbox}}}
\def\pst@@makesmall#1{%
\setbox#1=\hbox to\z@{\hss\vbox to \z@{\vss\box#1\vss}\hss}}
\def\pst@@@makesmall#1{%
\pst@dimh=\psk@xref\wd#1%
\ifx\psk@yref\relax
\pst@dimg=\dp#1%
\else
\pst@dimg=\psk@yref\ht#1%
\advance\pst@dimg\psk@yref\dp#1%
\fi
\setbox#1=\hbox to\z@{%
\kern-\pst@dimh\vbox to\z@{\vss\box#1\kern-\pst@dimg}\hss}}
\def\psset@ref#1{\pst@expandafter\psset@@ref{#1}\@empty,,\@nil}
\def\psset@@ref#1#2,#3,#4\@nil{%
\def\psk@xref{.5}%
\def\psk@yref{.5}%
\let\pst@makesmall\pst@@@makesmall
\ifx\@empty#3\@empty
\@nameuse{getref@#1}%
\@nameuse{getref@#2}%
\else
\pst@checknum{#1#2}\psk@xref
\pst@checknum{#3}\psk@yref
\fi}
\def\getref@c{\let\pst@makesmall\pst@@makesmall}
\def\getref@t{\def\psk@yref{1}}
\def\getref@b{\def\psk@yref{0}}
\def\getref@B{\let\psk@yref\relax}
\def\getref@l{\def\psk@xref{0}}
\def\getref@r{\def\psk@xref{1}}
\psset@ref{c}
\def\psset@rot#1{%
\pst@expandafter{\@ifnextchar*{\psset@@@rot}{\psset@@rot}}{#1}\@nil}
\def\psset@@rot#1\@nil{%
\def\next##1@#1=##2@##3\@nil{%
\ifx\relax##2%
\pst@getangle{#1}\psk@rot
\else
\def\psk@rot{##2}%
\fi}%
\expandafter\next\pst@rottable @#1=\relax @\@nil}
\def\psset@@@rot#1#2\@nil{%
\psset@@rot#2\@nil
\edef\psk@rot{\pst@rotlist \ifx\psk@rot\@empty\else\psk@rot add \fi}}
\def\pst@rotlist{mark RAngle /a ED cleartomark a neg }
\def\pst@rottable{%
@0=%
@U=%
@L=90 %
@D=180 %
@R=-90 %
@N=\pst@rotlist
@W=\pst@rotlist 90 add %
@S=\pst@rotlist 180 add %
@E=\pst@rotlist 90 sub }
\psset@rot{0}
\def\tx@RotBegin{RotBegin }
\def\tx@RotEnd{RotEnd }
\def\pst@rotate#1#2{%
\ifx#1\@empty\else
\setbox#2=\hbox{\pst@Verb{#1 \tx@RotBegin}\box#2\pst@Verb{\tx@RotEnd}}%
\fi}
\def\psput@cartesian#1{%
\hbox to \z@{\kern\pst@dimg{\vbox to \z@{\vss\box#1\vskip\pst@dimh}\hss}}}
\def\psput@special#1{%
\hbox{%
\pst@Verb{{ \pst@coor } \tx@PutCoor \tx@PutBegin}%
\box#1%
\pst@Verb{\tx@PutEnd}}}
\def\tx@PutCoor{PutCoor }
\def\tx@PutBegin{PutBegin }
\def\tx@PutEnd{PutEnd }
\def\rput{\def\pst@par{}\pst@ifstar{\@ifnextchar[{\rput@i}{\rput@ii}}}
\def\rput@i[#1]{\addto@par{ref={#1}}\rput@ii}
\def\rput@ii{\@ifnextchar({\rput@iv}{\rput@iii}}
\def\rput@iii#1{\addto@par{rot={#1}}\@ifnextchar({\rput@iv}{\rput@iv(\z@,\z@)}}
\def\rput@iv(#1){\pst@killglue\pst@makebox{\rput@v{#1}}}
\def\rput@v#1{%
\begingroup
\use@par
\if@star\pst@starbox\fi
\pst@makesmall\pst@hbox
\pst@rotate\psk@rot\pst@hbox
\psput@{#1}\pst@hbox
\endgroup
\ignorespaces}
\def\multirput{%
\def\pst@par{}%
\pst@ifstar{\@ifnextchar[{\multirput@i}{\multirput@ii}}}
\def\multirput@i[#1]{\addto@par{ref={#1}}\multirput@ii}
\def\multirput@ii{\@ifnextchar({\multirput@iv}{\multirput@iii}}
\def\multirput@iii#1{\addto@par{rot={#1}}\multirput@iv}
\def\multirput@iv(#1){%
\@ifnextchar({\multirput@v(#1)}{\multirput@v(\z@,\z@)(#1)}}
\def\multirput@v(#1,#2)(#3,#4)#5{%
\pst@makebox{\multirput@vi(#1,#2)(#3,#4){#5}}}
\def\multirput@vi(#1,#2)(#3,#4)#5{%
\begingroup
\use@par
\if@star\pst@starbox\fi
\pst@makesmall\pst@hbox
\pst@rotate\psk@rot\pst@hbox
\pssetxlength\pst@dima{#1}%
\pssetylength\pst@dimb{#2}%
\pssetxlength\pst@dimc{#3}%
\pssetylength\pst@dimd{#4}%
\pst@cntg=#5\relax
\pst@cnth=\@ne
\leavevmode
\loop
\vbox to \z@{%
\vss
\hbox to \z@{\kern\pst@dima\copy\pst@hbox\hss}%
\vskip\pst@dimb}%
\ifnum\pst@cntg>\pst@cnth
\advance\pst@dima\pst@dimc
\advance\pst@dimb\pst@dimd
\advance\pst@cnth\@ne
\repeat
\endgroup
\ignorespaces}
\newif\if@fixedradius
\def\cput{\pst@object{cput}}
\def\cput@i{\@fixedradiusfalse\cput@ii}
\def\cput@ii{\pst@killglue\@ifnextchar({\cput@iv}{\cput@iii}}
\def\cput@iii#1{%
\addto@par{rot={#1}}%
\@ifnextchar({\cput@iv}{\cput@iv(\z@,\z@)}}
\def\cput@iv(#1){\pst@makebox{\cput@v{#1}}}
\def\cput@v#1{%
\begingroup
\use@par
\setbox\pst@hbox=\hbox{%
\psboxsepfalse
\if@fixedradius\psCirclebox@ii\else\pscirclebox@ii\fi}%
\pst@@makesmall\pst@hbox
\pst@rotate\psk@rot\pst@hbox
\psput@{#1}\pst@hbox
\endgroup
\ignorespaces}
\def\Cput{\pst@object{Cput}}
\def\Cput@i{\@fixedradiustrue\cput@ii}
\newdimen\pslabelsep
\def\psset@labelsep#1{\pssetlength\pslabelsep{#1}}
\psset@labelsep{5pt}
\def\psset@refangle#1{\pst@expandafter\psset@@refangle{#1}\@nil}
\def\psset@@refangle#1\@nil{%
\def\next##1@#1=##2"##3@##4\@nil{%
\ifx\relax##2%
\pst@getangle{#1}\psk@refangle
\def\psk@uputref{}%
\else
\def\psk@refangle{##2 }%
\def\psk@uputref{##3}%
\fi}%
\expandafter\next\pst@refangletable @#1=\relax"@\@nil}
\def\pst@refangletable{%
@r=0"20%
@u=90"02%
@l=180"10%
@d=-90"01%
@ur=45"22%
@ul=135"12%
@dr=-135"21%
@dl=-45"11}
\psset@refangle{0}
\def\uput{\def\pst@par{}\@ifnextchar[{\uput@ii}{\uput@i}}
\def\uput@i#1{\addto@par{labelsep=#1}\uput@ii}
\def\uput@ii[#1]{%
\addto@par{refangle={#1}}%
\@ifnextchar({\uput@iv}{\uput@iii}}
\def\uput@iii#1{%
\addto@par{rot={#1}}%
\@ifnextchar({\uput@iv}{\uput@iv(\z@,\z@)}}
\def\uput@iv(#1){\pst@killglue\pst@makebox{\uput@v{#1}}}
\def\uput@v#1{%
\begingroup
\use@par
\if@star\pst@starbox\fi
\uput@vi
\psput@{#1}\pst@hbox
\endgroup
\ignorespaces}
\def\uput@vi{%
\ifx\psk@uputref\@empty
\uput@vii\tx@UUput{}%
\else
\ifx\psk@rot\@empty
\expandafter\uput@viii\psk@uputref
\else
\uput@vii\tx@UUput{}%
\fi
\fi}
\def\uput@vii#1#2{%
\edef\pst@coor{%
\pst@number\pslabelsep
#2%
\pst@number{\wd\pst@hbox}%
\pst@number{\ht\pst@hbox}%
\pst@number{\dp\pst@hbox}%
\psk@refangle\space \ifx\psk@rot\@empty\else\psk@rot\space sub \fi
\tx@Uput #1}%
\setbox\pst@hbox=\hbox to\z@{\hss\vbox to\z@{\vss\box\pst@hbox\vss}\hss}%
\setbox\pst@hbox=\psput@special\pst@hbox
\ifx\psk@rot\@empty\else\pst@rotate\psk@rot\pst@hbox\fi}
\def\uput@viii#1#2{%
\ifnum#1>\z@\ifnum#2>\z@\pslabelsep=.707\pslabelsep\fi\fi
\setbox\pst@hbox=\vbox to\z@{%
\ifnum#2=1 \vskip\pslabelsep\else\vss\fi
\hbox to\z@{%
\ifnum#1=2 \hskip\pslabelsep\else\hss\fi
\box\pst@hbox
\ifnum#1=1 \hskip\pslabelsep\else\hss\fi}%
\ifnum#2=2 \vskip\pslabelsep\else\vss\fi}}
\def\tx@Uput{Uput }
\def\tx@UUput{UUput }
\def\Rput{\def\pst@par{}\pst@ifstar{\@ifnextchar[{\Rput@ii}{\Rput@i}}}
\def\Rput@i#1{\addto@par{labelsep=#1}\Rput@ii}
\def\Rput@ii[#1]{\addto@par{ref={#1}}\@ifnextchar({\Rput@iv}{\Rput@iii}}
\def\Rput@iii#1{\addto@par{rot={#1}}\@ifnextchar({\Rput@iv}{\Rput@iv(\z@,\z@)}}
\def\Rput@iv(#1){\pst@killglue\pst@makebox{\Rput@v{#1}}}
\def\Rput@v#1{%
\begingroup
\use@par
\if@star\pst@starbox\fi
\Rput@vi
\pst@makesmall\pst@hbox
\pst@rotate\psk@rot\pst@hbox
\psput@{#1}\pst@hbox
\endgroup
\ignorespaces}
\def\Rput@vi{%
\pst@dimg=\dp\pst@hbox
\advance\pst@dimg\pslabelsep
\dp\pst@hbox=\pst@dimg
\pst@dimg=\ht\pst@hbox
\advance\pst@dimg\pslabelsep
\ht\pst@hbox=\pst@dimg
\setbox\pst@hbox\hbox{\kern\pslabelsep\box\pst@hbox\kern\pslabelsep}}%
\def\oldpsput{%
\def\pst@par{}\pst@ifstar{\@ifnextchar[{\oldpsput@i}{\oldpsput@ii}}}
\def\oldpsput@i[#1]{\addto@par{ref={#1}}\oldpsput@ii}
\def\oldpsput@ii{\@ifnextchar<{\oldpsput@iii}{\oldpsput@iv}}
\def\oldpsput@iii<#1>{\rput@iii{#1}}
\def\OldPsput{\let\psput\oldpsput}
\def\NewPsput{\let\psput\rput}
\def\pspicture{\begingroup\pst@ifstar\pst@picture}
\def\pst@picture{%
\@ifnextchar[{\pst@@picture}{\pst@@picture[0]}}
\def\pst@@picture[#1]#2(#3,#4){%
\@ifnextchar({\pst@@@picture[#1](#3,#4)}%
{\pst@@@picture[#1](0,0)(#3,#4)}}
\def\pst@@@picture[#1](#2,#3)(#4,#5){%
\pssetxlength\pst@dima{#2}%
\pssetylength\pst@dimb{#3}%
\pssetxlength\pst@dimc{#4}%
\pssetylength\pst@dimd{#5}%
\ifdim\pst@dima>\pst@dimc
\pst@dimg=\pst@dima
\pst@dima=\pst@dimc
\pst@dimc=\pst@dimg
\fi
\ifdim\pst@dimb>\pst@dimd
\pst@dimg=\pst@dimb
\pst@dimb=\pst@dimd
\pst@dimd=\pst@dimg
\fi
\def\pst@tempa{#1}%
\setbox\pst@hbox=\hbox\bgroup
\begingroup\KillGlue
\@ifundefined{@latexerr}{}{\let\unitlength\psunit}%
\edef\pic@coor{(#2,#3)(#2,#3)(#4,#5)}\ignorespaces}
\def\pic@coor{(0,0)(0,0)(10,10)}
\def\endpspicture{%
\pst@killglue
\endgroup
\egroup
\ifdim\wd\pst@hbox=\z@\else
%\@pstrickserr{Extraneous space in the pspicture environment}%
%{Type \space <return> \space to procede.}%
\fi
\ht\pst@hbox=\pst@dimd
\dp\pst@hbox=-\pst@dimb
\setbox\pst@hbox=\hbox{%
\kern-\pst@dima
\ifx\pst@tempa\@empty\else
\advance\pst@dimd-\pst@dimb
\pst@dimd=\pst@tempa\pst@dimd
\advance\pst@dimd\pst@dimb
\lower\pst@dimd
\fi
\box\pst@hbox
\kern\pst@dimc}%
\if@star\setbox\pst@hbox=\hbox{\clipbox@@\z@}\fi
\leavevmode\box\pst@hbox
\endgroup}
\@namedef{pspicture*}{\pspicture*}
\@namedef{endpspicture*}{\endpspicture}
\def\tx@BeginOL{BeginOL }
\def\tx@InitOL{InitOL }
\def\pst@initoverlay#1{\pst@Verb{\tx@InitOL /TheOL (#1) def}}
\def\AltOverlayMode{%
\def\pst@initoverlay##1{%
\pst@Verb{%
\tx@InitOL
/Visible { initclip } def
/Invisible {
CP newpath OLUnit itransform moveto clip newpath moveto
} def
/TheOL (##1) def}}}
\def\pst@overlay#1{%
\edef\curr@overlay{#1}%
\pst@Verb{(#1) BOL}%
\aftergroup\pst@endoverlay}
\def\pst@endoverlay{%
\pst@Verb{(\curr@overlay) BOL}}
\def\curr@overlay{all}
\newbox\theoverlaybox
\def\overlaybox{%
\global\setbox\theoverlaybox=\hbox\bgroup
\begingroup
\let\psoverlay\pst@overlay
\def\overlaybox{%
\@pstrickserr{Overlays cannot be nested}\@eha}%
\def\putoverlaybox{%
\@pstrickserr{You must end the overlay box
before using \string\putoverlaybox}}%
\psoverlay{main}%
\ignorespaces}
\def\endoverlaybox{\endgroup\egroup}
\def\putoverlaybox#1{%
\hbox{\pst@initoverlay{#1}\copy\theoverlaybox}}
\def\psoverlay{\@pstrickserr{\string\psoverlay\space
can only be used after \string\overlaybox}}
\ifx\pstcustomize\relax \input pstricks.con \fi
\catcode`\@=\PstAtCode\relax
%
\input pstricks.bug
\endinput
%%
%% END: pstricks.tex


shuffle.tex
%Run ispell!
% Get revtex4 from http://publish.aps.org/revtex4
% Versions 0.9-6 an onward of tetex include the mathptmx package.

%One-column version:
%\documentclass[amssymb,aps,secnumarabicnofootinbib]{revtex4}
%Two-column version:
\documentclass[twocolumn,amssymb,aps,secnumarabic,nofootinbib]{revtex4}
\usepackage{times,mathptmx,amsthm,amsmath}
\usepackage{pstricks,pst-node,graphics}
\bibliographystyle{hamsplain}

\newcommand{\half}{{\small 1/2}}
\newcommand{\odisk}{\pscircle[fillstyle=solid]}

\newcommand{\onex}{1.732}
\newcommand{\twox}{3.464}
\newcommand{\threex}{5.196}
\newcommand{\fourx}{6.928}

\theoremstyle{definition}
\newtheorem*{note}{Note}

\renewcommand{\figurename}{Figure}

\psset{linewidth=.5pt}

\begin{document}
\title{Generalized Domino-Shuffling}
\author{James Propp ({\tt propp@math.wisc.edu})}
\thanks{Supported by grants from the National Science
Foundation and the National Security Agency.} 
\affiliation{Department of Mathematics \\
University of Wisconsin - Madison}
\date{September 30, 2001}
\begin{abstract}
\vspace{.1in}
The problem of counting tilings of a plane region
using specified tiles
can often be recast as 
the problem of counting (perfect) matchings 
of some subgraph of an Aztec diamond graph $A_n$,
or more generally 
calculating the sum of the weights of all the matchings,
where the weight of a matching is equal to the product
of the (pre-assigned) weights of the constituent edges
(assumed to be non-negative).
This article presents efficient algorithms 
that work in this context to solve three problems: 
finding the sum of the weights of the matchings
of a weighted Aztec diamond graph $A_n$; 
computing the probability that a randomly-chosen matching of $A_n$ 
will include a particular edge
(where the probability of a matching is proportional to its weight); 
and generating a matching of $A_n$ at random.
The first of these algorithms is equivalent to
a special case of Mihai Ciucu's cellular complementation algorithm \cite{Ci2}
and can be used to solve many of the same problems.
The second of the three algorithms is a generalization 
of not-yet-published work of Alexandru Ionescu, 
and can be employed to prove an identity 
governing a three-variable generating function
whose coefficients are all the edge-inclusion probabilities;
this formula has been used \cite{CEP}
as the basis for asymptotic formulas for these probabilities,
but a proof of the generating function identity
has not hitherto been published.
%%FIX Will I give the proof of the identity?
The third of the three algorithms 
is a generalization of the domino-shuffling algorithm
presented in \cite{EKLP}; 
it enables one to generate random ``diabolo-tilings of fortresses''
and thereby to make intriguing inferences 
about their asymptotic behavior.
\vspace{.1in}
\end{abstract}
\maketitle

\section{Introduction}

\subsection{Background}

Let $L$ be the rotated square lattice with vertex set 
$\{(i,j): i,j \in {\bf Z}, \ \mbox{$i+j$ is odd}\}$, 
and with an edge joining two vertices in the graph 
if and only if the Euclidean distance between the corresponding 
points in the plane is $\sqrt{2}$.
Define the {\it Aztec diamond graph\/} of order $n$
(denoted by $A_n$) 
as the induced subgraph of $L$ 
with vertices $(i,j$) satisfying $-n \leq i,j \leq n$, 
as shown below for $n=3$.
$$
\pspicture(-1.8,-1.8)(1.8,1.8)
\psset{xunit=.5cm,yunit=.5cm}
\pspolygon(-3,-2)(2,3)(3,2)(-2,-3)
\pspolygon(-3,0)(0,3)(3,0)(0,-3)
\pspolygon(-3,2)(-2,3)(3,-2)(2,-3)
\endpspicture
$$
A {\it partial matching\/} of a graph 
is a set of vertex-disjoint edges belonging to the graph, 
and a {\it perfect matching\/} is a partial matching 
with the property that every vertex of the graph 
belongs to exactly one edge in the matching.
Here is a perfect matching of
an Aztec diamond graph of order 3:
$$
\pspicture(-1.8,-1.8)(1.8,1.8)
\psset{xunit=.5cm,yunit=.5cm}
\psline(-3,2)(-2,3)
\psline(-3,-2)(-2,-3)
\psline(3,2)(2,3)
\psline(3,-2)(2,-3)
\psline(-3,0)(-2,1)
\psline(0,-3)(1,-2)
\psline(-1,-2)(-2,-1)
\psline(0,-1)(-1,0)
\psline(-1,2)(0,3)
\psline(0,1)(1,2)
\psline(2,-1)(1,0)
\psline(3,0)(2,1)
\endpspicture
$$
(Hereafter, the term ``matching'', used without a modifier,
will denote a perfect matching.)

Matchings of Aztec diamond graphs
were studied in \cite{EKLP},
in the dual guise of domino-tilings
(see below for the domino-tiling
dual to the previously depicted matching).
$$
\pspicture(-2.2,-2.2)(2.2,2.2)
\psset{xunit=.5cm,yunit=.5cm}
\psline(-4,2)(-2,4)
\psline(-4,0)(0,4)
\psline(-4,-2)(2,4)
\psline(0,0)(2,2)
\psline(-2,-4)(1,-1)
\psline(3,1)(4,2)
\psline(0,-4)(4,0)
\psline(2,-4)(4,-2)
\psline(-4,-2)(-2,-4)
\psline(-4,0)(0,-4)
\psline(-4,2)(-3,1)
\psline(-2,0)(0,-2)
\psline(1,-3)(2,-4)
\psline(-2,2)(2,-2)
\psline(-2,4)(-1,3)
\psline(1,1)(4,-2)
\psline(0,4)(4,0)
\psline(2,4)(4,2)
\endpspicture
$$
Note that this is rotated by 45 degrees from
the original picture presented in \cite{EKLP}.
That article showed, by means of four different proofs,
that the number of 
matchings of an Aztec diamond graph of order $n$ 
is $2^{n(n+1)/2}$
(as had been conjectured a decade earlier
in the physics literature \cite{GCZ}).
One of the proofs of this result 
(developed by authors Kuperberg and Propp)
used a geometric-combinatorial procedure dubbed ``shuffling" 
(short for ``domino-shuffling"). 
Shuffling was originally introduced purely 
for purposes of counting
the domino-tilings of the Aztec diamond of order $n$,
but it later turned out to be useful as the basis 
for an algorithm for sampling from 
the uniform distribution on this set of tilings. 
An undergraduate, Sameera Iyengar, 
was the first person to implement
domino-shuffling on a computer,
and the output of her program suggested that 
domino-tilings of Aztec diamonds
exhibit a spatially-expressed phase transition,
where the boundary 
between ``frozen'' and ``non-frozen'' regions 
in a random domino-tiling of a large Aztec diamond
is roughly circular in shape.
A rigorous analysis of the behavior of the shuffling algorithm
led to the first proof (by Jockusch, Propp, and Shor \cite{JPS})
of the asymptotic circularity
of the boundary of the frozen region
(the ``arctic circle theorem'').

Meanwhile, Alexandru Ionescu,
also an undergraduate at the time,
discovered a recurrence relation related to shuffling
that permits one to calculate fairly efficiently, 
for any edge $e$ in an (unweighted) Aztec diamond graph,
the probability that a random matching of the graph
contains the edge $e$.
This theorem allowed Gessel, Ionescu, and Propp
(in unpublished work)
to prove a conjecture of Jockusch
concerning the value of this probability
when $e$ is one of the four central edges in the graph.
More significantly, the theorem allowed 
Cohn, Elkies, and Propp \cite{CEP}
to give a detailed analysis of 
the asymptotic behavior of this probability
as a function of the position of the edge $e$
as the size of the Aztec diamond graph goes to infinity.

During this same period, 
it had become clear that (weighted) enumeration
of matchings of weighted Aztec diamond graphs
had relevance to tiling-models other than domino-tiling.
Notably, Bo-Yin Yang had shown \cite{Y}
that the number of ``diabolo-tilings'' of a ``fortress of order $n$''
was given by a certain formula conjectured by Propp
(for more on this, see section 8).
%kludge: fix by hand
Yang's proof made use of Kuperberg's re-formulation of the problem
as a question concerning weighted enumeration of matchings
of a weighted version of the Aztec diamond graph
in which some edges had weight 1
while other edges had weight $\frac12$
(see the end of section 5 of this article
and the longer discussion in section 8).
It was clearly desirable to try to extend
the shuffling algorithm to the context of weighted matchings,
or as physicists would call it, the dimer model
in the presence of non-uniform bond-weights,
but at the time it was unclear how to devise the right extension.
Ciucu's work \cite{Ci2}
went part of the way towards this,
and in particular it gave a very clean combinatorial proof
of Yang's result.
However, it was not clear whether one could
efficiently generate diabolo-tilings
using some extension of domino-shuffling.

The purpose of the present article is to give the details
of just such a generalization of domino-shuffling 
into the general context
of Aztec diamond graphs with weighted edges.
At the same time, my goal is to remove some of the mystery
that hung about the shuffling algorithm in the original exposition
in \cite{EKLP},
and to give a exposition of the work of Ionescu,
which up until now has not been described in the literature
at any useful level of detail.
It should be stressed 
\begin{itemize}
\item[$\cdot$]
that the counting algorithm
(presented in section 2 and analyzed in section 5)
%kludge: fix by hand (see rest of paragraph too)
is essentially a restatement of Mihai Ciucu's 
cellular graph complementation algorithm \cite{Ci2},
\item[$\cdot$]
that the probability computation algorithm
(presented in section 3 and analyzed in section 6)
is a reasonably straightforward generalization
of Ionescu's unpublished algorithm for
the unweighted case,
\item[$\cdot$]
and that the random generation algorithm
(presented in section 4 and analyzed in section 7),
although algebraically more complicated,
represents no conceptual advance over
the unweighted version of shuffling presented
by Kuperberg and Propp.
\end{itemize}
I think that the major contribution offered by this paper
is not any one of these algorithms in isolation
but the way they fit together in a uniform framework.

The essential tool that makes generalized shuffling work
is a principle first communicated to me by Kuperberg,
which is very similar to tricks common in
the literature on exactly solvable lattice models.
This principle is a lemma that asserts a relationship between
the dimer model on one graph
and the dimer model on another,
where the two graphs differ only in that
a small patch of one graph (sometimes called a ``city'')
has been slightly modified in a particular way
(a process sometimes called ``urban renewal'').
Urban renewal is a powerful trick,
especially when used in combination with an even more trivial trick
called vertex splitting/merging.
(Such graph-rewriting rules are not new to the subject
of enumeration of matchings;
see for instance the article of 
Colbourn, Provan, and Vertigan \cite{CPV}
for a very general approach that uses the ``wye-delta'' lemma
in place of the ``urban renewal'' lemma.)
Urban renewal, applied in $n^2$ locations
in an Aztec diamond of order $n$,
essentially converts it into an Aztec diamond of order $n-1$.
In this way, a relation is established
between matchings of $A_n$ and matchings of $A_{n-1}$.
In particular, one can reduce the weighted enumeration 
of matchings of a weighted Aztec diamond graph of order $n$ 
to a (differently) weighted enumeration of matchings
of the Aztec diamond graph of order $n-1$.

The results described in this article
were first communicated by means of
several long email messages I sent out 
to a number of colleagues in 1996.
I am greatly indebted to Greg Kuperberg,
who in the Fall of 2000 turned these messages
into the first draft of this article,
and who in particular created most of the illustrations
(thereby introducing me to the joys of {\tt{pstricks}}).
Also, Harald Helfgott's program {\tt ren}
(currently available from {\tt http://www.math.wisc.edu/$\sim$propp/};
see the files {\tt ren.c}, {\tt ren.h}, and {\tt ren.html})
was the first implementation of the general algorithm,
and it facilitated several useful discoveries,
including phenomena associated with fortresses \cite{Ke2}.
Helfgott and Ionescu and Iyengar were three 
among many undergraduate research assistants
whose participation has contributed to my work on tilings;
the other members of the Tilings Research Group 
(most of whom were undergraduates at the time
the research was done)
were Pramod Achar, Karen Acquista, Josie Ammer, Federico Ardila,
Rob Blau, Matt Blum, Ruth Britto-Pacumio, Constantin Chiscanu,
Henry Cohn, Chris Douglas, Edward Early, Marisa Gioioso,
David Gupta, Sharon Hollander, 
Julia Khodor, Neelakantan Krishnaswami,
Eric Kuo, Ching Law, Andrew Menard, Alyce Moy, Ben Raphael,
Vis Taraz, Jordan Weitz, Ben Wieland, Lauren Williams,
David Wilson, Jessica Wong, Jason Woolever, and Laurence Yogman. 
I thank Chen Zeng,
who has made use of the generalized shuffling algorithm \cite{ZLH}
in his own work on
and thereby encouraged me to write up this algorithm
for publication.
Lastly, I thank the anonymous referee,
whose careful reading and helpful comments
have made this a better article in every way.

\subsection{Two examples}

Here are two illustrations
of the flexibility of the procedures
described in this article.
The figure below shows a subgraph of
the Aztec diamond graph $A_5$.
This can be thought of as an edge-weighting
of the Aztec diamond graph of order 5
in which the marked edges are assigned weight 1
and the remaining (absent) edges are assigned weight 0.
$$
\pspicture(-1.8,-1.8)(1.8,1.8)
\psset{xunit=.3cm,yunit=.3cm}
\psline(-5,0)(0,5)
\psline(-4,-1)(1,4)
\psline(-3,-2)(2,3)
\psline(-2,-3)(3,2)
\psline(-1,-4)(4,1)
\psline(0,-5)(5,0)
\psline(-5,0)(0,-5)
\psline(-4,1)(1,-4)
\psline(-3,2)(2,-3)
\psline(-2,3)(3,-2)
\psline(-1,4)(4,-1)
\psline(0,5)(5,0)
\psline(-5,-4)(-4,-5)
\psline(-5,-2)(-4,-3)
\psline(-3,-4)(-2,-5)
\psline(5,-4)(4,-5)
\psline(5,-2)(4,-3)
\psline(3,-4)(2,-5)
\psline(-5,4)(-4,5)
\psline(-5,2)(-4,3)
\psline(-3,4)(-2,5)
\psline(5,4)(4,5)
\psline(5,2)(4,3)
\psline(3,4)(2,5)
\endpspicture
$$
It is easy to see that 
the twelve isolated edges all are ``forced'',
in the sense that every matching of the graph
must contain them.
When these forced edges are pruned from the graph,
what remains is the 6-by-6 square grid.
More generally, for any $n$,
one can assign a $0,1$-weighting to the edges
of the Aztec diamond graph of order $2n-1$
so that the matchings of positive weight (i.e., weight 1)
correspond to the matchings of the $2n$-by-$2n$ square grid.
One can use this correspondence in order 
to count matchings of the square grid,
determine inclusion-probabilities for individual edges,
and generate random matchings
(for a technical caveat, see section 9, item 1).

The second example concerns matchings of graphs called
``hexagon honeycomb graphs''.
These graphs have been studied by chemists
as examples of generalized benzene-like hydrocarbons \cite{CG},
and they also
have connections to the study of plane partitions \cite{CLP}.
To construct such a graph, start with a hexagon
with all internal angles measuring 120 degrees
and with sides of respective lengths $a,b,c,a,b,c$,
where $a$, $b$, and $c$ are non-negative integers,
and divide it (in the unique way) into
unit equilateral triangles,
as shown below with $a=b=c=2$.
$$
\pspicture(-1.8,-1.8)(1.8,1.8)
\psset{xunit=.3cm,yunit=.3cm}
\psline(-\fourx,0)(-\twox,6)
\psline(-\threex,-3)(0,6)
\psline(-\twox,-6)(\twox,6)
\psline(0,-6)(\threex,3)
\psline(\twox,-6)(\fourx,0)
\psline(-\fourx,0)(-\twox,-6)
\psline(-\threex,3)(0,-6)
\psline(-\twox,6)(\twox,-6)
\psline(0,6)(\threex,-3)
\psline(\twox,6)(\fourx,0)
\psline(-\twox,6)(\twox,6)
\psline(-\threex,3)(\threex,3)
\psline(-\fourx,0)(\fourx,0)
\psline(-\threex,-3)(\threex,-3)
\psline(-\twox,-6)(\twox,-6)
\endpspicture
$$
Let $V$ be the set of triangles,
and let $E$ be the set of pairs of triangles
sharing an edge.
(Pictorially, we may represent the elements of $V$
by dots centered in the respective triangles,
and the elements of $E$ by segments joining
elements of $V$ at unit distance.)
The graph $(V,E)$ is the hexagon honeycomb graph
$H_{a,b,c}$.
Here, for instance, is the
hexagon honeycomb graph $H_{2,2,2}$:
$$
\pspicture(-1.8,-1.8)(1.8,1.8)
\psset{xunit=.3cm,yunit=.3cm}
\psline(-\threex,-1)(-\threex,1)
\psline(-\twox,-4)(-\twox,-2)
\psline(-\twox,2)(-\twox,4)
\psline(-\onex,-1)(-\onex,1)
\psline(0,-4)(0,-2)
\psline(0,2)(0,4)
\psline(\onex,-1)(\onex,1)
\psline(\twox,-4)(\twox,-2)
\psline(\twox,2)(\twox,4)
\psline(\threex,-1)(\threex,1)
\psline(-\twox,4)(-\onex,5)
\psline(-\threex,1)(-\twox,2)
\psline(0,4)(\onex,5)
\psline(-\onex,1)(0,2)
\psline(-\twox,-2)(-\onex,-1)
\psline(\onex,1)(\twox,2)
\psline(0,-2)(\onex,-1)
\psline(-\onex,-5)(0,-4)
\psline(\twox,-2)(\threex,-1)
\psline(\onex,-5)(\twox,-4)
\psline(\twox,4)(\onex,5)
\psline(\threex,1)(\twox,2)
\psline(0,4)(-\onex,5)
\psline(\onex,1)(0,2)
\psline(\twox,-2)(\onex,-1)
\psline(-\onex,1)(-\twox,2)
\psline(0,-2)(-\onex,-1)
\psline(\onex,-5)(0,-4)
\psline(-\twox,-2)(-\threex,-1)
\psline(-\onex,-5)(-\twox,-4)
\endpspicture
$$
Perfect matchings of such a graph
correspond to tilings of the $a,b,c,a,b,c$ hexagon
by unit rhombuses with angles of 60 and 120 degrees,
each composed of two of the unit equilateral triangles. 

The following figure shows, illustratively,
how $H_{2,2,2}$
can be embedded in the Aztec diamond graph $A_5$:
$$
\pspicture(-1.8,-1.8)(1.8,1.8)
\psset{xunit=.3cm,yunit=.3cm}
\psline(-5,4)(-4,5)
\psline(-3,4)(-2,5)
\psline(-1,4)(0,5)
\psline(0,3)(1,4)
\psline(2,5)(3,4)
\psline(4,5)(5,4)
\psline(-5,2)(-4,3)
\psline(-3,2)(-2,3)
\psline(2,3)(3,2)
\psline(4,3)(5,2)
\psline(-5,0)(-4,1)
\psline(3,0)(4,1)
\psline(4,-1)(5,0)
\psline(2,-3)(3,-2)
\psline(4,-3)(5,-2)
\psline(0,-5)(1,-4)
\psline(2,-5)(3,-4)
\psline(4,-5)(5,-4)
\psline(-5,-2)(-4,-3)
\psline(-3,0)(-2,-1)
\psline(-1,2)(0,1)
\psline(-5,-4)(-4,-5)
\psline(-3,-2)(-2,-3)
\psline(-1,0)(0,-1)
\psline(1,2)(2,1)
\psline(-3,-4)(-2,-5)
\psline(-1,-2)(0,-3)
\psline(1,0)(2,-1)
\psline(-5,-2)(-1,2)
\psline(-5,-4)(1,2)
\psline(-4,-5)(2,1)
\psline(-2,-5)(2,-1)
\endpspicture
$$
More generally, for any $a,b,c$,
one can assign a $0,1$-weighting to the edges
of a suitably large Aztec diamond graph
so that the matchings of positive weight (i.e., weight 1)
correspond to the matchings of $H_{a,b,c}$.
One can use this correspondence in order 
to count matchings of the honeycomb graph,
determine inclusion-probabilities for individual edges,
and generate random matchings
(once again subject to the technical caveat
discussed at the beginning of section 9).


\subsection{Evaluation and comparison of the algorithms}

I have not done a rigorous study of the running-times
of these algorithms under realistic assumptions,
but if one makes the (unrealistic) assumption
that arithmetic operations take constant time
(regardless of the complexity of the numbers involved),
then it is easy to see that the most straightforward
implementation of generalized shuffling,
when applied in an Aztec diamond of order $n$,
takes time roughly $n^3$
(ignoring factors of $\log n$).
We have found that in practice, shuffling is extremely efficient.
The physicist Zeng
has applied the algorithm to the study of the dimer model
in the presence of random edge-weights \cite{ZLH}. 

Alternative methods of enumerating matchings of graphs
are legion;
the simplest method that applies to all planar graphs
is the Pfaffian method of Kasteleyn \cite{Ka},
and there is a variant due to Percus \cite{Pe}
(the permanent-determinant method)
that applies when the graph is bipartite.
For the special case of 
enumerating matchings of Aztec diamond graphs,
there are close to a dozen different
(or at least different-looking) proofs
in the literature.
One that is particularly worthy of mention
is the recent condensation algorithm of Eric Kuo \cite{Kuo}.
Kuo's algorithm appears to be closely related
to the algorithm presented here,
although I have not worked out the details
of the correspondence.
It is also worth remarking upon
the resemblance between Kuo's basic bilinear relation
and the bilinear relation that appears
in section 6
%kludge; renumber by hand
of this article;
both relations are proved in similar ways. 
    
Once one knows how to count matchings of graphs
(or, in the weighted case, to sum the weights
of all the matchings),
there is a trivial way to use this to compute
edge-inclusion probabilities:
apply the counting-algorithm to both the original graph
and the graph from which a selected edge
has been deleted (along with its two endpoints).
The ratio of these (weighted) counts
gives the desired probability.
If one wants to compute only a single edge-inclusion probability,
this method is quite efficient,
and if one uses Kasteleyn's approach,
one need only calculate two Pfaffians;
however, if one wants to compute all edge-inclusion probabilities,
it is wasteful to compute all the Pfaffians
independently of one another,
since the different subgraphs are all very similar.
Wilson \cite{W}
shows how one can organize the calculation more efficiently,
exploiting the similarities between the subgraphs.
I believe that Wilson's algorithm and the approach given here
are likely to be roughly equivalent
in terms of computational difficulty
and numerical stability.
The new approach has the virtue
of being much simpler to code.

Once one knows how to compute edge-inclusion probabilities,
generating a random matching is not hard:
one can cycle through the set of edges,
making decisions about whether to include or not include an edge
in accordance with the associated inclusion-probability
(whose value in general depends on the outcome
of earlier decisions).
The na{}ive way of implementing this,
like the na{}ive way of computing all the inclusion probabilities
in parallel,
requires many determinant-evaluations
or Pfaffian-evaluations
of highly similar matrices;
as in the case of the previous paragraph,
Wilson \cite{W} has shown how to use this
to increase efficiency, resulting in
an $O(N^{1.5})$ algorithm,
where $N$ is the number of vertices.
Note that in the case of Aztec diamonds,
$N=O(n^2)$ and $N^{1.5}=O(n^3)$,
so this is the same approximate running-time
as the algorithm given in this article.
No algorithm faster than Wilson's is known.

\subsection{Overview of article}

%kludged section numbers: fix by hand
The layout of the rest of the article is as follows.
Sections 2 through 7 correspond to the original six installments
of the 1996 e-mail version of the article.
Sections 2 through 4 give algorithms for
weighted enumeration, computation of probabilities,
and random generation;
sections 5 through 7 give the proofs that
these algorithms are valid.
The expository strategy is to use examples wherever possible,
rather than resort to descriptions of the general situation,
especially where this might entail cumbersome notation.
Section 8 applies the methods of the article
to the study of diabolo-tilings of fortresses.
Section 9 concludes the article with a summary
and some open problems.

\section{Computing weight-sums: the algorithm}

Here is the rule (to be immediately followed by an example)
for finding the sum of the weights of all the matchings
of an Aztec diamond graph: 
Given an Aztec diamond graph of order $n$ 
whose edges are marked with weights, 
first decompose the graph into $n^2$ 4-cycles 
(to be called ``cells'' following Mihai Ciucu's coinage \cite{Ci1}), 
and then replace each marked cell
$$
\pspicture(-1,-1)(1,1)
\pspolygon(-1,0)(0,1)(1,0)(0,-1)
\rput[br](-.55, .55){$w$} \rput[bl](.55, .55){$x$}
\rput[tr](-.55,-.55){$y$} \rput[tl](.55,-.55){$z$}
\endpspicture
$$
by the marked cell
$$
\pspicture(-1,-1)(1,1)
\pspolygon(-1,0)(0,1)(1,0)(0,-1)
\rput[br](-.55, .55){$z/(wz+xy)$} \rput[bl](.55, .55){$y/(wz+xy)$}   
\rput[tr](-.55,-.55){$x/(wz+xy)$} \rput[tl](.55,-.55){$w/(wz+xy)$}
\endpspicture
$$
and strip away the outer flank of edges, 
so that an edge-marked Aztec diamond graph of order $n-1$ remains.  
Then (as will be shown in section 5)
%kludge: fix by hand 
the sum of the weights of the matchings of the graph of order $n$ 
equals the sum of the weights of the matchings 
of the graph of order $n-1$ 
times the product of the $n^2$
(different) factors of the form $wz+xy$
(``cell-factors'').  
So, if you perform the reduction process $n$ times, 
obtaining in the end the Aztec diamond of order $0$ 
(for which the sum of the weights of the matchings is $1$), 
you will find that the weighted sum of the matchings of 
the original graph of order $n$ 
is just the product of
$$n^2 + (n-1)^2 + \ldots + 2^2 + 1^2$$
terms, read off from the cells.

Let us try this with the weighted Aztec diamond graph
discussed earlier, in connection with the $4 \times 4$ grid:
$$
\pspicture(-3,-3)(3,3)
\pspolygon(-3,-2)(2,3)(3,2)(-2,-3)
\pspolygon(-3,0)(0,3)(3,0)(0,-3)
\pspolygon(-3,2)(-2,3)(3,-2)(2,-3)
\rput[tl](-2.45,2.45){1} \rput[tr](-1.55,2.45){0}
\rput[tl](-0.45,2.45){1} \rput[tr]( 0.45,2.45){1}
\rput[tl]( 1.55,2.45){0} \rput[tr]( 2.45,2.45){1}
\rput[bl](-2.45,1.55){0} \rput[br](-1.55,1.55){1}
\rput[bl](-0.45,1.55){1} \rput[br]( 0.45,1.55){1}
\rput[bl]( 1.55,1.55){1} \rput[br]( 2.45,1.55){0}
\rput[tl](-2.45,0.45){1} \rput[tr](-1.55,0.45){1}
\rput[tl](-0.45,0.45){1} \rput[tr]( 0.45,0.45){1}
\rput[tl]( 1.55,0.45){1} \rput[tr]( 2.45,0.45){1}
\rput[bl](-2.45,-0.45){1} \rput[br](-1.55,-0.45){1}
\rput[bl](-0.45,-0.45){1} \rput[br]( 0.45,-0.45){1}
\rput[bl]( 1.55,-0.45){1} \rput[br]( 2.45,-0.45){1}
\rput[tl](-2.45,-1.55){0} \rput[tr](-1.55,-1.55){1}
\rput[tl](-0.45,-1.55){1} \rput[tr]( 0.45,-1.55){1}
\rput[tl]( 1.55,-1.55){1} \rput[tr]( 2.45,-1.55){0}
\rput[bl](-2.45,-2.45){1} \rput[br](-1.55,-2.45){0}
\rput[bl](-0.45,-2.45){1} \rput[br]( 0.45,-2.45){1}
\rput[bl]( 1.55,-2.45){0} \rput[br]( 2.45,-2.45){1}
\endpspicture
$$
First we apply the replacement rule described above:
$$
\pspicture(-3,-3)(3,3)
\pspolygon(-3,-2)(2,3)(3,2)(-2,-3)
\pspolygon(-3,0)(0,3)(3,0)(0,-3)
\pspolygon(-3,2)(-2,3)(3,-2)(2,-3)
\rput[tl](-2.45,2.45){1} \rput[tr](-1.55,2.45){0}
\rput[tl](-0.45,2.45){\half} \rput[tr]( 0.45,2.45){\half}
\rput[tl]( 1.55,2.45){0} \rput[tr]( 2.45,2.45){1}
\rput[bl](-2.45,1.55){0} \rput[br](-1.55,1.55){1}
\rput[bl](-0.45,1.55){\half} \rput[br]( 0.45,1.55){\half}
\rput[bl]( 1.55,1.55){1} \rput[br]( 2.45,1.55){0}
\rput[tl](-2.45,0.45){\half} \rput[tr](-1.55,0.45){\half}
\rput[tl](-0.45,0.45){\half} \rput[tr]( 0.45,0.45){\half}
\rput[tl]( 1.55,0.45){\half} \rput[tr]( 2.45,0.45){\half}
\rput[bl](-2.45,-0.45){\half} \rput[br](-1.55,-0.45){\half}
\rput[bl](-0.45,-0.45){\half} \rput[br]( 0.45,-0.45){\half}
\rput[bl]( 1.55,-0.45){\half} \rput[br]( 2.45,-0.45){\half}
\rput[tl](-2.45,-1.55){0} \rput[tr](-1.55,-1.55){1}
\rput[tl](-0.45,-1.55){\half} \rput[tr]( 0.45,-1.55){\half}
\rput[tl]( 1.55,-1.55){1} \rput[tr]( 2.45,-1.55){0}
\rput[bl](-2.45,-2.45){1} \rput[br](-1.55,-2.45){0}
\rput[bl](-0.45,-2.45){\half} \rput[br]( 0.45,-2.45){\half}
\rput[bl]( 1.55,-2.45){0} \rput[br]( 2.45,-2.45){1}
\endpspicture
$$
Next we strip away the outer layer (note that some of the values
computed at the previous step are simply thrown away, so that
it is not in fact strictly necessary to have computed them):
$$
\pspicture(-2,-2)(2,2)
\pspolygon(-2,-1)(1,2)(2,1)(-1,-2)
\pspolygon(-2,1)(-1,2)(2,-1)(1,-2)
\rput[tl](-1.45,1.45){1} \rput[tr](-0.55,1.45){\half}
\rput[tl](0.55,1.45){\half} \rput[tr](1.45,1.45){1}
\rput[bl](-1.45,0.55){\half} \rput[br](-0.55,0.55){\half}
\rput[bl](0.55,0.55){\half} \rput[br](1.45,0.55){\half}
\rput[tl](-1.45,-0.55){\half} \rput[tr](-0.55,-0.55){\half}
\rput[tl](0.55,-0.55){\half} \rput[tr](1.45,-0.55){\half}
\rput[bl](-1.45,-1.45){1} \rput[br](-0.55,-1.45){\half}
\rput[bl](0.55,-1.45){\half} \rput[br](1.45,-1.45){1}
\endpspicture
$$
Now we do it again (only this time I will not bother to depict
the weights that end up getting thrown away):
$$
\pspicture(-1,-1)(1,1)
\pspolygon(-1,0)(0,1)(1,0)(0,-1)
\rput[br](-.55, .55){4/3} \rput[bl](.55, .55){4/3}
\rput[tr](-.55,-.55){4/3} \rput[tl](.55,-.55){4/3}
\endpspicture
$$
We do it one more time, and we obtain the empty Aztec diamond.

Now we multiply together all the cell-factors:
$$2^5  \times (3/4)^4 \times (32/9) = 36.$$

A different example arises when 
the cells of an Aztec diamond of order $n$
are alternately colored white and black,
with all the edges in the white cells
being assigned one weight ($a$)
and all the edges in the black cells
being assigned another weight ($b$).
In this case, a single application of the algorithm
gives an Aztec diamond of order $n-1$
in which there are again edges of two different weights,
only now the different-weighted edges
are intermixed in the cells.
However, if one repeats the algorithm again,
one gets an Aztec diamond of order $n-2$
in which the alternation of the two weights
is as in the original graph.
In this fashion, it is possible to express
the sum of the weights of all the matchings of the graph
in terms of cell-factors equal to 
$2a^2$, $2b^2$, and $a^2+b^2$.
Indeed, by specializing these weights with $a=1$ and $b=\frac12$,
we get a very simple proof of the ``powers-of-5'' formula
proved by Yang \cite{Y},
similar to the proof given by Ciucu \cite{Ci2}.

\section{Computing edge-inclusion probabilities: the algorithm}

Let us assume that non-negative real weights have been assigned
to the edges of an Aztec diamond graph,
and let us define the weight of a matching of the graph
as the product of the weights of the constituent edges.
Assume that the weighting of the edges is such that
there exists at least one matching of non-zero weight.
Then the weighting of the matchings
induces a probability distribution 
on the set of matchings of the graph,
in which the probability of a particular matching is proportional
to the weight of that matching.
This is most natural in the case where all edges
have weight 0 or weight 1;
then one is looking at the uniform distribution on
the set of all matchings of the subgraph
consisting of the edges of weight 1.
In any case, the probability distribution is well-defined,
so it makes sense to ask,
what is the probability that a random matching
(chosen relative to the aforementioned probability distribution)
will contain some particular edge $e$?
Here we present a scheme that simultaneously answers this question
for all edges $e$ of the graph.

What we do is thread our way back 
through the reduction process described in the previous section, 
%kludge: fix by hand 
starting from order 0 and working our way back up to order $n$,
computing the edge probability in successively larger and larger 
weighted Aztec diamonds graphs;
along the way we make use of the cell-weights 
that were computed during the reduction process.  
Suppose we have computed edge probabilities for
the weighted graph of order $n-1$.  
To derive the edge probabilities
for the weighted graph of order $n$, 
we embed the smaller graph in
the larger (concentrically), 
divide the larger graph into $n^2$ cells,
and swap the numbers belonging to edges 
on opposite sides of a cell
(the example below will make this clearer).  
When we have done this,
the numbers on the edges are (typically) 
not yet the true probabilities, 
but they can be regarded as approximations to them, 
in the sense that we can add a slightly more complicated
correction term that makes the ``approximate'' formulas exact.  
Let us zoom in on a particular cell to see
how it works: 
Consider the typical cell
$$
\pspicture(-1,-1)(1,1)
\pspolygon(-1,0)(0,1)(1,0)(0,-1)
\rput[br](-.55, .55){$w$} \rput[bl](.55, .55){$x$}
\rput[tr](-.55,-.55){$y$} \rput[tl](.55,-.55){$z$}
\endpspicture
$$
and suppose that the edges with weights $w$, $x$, $y$, and $z$ 
(before the swapping has taken place) 
have been given ``approximate'' probabilities
$p$, $q$, $r$, and $s$, respectively.  
Then the \emph{exact} probabilities for
these respective edges are
%\begin{eqnarray*}
%s &=& \frac{(1-p-q-r-s)wz}{wz+xy} \\  
%r &=& \frac{(1-p-q-r-s)xy}{wz+xy} \\
%q &=& \frac{(1-p-q-r-s)xy}{wz+xy} \\ 
%p &=& \frac{(1-p-q-r-s)wz}{wz+xy}.
%\end{eqnarray*}
\begin{align*}
&s + \frac{(1-p-q-r-s)wz}{wz+xy} && r + \frac{(1-p-q-r-s)xy}{wz+xy} \\
&q + \frac{(1-p-q-r-s)xy}{wz+xy} && p + \frac{(1-p-q-r-s)wz}{wz+xy}.
\end{align*}
The number $1-p-q-r-s$ will be called the \emph{deficit}
associated with that cell, 
and in the context of the four preceding inset expressions,
it is called the \emph{(net) creation rate};
the numbers $wz/(wz+xy)$ and $xy/(wz+xy)$ 
are called \emph{(net) creation biases}.

Applying this to the $4 \times 4$ grid graph, 
we find that for the weighted Aztec graphs 
of orders $1$, $2$, and $3$ that we found (in reverse order)
when we \emph{counted} the matchings, 
the edge-probabilities are as follows:
For the order $1$ graph, we have
$$
\pspicture(-1,-1)(1,1)
\pspolygon(-1,0)(0,1)(1,0)(0,-1)
\rput[br](-.55, .55){\half} \rput[bl](.55, .55){\half}
\rput[tr](-.55,-.55){\half} \rput[tl](.55,-.55){\half}
\endpspicture
$$
We embed this in the Aztec graph of order $2$:
$$
\pspicture(-2,-2)(2,2)
\pspolygon(-2,-1)(1,2)(2,1)(-1,-2)
\pspolygon(-2,1)(-1,2)(2,-1)(1,-2)
\qdisk(-1,-1){.05} \qdisk(-1,1){.05} \qdisk(1,-1){.05} \qdisk(1,1){.05}
\rput[tl](-1.45,1.45){0} \rput[tr](-0.55,1.45){0}
\rput[tl](0.55,1.45){0} \rput[tr](1.45,1.45){0}
\rput[bl](-1.45,0.55){0} \rput[br](-0.55,0.55){\half}
\rput[bl](0.55,0.55){\half} \rput[br](1.45,0.55){0}
\rput[tl](-1.45,-0.55){0} \rput[tr](-0.55,-0.55){\half}
\rput[tl](0.55,-0.55){\half} \rput[tr](1.45,-0.55){0}
\rput[bl](-1.45,-1.45){0} \rput[br](-0.55,-1.45){0}
\rput[bl](0.55,-1.45){0} \rput[br](1.45,-1.45){0}
\endpspicture
$$
Note that I have put a dot in the middle of each of the four cells.
We swap each number with the number opposite it in its cell:
$$
\pspicture(-2,-2)(2,2)
\pspolygon(-2,-1)(1,2)(2,1)(-1,-2)
\pspolygon(-2,1)(-1,2)(2,-1)(1,-2)
\qdisk(-1,-1){.05} \qdisk(-1,1){.05} \qdisk(1,-1){.05} \qdisk(1,1){.05}
\rput[tl](-1.45,1.45){\half} \rput[tr](-0.55,1.45){0}
\rput[tl](0.55,1.45){0} \rput[tr](1.45,1.45){\half}
\rput[bl](-1.45,0.55){0} \rput[br](-0.55,0.55){0}
\rput[bl](0.55,0.55){0} \rput[br](1.45,0.55){0}
\rput[tl](-1.45,-0.55){0} \rput[tr](-0.55,-0.55){0}
\rput[tl](0.55,-0.55){0} \rput[tr](1.45,-0.55){0}
\rput[bl](-1.45,-1.45){\half} \rput[br](-0.55,-1.45){0}
\rput[bl](0.55,-1.45){0} \rput[br](1.45,-1.45){\half}
\endpspicture
$$
These are the approximate, inexact edge-probabilities.  
To find the exact values, we compute that in each of the four cells 
the deficit $1-p-q-r-s$ is $1/2$.  
The weights on the edges 
(all equal to $1$ or $1/2$ --- see second-to-list figure of section 2) 
give us creation biases
$$(1/2)/(3/4) = 2/3$$
and
$$(1/4)/(3/4) = 1/3.$$
So we increment the $1/2$'s (and the $0$'s that are opposite
them) by
$$(1/2)(2/3) = 1/3,$$
and we increment the other $0$'s by
$$(1/2)(1/3) = 1/6,$$
obtaining
$$
\pspicture(-2,-2)(2,2)
\pspolygon(-2,-1)(1,2)(2,1)(-1,-2)
\pspolygon(-2,1)(-1,2)(2,-1)(1,-2)
\rput[tl](-1.45, 1.45){\small 5/6} \rput[tr](-0.55, 1.45){\small 1/6}
\rput[tl]( 0.55, 1.45){\small 1/6} \rput[tr]( 1.45, 1.45){\small 5/6}
\rput[bl](-1.45, 0.55){\small 1/6} \rput[br](-0.55, 0.55){\small 1/3}
\rput[bl]( 0.55, 0.55){\small 1/3} \rput[br]( 1.45, 0.55){\small 1/6}
\rput[tl](-1.45,-0.55){\small 1/6} \rput[tr](-0.55,-0.55){\small 1/3}
\rput[tl]( 0.55,-0.55){\small 1/3} \rput[tr]( 1.45,-0.55){\small 1/6}
\rput[bl](-1.45,-1.45){\small 5/6} \rput[br](-0.55,-1.45){\small 1/6}
\rput[bl]( 0.55,-1.45){\small 1/6} \rput[br]( 1.45,-1.45){\small 5/6}
\endpspicture
$$
Embed this in the graph of order $3$, 
and swap the numbers in each cell:
$$
\pspicture(-3,-3)(3,3)
\pspolygon(-3,-2)(2,3)(3,2)(-2,-3)
\pspolygon(-3,0)(0,3)(3,0)(0,-3)
\pspolygon(-3,2)(-2,3)(3,-2)(2,-3)
\qdisk(-2,-2){.05}\qdisk(-2, 0){.05}\qdisk(-2, 2){.05}
\qdisk( 0,-2){.05}\qdisk( 0, 0){.05}\qdisk( 0, 2){.05}
\qdisk( 2,-2){.05}\qdisk( 2, 0){.05}\qdisk( 2, 2){.05}
\rput[tl](-2.45, 2.45){\small 5/6} \rput[tr](-1.55, 2.45){0}
\rput[tl](-0.45, 2.45){\small 1/6} \rput[tr]( 0.45, 2.45){\small 1/6}
\rput[tl]( 1.55, 2.45){0} \rput[tr]( 2.45, 2.45){\small 5/6}
\rput[bl](-2.45, 1.55){0} \rput[br](-1.55, 1.55){0}
\rput[bl](-0.45, 1.55){0} \rput[br]( 0.45, 1.55){0}
\rput[bl]( 1.55, 1.55){0} \rput[br]( 2.45, 1.55){0}
\rput[tl](-2.45, 0.45){\small 1/6} \rput[tr](-1.55, 0.45){0}
\rput[tl](-0.45, 0.45){\small 1/3} \rput[tr]( 0.45, 0.45){\small 1/3}
\rput[tl]( 1.55, 0.45){0} \rput[tr]( 2.45, 0.45){\small 1/6}
\rput[bl](-2.45,-0.45){\small 1/6} \rput[br](-1.55,-0.45){0}
\rput[bl](-0.45,-0.45){\small 1/3} \rput[br]( 0.45,-0.45){\small 1/3}
\rput[bl]( 1.55,-0.45){0} \rput[br]( 2.45,-0.45){\small 1/6}
\rput[tl](-2.45,-1.55){0} \rput[tr](-1.55,-1.55){0}
\rput[tl](-0.45,-1.55){0} \rput[tr]( 0.45,-1.55){0}
\rput[tl]( 1.55,-1.55){0} \rput[tr]( 2.45,-1.55){0}
\rput[bl](-2.45,-2.45){\small 5/6} \rput[br](-1.55,-2.45){0}
\rput[bl](-0.45,-2.45){\small 1/6} \rput[br]( 0.45,-2.45){\small 1/6}
\rput[bl]( 1.55,-2.45){0} \rput[br]( 2.45,-2.45){\small 5/6}
\endpspicture
$$
The four corner-cells have deficit $1/6$, 
the other four outer cells have deficit $2/3$ 
and the inner cell has deficit $-1/3$ 
(or surplus $+1/3$).  So we do our adjustments, 
this time with all creation biases equal to $1/2$ 
(except in the corners, 
where the creation biases are $0$ and $1$ ---
see third-to-list figure of section 2): 
$$
\pspicture(-3,-3)(3,3)
\pspolygon(-3,-2)(2,3)(3,2)(-2,-3)
\pspolygon(-3,0)(0,3)(3,0)(0,-3)
\pspolygon(-3,2)(-2,3)(3,-2)(2,-3)
\qdisk(-2,-2){.05}\qdisk(-2, 0){.05}\qdisk(-2, 2){.05}
\qdisk( 0,-2){.05}\qdisk( 0, 0){.05}\qdisk( 0, 2){.05}
\qdisk( 2,-2){.05}\qdisk( 2, 0){.05}\qdisk( 2, 2){.05}
\rput[tl](-2.45, 2.45){1} \rput[tr](-1.55, 2.45){0}
\rput[tl](-0.45, 2.45){\small 1/2} \rput[tr]( 0.45, 2.45){\small 1/2}
\rput[tl]( 1.55, 2.45){0} \rput[tr]( 2.45, 2.45){1}
\rput[bl](-2.45, 1.55){0} \rput[br](-1.55, 1.55){\small 1/6}
\rput[bl](-0.45, 1.55){\small 1/3} \rput[br]( 0.45, 1.55){\small 1/3}
\rput[bl]( 1.55, 1.55){\small 1/6} \rput[br]( 2.45, 1.55){0}
\rput[tl](-2.45, 0.45){\small 1/2} \rput[tr](-1.55, 0.45){\small 1/3}
\rput[tl](-0.45, 0.45){\small 1/6} \rput[tr]( 0.45, 0.45){\small 1/6}
\rput[tl]( 1.55, 0.45){\small 1/3} \rput[tr]( 2.45, 0.45){\small 1/2}
\rput[bl](-2.45,-0.45){\small 1/2} \rput[br](-1.55,-0.45){\small 1/3}
\rput[bl](-0.45,-0.45){\small 1/6} \rput[br]( 0.45,-0.45){\small 1/6}
\rput[bl]( 1.55,-0.45){\small 1/3} \rput[br]( 2.45,-0.45){\small 1/2}
\rput[tl](-2.45,-1.55){0} \rput[tr](-1.55,-1.55){\small 1/6}
\rput[tl](-0.45,-1.55){\small 1/3} \rput[tr]( 0.45,-1.55){\small 1/3}
\rput[tl]( 1.55,-1.55){\small 1/6} \rput[tr]( 2.45,-1.55){0}
\rput[bl](-2.45,-2.45){1} \rput[br](-1.55,-2.45){0}
\rput[bl](-0.45,-2.45){\small 1/2} \rput[br]( 0.45,-2.45){\small 1/2}
\rput[bl]( 1.55,-2.45){0} \rput[br]( 2.45,-2.45){1}
\endpspicture
$$
These are the true edge-inclusion probabilities 
associated with the original graph.  
That is, if we take a uniform random matching 
of the $4 \times 4$ grid, 
these are the probabilities with which we will see 
the respective edges occur in the matching.


\section{Generating a random matching: the algorithm}

Before one can begin to generate random matchings of
a weighted Aztec diamond graph of order $n$, 
one must apply the reduction algorithm used in the counting algorithm,
obtaining weighted Aztec diamond graphs of
orders $n-1$, $n-2$, etc.  
But once this has been done, 
generating random matchings of the graph is quite easy.  
The algorithm is an iterative one: 
starting from a Aztec diamond graph of order $0$, 
one successively generates random matchings 
of the graphs of orders $1$, $2$, $3$, etc., 
using the weights that one computed during the reduction-process.  
At each stage, the probability of seeing any particular matching 
can be shown to be proportional to the weight of that matching 
(where the constant of proportionality naturally changes 
as one progresses to larger and larger Aztec diamond graphs).

Here is how one iteration of the procedure works.  
Given a perfect matching of the Aztec diamond graph of order $k-1$, 
embed the matching inside the Aztec diamond graph of order $k$, 
so that you have a partial matching of an Aztec diamond graph order $k$.  
(Note that the $4$-cycles that were cells in the small graph
become the holes between the cells in the large graph).  
In the new enlarged graph, find all (new) cells 
that contain two matched edges and delete both edges. 
(In \cite{EKLP}, this was called ``destruction''.) 
Then replace each edge in the resulting matching 
with the edge opposite it in its cell.  
(In \cite{EKLP}, this was called ``shuffling'',
although in subsequent talks and articles
I prefer to call this step of the algorithm ``sliding''
and to reserve the term ``shuffling'' for
the compound operation consisting
of ``creation'', ``sliding'', and ``destruction''.)
It can be shown that the complement of the resulting matching 
(that is, the graph that remains when the matched vertices
and all their incident edges are removed) 
can be covered by $4$-cycles in a unique way 
(and it is easy to find this covering 
just by making a one-time scan through the graph).  
Each such $4$-cycle has weights attached to each of its $4$ edges, 
so we can choose a random perfect matching of the 4-cycle
using the weights to determine the respective probabilities 
of the two different ways to match the cycle.
(In \cite{EKLP}, this was called ``creation''.)  
Taking the union of these new edges with
the edges that are already in place, 
we get a perfect matching of the Aztec
diamond graph of order $k$.

Let us see how this works with the $4 \times 4$ grid 
(for which we have already worked out the reduction process).  
To generate a random perfect matching, 
we start with the empty matching of the graph of order 0, 
embed it in the graph of order 1, 
and find that the complementary graph of the empty matching 
is a single 4-cycle, which we match in one of two possible ways. 
In this case,
each of the four edges has weight $4/3$, 
so both matchings have equal likelihood; say we choose
$$
\pspicture(-1,-1)(1,1)
\psline(-1,0)(0,1)\psline(0,-1)(1,0)
\qdisk(0,0){.05} \odisk( 1,0){.1} \odisk(-1,0){.1}
\odisk( 0,1){.1} \odisk( 0,-1){.1}
\endpspicture
$$
(Here we have used open circles to denote the vertices of the graph.)
Now we embed this matching in the Aztec diamond graph of order $2$:
$$
\pspicture(-2,-2)(2,2)
\psline(-1,0)(0,1)\psline(0,-1)(1,0)
\qdisk(-1,-1){.05}\qdisk(1,-1){.05}
\qdisk(-1,1){.05}\qdisk(1,1){.05}
\odisk(-1,2){.1} \odisk( 1,2){.1}
\odisk(-2,1){.1} \odisk( 0,1){.1} \odisk( 2,1){.1}
\odisk(-1,0){.1} \odisk( 1,0){.1}
\odisk(-2,-1){.1} \odisk( 0,-1){.1} \odisk( 2,-1){.1}
\odisk(-1,-2){.1} \odisk( 1,-2){.1}
\endpspicture
$$
Neither of the two edges needs to be destroyed, because they belong
to different cells.  Replacing each by the opposite edge in its cell,
we get
$$
\pspicture(-2,-2)(2,2)
\psline(-2,1)(-1,2)\psline(2,-1)(1,-2)
\qdisk(-1,-1){.05}\qdisk(1,-1){.05}
\qdisk(-1,1){.05}\qdisk(1,1){.05}
\odisk(-1,2){.1} \odisk( 1,2){.1}
\odisk(-2,1){.1} \odisk( 0,1){.1} \odisk( 2,1){.1}
\odisk(-1,0){.1} \odisk( 1,0){.1}
\odisk(-2,-1){.1} \odisk( 0,-1){.1} \odisk( 2,-1){.1}
\odisk(-1,-2){.1} \odisk( 1,-2){.1}
\endpspicture
$$
The complementary graph has a unique cover by $4$-cycles:
$$
\pspicture(-2,-2)(2,2)
\pspolygon(-2,-1)(-1,0)(0,-1)(-1,-2)
\pspolygon(2,1)(1,0)(0,1)(1,2)
\qdisk(-1,-1){.05}\qdisk(1,-1){.05}
\qdisk(-1,1){.05}\qdisk(1,1){.05}
\odisk(-1,2){.1} \odisk( 1,2){.1}
\odisk(-2,1){.1} \odisk( 0,1){.1} \odisk( 2,1){.1}
\odisk(-1,0){.1} \odisk( 1,0){.1}
\odisk(-2,-1){.1} \odisk( 0,-1){.1} \odisk( 2,-1){.1}
\odisk(-1,-2){.1} \odisk( 1,-2){.1}
\endpspicture
$$  
In each $4$-cycle, three edges have weight $1/2$ 
and one has weight $1$,
so we are twice as likely to see the one of the matchings as the other.  
Let us suppose that when we choose matchings with suitable bias, 
we get the more likely of the two matchings in both cells 
(as happens $4/9$ of the time).  Thus we have
$$
\pspicture(-2,-2)(2,2)
\qdisk(-1,-1){.05}\qdisk(1,-1){.05}
\qdisk(-1,1){.05}\qdisk(1,1){.05}
\psline(-2,1)(-1,2)\psline(2,1)(1,2)\psline(1,0)(0,1)
\psline(2,-1)(1,-2)\psline(-2,-1)(-1,-2)\psline(-1,0)(0,-1)
\odisk(-1,2){.1} \odisk( 1,2){.1}
\odisk(-2,1){.1} \odisk( 0,1){.1} \odisk( 2,1){.1}
\odisk(-1,0){.1} \odisk( 1,0){.1}
\odisk(-2,-1){.1} \odisk( 0,-1){.1} \odisk( 2,-1){.1}
\odisk(-1,-2){.1} \odisk( 1,-2){.1}
\endpspicture
$$
Now we embed the matching in the graph of order $3$:
$$
\pspicture(-3,-3)(3,3)
\qdisk(-2,2){.05}\qdisk(0,2){.05}\qdisk(2,2){.05}
\qdisk(-2,0){.05}\qdisk(0,0){.05}\qdisk(2,0){.05}
\qdisk(-2,-2){.05}\qdisk(0,-2){.05}\qdisk(2,-2){.05}
\psline(-2,1)(-1,2)\psline(2,1)(1,2)\psline(1,0)(0,1)
\psline(2,-1)(1,-2)\psline(-2,-1)(-1,-2)\psline(-1,0)(0,-1)
\odisk(-2,3){.1} \odisk( 0,3){.1} \odisk( 2,3){.1}
\odisk(-3,2){.1} \odisk(-1,2){.1} \odisk( 1,2){.1} \odisk( 3,2){.1}
\odisk(-2,1){.1} \odisk( 0,1){.1} \odisk( 2,1){.1}
\odisk(-3,0){.1} \odisk(-1,0){.1} \odisk( 1,0){.1} \odisk( 3,0){.1}
\odisk(-2,-1){.1} \odisk( 0,-1){.1} \odisk( 2,-1){.1}
\odisk(-3,-2){.1} \odisk(-1,-2){.1} \odisk( 1,-2){.1} \odisk( 3,-2){.1}
\odisk(-2,-3){.1} \odisk( 0,-3){.1} \odisk( 2,-3){.1}
\endpspicture
$$
This time we must delete the two central edges, 
because they belong to the same cell.  
After we have done this, 
we replace each of the four remaining edges 
with the opposite edge of its $4$-cycle, obtaining
$$
\pspicture(-3,-3)(3,3)
\qdisk(-2,2){.05}\qdisk(0,2){.05}\qdisk(2,2){.05}
\qdisk(-2,0){.05}\qdisk(0,0){.05}\qdisk(2,0){.05}
\qdisk(-2,-2){.05}\qdisk(0,-2){.05}\qdisk(2,-2){.05}
\psline(-3,2)(-2,3)\psline(2,3)(3,2)
\psline(-3,-2)(-2,-3)\psline(2,-3)(3,-2)
\odisk(-2,3){.1} \odisk( 0,3){.1} \odisk( 2,3){.1}
\odisk(-3,2){.1} \odisk(-1,2){.1} \odisk( 1,2){.1} \odisk( 3,2){.1}
\odisk(-2,1){.1} \odisk( 0,1){.1} \odisk( 2,1){.1}
\odisk(-3,0){.1} \odisk(-1,0){.1} \odisk( 1,0){.1} \odisk( 3,0){.1}
\odisk(-2,-1){.1} \odisk( 0,-1){.1} \odisk( 2,-1){.1}
\odisk(-3,-2){.1} \odisk(-1,-2){.1} \odisk( 1,-2){.1} \odisk( 3,-2){.1}
\odisk(-2,-3){.1} \odisk( 0,-3){.1} \odisk( 2,-3){.1}
\endpspicture
$$
There is a unique cover of the complement by $4$-cycles:
$$
\pspicture(-3,-3)(3,3)
\qdisk(-2,2){.05}\qdisk(0,2){.05}\qdisk(2,2){.05}
\qdisk(-2,0){.05}\qdisk(0,0){.05}\qdisk(2,0){.05}
\qdisk(-2,-2){.05}\qdisk(0,-2){.05}\qdisk(2,-2){.05}
\pspolygon(-3,0)(-2,1)(-1,0)(-2,-1)
\pspolygon(3,0)(2,-1)(1,0)(2,1)
\pspolygon(0,-3)(1,-2)(0,-1)(-1,-2)
\pspolygon(0,3)(-1,2)(0,1)(1,2)
\odisk(-2,3){.1} \odisk( 0,3){.1} \odisk( 2,3){.1}
\odisk(-3,2){.1} \odisk(-1,2){.1} \odisk( 1,2){.1} \odisk( 3,2){.1}
\odisk(-2,1){.1} \odisk( 0,1){.1} \odisk( 2,1){.1}
\odisk(-3,0){.1} \odisk(-1,0){.1} \odisk( 1,0){.1} \odisk( 3,0){.1}
\odisk(-2,-1){.1} \odisk( 0,-1){.1} \odisk( 2,-1){.1}
\odisk(-3,-2){.1} \odisk(-1,-2){.1} \odisk( 1,-2){.1} \odisk( 3,-2){.1}
\odisk(-2,-3){.1} \odisk( 0,-3){.1} \odisk( 2,-3){.1}
\endpspicture
$$
As it happens, each edge in the complement has weight $1$ 
in the (original) weighted Aztec diamond of order $3$, 
so we can use a fair coin to decide 
how to match each of the $4$-cycles.

\section{Computing weight-sums: the proof}

To prove the claim, 
we begin with a lemma 
(the ``urban renewal lemma"):
If you have a weighted graph $G$
that contains the local pattern
$$
\pspicture(-2.5,-2.5)(2.5,2.5)
\pspolygon(-1,0)(0,1)(1,0)(0,-1)
\psline(1,0)(2.4,0)\psline(-1,0)(-2.4,0)
\psline(0,1)(0,2.4)\psline(0,-1)(0,-2.4)
\psline(.2,2.4)(0,2)(-.2,2.4)
\psline(.2,-2.4)(0,-2)(-.2,-2.4)
\psline(2.4,.2)(2,0)(2.4,-.2)
\psline(-2.4,.2)(-2,0)(-2.4,-.2)
\rput[br](-.55, .55){$w$} \rput[bl](.55, .55){$x$}
\rput[tr](-.55,-.55){$y$} \rput[tl](.55,-.55){$z$}
\odisk(0,-2){.1} \odisk(0,-1){.1} \odisk(0, 1){.1} \odisk(0, 2){.1}
\odisk(-2,0){.1} \odisk(-1,0){.1} \odisk( 1,0){.1} \odisk( 2,0){.1}
\rput[r](-.2,2){$A$}
\rput[b](-2,.2){$B$}
\rput[b](2,.2){$C$}
\rput[r](-.2,-2){$D$}
\endpspicture
$$
(here $A$,$B$,$C$,$D$ are vertex labels 
and $w$,$x$,$y$,$z$ are edge weights,
with unmarked edges having weight $1$) and you define $G'$ as the
graph you get when you replace this local pattern by
$$
\pspicture(-2.5,-2.5)(2.5,2.5)
\pspolygon(-2,0)(0,2)(2,0)(0,-2)
\psline(2,0)(2.4,0)\psline(-2,0)(-2.4,0)
\psline(0,2)(0,2.4)\psline(0,-2)(0,-2.4)
\psline(.2,2.4)(0,2)(-.2,2.4)
\psline(.2,-2.4)(0,-2)(-.2,-2.4)
\psline(2.4,.2)(2,0)(2.4,-.2)
\psline(-2.4,.2)(-2,0)(-2.4,-.2)
\rput[br](-1.05, 1.05){$w'$} \rput[bl](1.05, 1.05){$x'$}
\rput[tr](-1.05,-1.05){$y'$} \rput[tl](1.05,-1.05){$z'$}
\odisk(0,-2){.1} \odisk(0,2){.1}
\odisk(-2,0){.1} \odisk(2,0){.1}
\rput[r](-.2,2){$A$}
\rput[b](-2,.2){$B$}
\rput[b](2,.2){$C$}
\rput[r](-.2,-2){$D$}
\endpspicture
$$
with
%align
%\begin{eqnarray*}
%w' = z/(wz+xy) && x' = y/(wz+xy) \\
%y' = x/(wz+xy) && z' = w/(wz+xy),
%\end{eqnarray*}
\begin{align*}
w' &= z/(wz+xy) & x' &= y/(wz+xy) \\
y' &= x/(wz+xy) & z' &= w/(wz+xy),
\end{align*}
then the sum of the weights of the matchings of $G$ equals $wz+xy$ times
the sum of the weights of the matchings of $G'$.  The proof will be
by verification:
For each possible subset $S$ of $\{A,B,C,D\}$,
    we will check that
	the total weight of the matchings of $G$ in which
	    the vertices in $S$ are matched with vertices 
    inside the patch
	    and the vertices in $\{A,B,C,D\}\setminus S$ are matched 
    outside the patch
	equals $wz+xy$ times the total weight of the matchings of $G'$ 
    in which the vertices in $S$ are matched with vertices 
    inside the patch
	    and the vertices in $\{A,B,C,D\}\setminus S$ are matched 
    outside the patch.
As it turns out, $10$ of the $2^4=16$ cases
are trivial, and of the remaining $6$, 
four are related by symmetry, 
so it comes down to three cases.

\begin{description}
\item[$\bullet$] $S = \{A,B\}$: 
In this case our matching of $G$ 
matches $A$,$B$ inward and $C$,$D$ outward, 
so it must contain the edge of weight $z$.
This matching of $G$ is associated with a matching of $G'$ 
in which $A$ and $B$ are matched (inward) to each other
via an edge of weight $w'$
and $C$ and $D$ are matched outward just as before.
The ratio of the weight of the (given) matching of $G$
to the (associated) matching of $G'$ is $z/w' = wz+xy$.

\item[$\bullet$] $S = \{A,B,C,D\}$: 
In this case our matching of $G$
matches all four vertices $A,B,C,D$ inward.
This matching is associated with two matchings of $G'$,
one of which matches $A$ with $B$ and $C$ with $D$
and the other of which matches $A$ with $C$ and $B$ with $D$
(all edges outside of the patch remain as before).
If we let $Q$ denote the weight 
of the given matching of $G$,
one of the two derived matchings of $G'$ has weight $w'z'Q$
and the other has weight $x'y'Q$.  
The combined weight of the two matchings is
$$(w'z'+x'y')Q = Q/(wz+xy),$$
so the ratio of the weight of the single (given) matching of $G$
to the two (associated) matchings of $G'$ is $wz+xy$.

\item[$\bullet$] $S = \emptyset$: 
In this case our matching of $G$
matches all four vertices $A,B,C,D$ outward,
and either contains edges $w$ and $z$
or contains edges $x$ and $y$.
These two cases must be lumped together.
Let $Q$ denote the product of the edges
of all the weights of the other edges of the matching
(not counting $w,x,y,z$).
We find that two matchings of $G$, of weight $wzQ$ and $xyQ$, 
are associated with a single matching of $G'$ of weight $Q$.  
The ratio of the weights of the two matchings of $G$
to the single matching of $G'$ is $wz+xy$.
\end{description}

This completes the proof of the lemma.

Now, to prove the Aztec reduction theorem, suppose we have a weighted
Aztec graph of order $n$.
$$
\pspicture(-1.5,-1.5)(1.5,1.5)
\pspolygon(-1.5,-1)(-1,-1.5)(1.5,1)(1,1.5)
\pspolygon(-1.5,0)(0,-1.5)(1.5,0)(0,1.5)
\pspolygon(-1.5,1)(1,-1.5)(1.5,-1)(-1,1.5)
\odisk(-1,1.5){.1}\odisk(0,1.5){.1}\odisk(1,1.5){.1}
\odisk(-1.5,1){.1}\odisk(-.5,1){.1}\odisk(.5,1){.1}\odisk(1.5,1){.1}
\odisk(-1,.5){.1}\odisk(0,.5){.1}\odisk(1,.5){.1}
\odisk(-1.5,0){.1}\odisk(-.5,0){.1}\odisk(.5,0){.1}\odisk(1.5,0){.1}
\odisk(-1,-.5){.1}\odisk(0,-.5){.1}\odisk(1,-.5){.1}
\odisk(-1.5,-1){.1}\odisk(-.5,-1){.1}\odisk(.5,-1){.1}\odisk(1.5,-1){.1}
\odisk(-1,-1.5){.1}\odisk(0,-1.5){.1}\odisk(1,-1.5){.1}
\endpspicture
$$
(Here $n=3$ and the weights are not shown.)
We begin our reduction by splitting each vertex into three
vertices:
$$
\pspicture(-3.5,-3.5)(3.5,3.5)
\psline(-2,2.5)(-2,3.5)\psline(0,2.5)(0,3.5)\psline(2,2.5)(2,3.5)
\psline(2.5,-2)(3.5,-2)\psline(2.5,0)(3.5,0)\psline(2.5,2)(3.5,2)
\multips(-2,-2)(2,0){3}{\multips(0,0)(0,2){3}{
    \psline(-1.5,0)(-.5,0)\psline(0,-1.5)(0,-.5)
    \pspolygon(0,.5)(.5,0)(0,-.5)(-.5,0)
    \odisk(0,.5){.1}\odisk(.5,0){.1}\odisk(0,-.5){.1}\odisk(-.5,0){.1}
    \odisk(0,-1){.1}\odisk(0,-1.5){.1}\odisk(-1,0){.1}\odisk(-1.5,0){.1}}}
\odisk(-2,3){.1}\odisk(0,3){.1}\odisk(2,3){.1}
\odisk(-2,3.5){.1}\odisk(0,3.5){.1}\odisk(2,3.5){.1}
\odisk(3,-2){.1}\odisk(3,0){.1}\odisk(3,2){.1}
\odisk(3.5,-2){.1}\odisk(3.5,0){.1}\odisk(3.5,2){.1}
\endpspicture
$$
It is easy to see that this vertex-splitting does not
change the sums of the weights of the matchings, as long as the
new edges we add are given weight 1.

Now we apply urban renewal in $n^2$ locations 
to get a graph of the form
$$
\pspicture(-3.5,-3.5)(3.5,3.5)
\pspolygon(-3,-2)(2,3)(3,2)(-2,-3)
\pspolygon(-3,0)(0,3)(3,0)(0,-3)
\pspolygon(-3,2)(-2,3)(3,-2)(2,-3)
\psline(-3.5,2)(-3,2)\psline(3,2)(3.5,2)
\psline(-3.5,0)(-3,0)\psline(3,0)(3.5,0)
\psline(-3.5,-2)(-3,-2)\psline(3,-2)(3.5,-2)
\psline(2,-3.5)(2,-3)\psline(2,3)(2,3.5)
\psline(0,-3.5)(0,-3)\psline(0,3)(0,3.5)
\psline(-2,-3.5)(-2,-3)\psline(-2,3)(-2,3.5)
\multips(-3,-2)(0,2){3}{\multips(0,0)(2,0){4}{\odisk(0,0){.1}}}
\multips(-2,-3)(0,2){4}{\multips(0,0)(2,0){3}{\odisk(0,0){.1}}}
\odisk(-3.5,2){.1}\odisk(-3.5,0){.1}\odisk(-3.5,-2){.1}
\odisk( 3.5,2){.1}\odisk( 3.5,0){.1}\odisk( 3.5,-2){.1}
\odisk(2,-3.5){.1}\odisk(0,-3.5){.1}\odisk(-2,-3.5){.1}
\odisk( 2,3.5){.1}\odisk( 0,3.5){.1}\odisk( -2,3.5){.1}
\endpspicture
$$
with new weights $w'$, $x'$, $y'$, $z'$ 
replacing the old weights $w$, $x$, $y$, $z$.
(If one were attempting a literal description of the algorithm,
one would want the weight-variables to have subscripts 
$i,j$ ranging from $1$ to $n$.)
Here is the coup de grace: The pendant edges that we see must
belong to \emph{every} perfect matching of the graph, 
so we can delete them from the graph, 
obtaining an Aztec graph of order $n-1$:
$$
\pspicture(-2,-2)(2,2)
\pspolygon(-2,-1)(1,2)(2,1)(-1,-2)
\pspolygon(-2,1)(-1,2)(2,-1)(1,-2)
\multips(-2,-1)(0,2){2}{\multips(0,0)(2,0){3}{\odisk(0,0){.1}}}
\multips(-1,-2)(0,2){3}{\multips(0,0)(2,0){2}{\odisk(0,0){.1}}}
\endpspicture
$$

The theorem now follows.

One can prove the ``fortress" theorem (see \cite{Ci2})
by similar means.  
Here, the initial graph is
$$
\pspicture(-2.5,-2.5)(2.5,2.5)
\multips(-1,-1.5)(0,1.5){3}{\multips(0,0)(1.5,0){2}{\psline(0,0)(.5,0)}}
\multips(-1.5,-1)(1.5,0){3}{\multips(0,0)(0,1.5){2}{\psline(0,0)(0,.5)}}
\psline(-2.5,-1.5)(-2,-1.5)\psline(-1.5,-2.5)(-1.5,-2)
\psline( 2.5,-1.5)( 2,-1.5)\psline( 1.5,-2.5)( 1.5,-2)
\psline(-2.5, 1.5)(-2, 1.5)\psline(-1.5, 2.5)(-1.5, 2)
\psline( 2.5, 1.5)( 2, 1.5)\psline( 1.5, 2.5)( 1.5, 2)
\multips(-1.5,-1.5)(0,1.5){3}{\multips(0,0)(1.5,0){3}{
    \pspolygon(0,.5)(.5,0)(0,-.5)(-.5,0)
    \odisk(0,.5){.1}\odisk(.5,0){.1}\odisk(0,-.5){.1}\odisk(-.5,0){.1}}}
\odisk(-2.5,-1.5){.1}\odisk(-1.5,-2.5){.1}
\odisk( 2.5,-1.5){.1}\odisk( 1.5,-2.5){.1}
\odisk(-2.5, 1.5){.1}\odisk(-1.5, 2.5){.1}
\odisk( 2.5, 1.5){.1}\odisk( 1.5, 2.5){.1}
\endpspicture
$$
One's first impulse is to remove the pendant edges, 
but it is better still to apply urban renewal 
to every \emph{other} ``city" in this graph.  
Then one gets an Aztec diamond graph in which 
roughly half of the edges have weight $1$ 
and the rest have weight $1/2$,
with the two sorts of cities alternating
in checkerboard fashion. 
The same techniques that were used above can also be applied here 
to allow one to conclude that the number of matchings of such a
graph is a certain power of 5 (or twice a certain power of $5$).  
The ``5" comes from the cell-factor $(1)(1)+(1/2)(1/2)$ 
(when multiplied by $4$), just as (in the unweighted Aztec diamond theorem) 
the ``2" comes from the cell-factor $(1)(1)+(1)(1)$.
In short, the proof of Yang's theorem becomes a near-triviality
(just as it is for Ciucu's method \cite{Ci2}).


\section{Computing edge-inclusion probabilities: the proof}

In this section I will prove that the iterative scheme for
computing these probabilities that was described earlier does in
fact work (at least when all edge-weights are non-vanishing).  
To start things off we will need a lemma:
This lemma is a generalization of a proposition
originally conjectured by Alexandru Ionescu
in the context of Aztec diamond graphs,
and was proved by Propp in 1993 (private e-mail communication).

Let $G$ be a bipartite planar graph
and let $A$,$B$,$C$,$D$ be four vertices of $G$
that form a 4-cycle $ABDC$ bounding a face of $G$:
$$
\pspicture(-2.5,-2.5)(2.5,2.5)
\pspolygon(-2,0)(0,2)(2,0)(0,-2)
\psline(2,0)(2.4,0)\psline(-2,0)(-2.4,0)
\psline(0,2)(0,2.4)\psline(0,-2)(0,-2.4)
\psline(.2,2.4)(0,2)(-.2,2.4)
\psline(.2,-2.4)(0,-2)(-.2,-2.4)
\psline(2.4,.2)(2,0)(2.4,-.2)
\psline(-2.4,.2)(-2,0)(-2.4,-.2)
\odisk(0,-2){.1} \odisk(0,2){.1}
\odisk(-2,0){.1} \odisk(2,0){.1}
\rput[r](-.2,2){$A$}
\rput[b](-2,.2){$B$}
\rput[b](2,.2){$C$}
\rput[r](-.2,-2){$D$}
\endpspicture
$$
Assume the edges of this graph are weighted in some fashion.
Define $G_{AB}$ as the weighted graph obtained 
by deleting vertices $A$ and $B$ 
and all incident edges;
all other edges have the same weight as in $G$. 
Define $G_{AC}$, $G_{BD}$, $G_{CD}$, 
and $G_{ABCD}$ similarly.  
For any edge-weighted graph $H$, let $M(H)$ denote 
the sum of the weights of the matchings of $H$.
Then the identity we will prove is
%One-column version:
$$M(G) M(G_{ABCD}) = M(G_{AB}) M(G_{CD}) + M(G_{AC}) M(G_{BD}).$$
%Two-column version:
%FIX: kludge
%$$M(G) M(G_{ABCD}) = $$
%$$M(G_{AB}) M(G_{CD}) + M(G_{AC}) M(G_{BD}).$$

Note that if we superimpose a matching of $G$ 
and a matching of $G_{ABCD}$, 
we get a multiset of edges of $G$ 
in which vertices $A$,$B$,$C$,$D$ get degree 1 and
every other vertex gets degree 2.  
The same thing happens if we superimpose
a matching of $G_{AB}$ and a matching of $G_{CD}$, 
or a matching of $G_{AC}$ and a matching of $G_{BD}$.  
Call an edge-multiset of this sort a ``near 2-factor" of $G$.  
I will prove that equality holds above by showing that 
each near 2-factor $F$ makes the same contribution 
to the left side as it does to the right side.

Pick a specific near 2-factor $F$ of $G$; 
it consists of $k$ closed loops plus some paths 
that connect up the four vertices 
$A$,$B$,$C$,$D$ in pairs.  
It is impossible that the vertices 
are paired as $\{A,D\}$ and $\{B,C\}$, 
since the graph is planar.
Hence the vertices pair as 
either $\{A,B\}$ and $\{C,D\}$ 
or $\{A,C\}$ and $\{B,D\}$.  
Without loss of generality, 
let us focus on the former case.  
Since $G$ is bipartite, the path from $A$ to $B$ 
will contain an odd number of edges, 
as will the path from $C$ to $D$.
It is easy to verify
the following three claims:
\begin{enumerate}
\item There are $2^k$ ways to split up $F$ 
as a matching of $G$ together with 
a matching of $G_{ABCD}$.
\item There are $2^k$ ways to split up $F$ 
as a matching of $G_{AB}$ together with 
a matching of $G_{CD}$.
\item There are \emph{no} ways to split up $F$ 
as a matching of $G_{AC}$ together with 
a matching of $G_{BD}$.
\end{enumerate}
Moreover, one can check that each near 2-factor 
that pairs the vertices as $\{A,B\}$ and $\{C,D\}$
contributes equal weight to both 
sides of the equation.  
Clearly the same is true for the near 2-factors
that pair the vertices the other way
($A$ with $C$ and $B$ with $D$).
This completes the proof. 

(Note: Another way to prove this lemma
is to use the face that the number of perfect matchings
of a bipartite plane graph with $2n$ vertices
can be written as the determinant of an $n$-by-$n$
Kasteleyn-Percus matrix \cite{Ka} \cite{Pe}.
Then the lemma is seen to be a restatement
of Dodgson condensation (\cite{D}; see also \cite{RR}).

It will be convenient for us to restate this lemma
in a somewhat different form.
Assume that the graph has
at least one matching of positive weight.
Let $w$, $x$, $y$, and $z$ denote the respective weights
of the edges $AB$, $AC$, $BD$, and $CD$,
and let $p$, $q$, $r$, and $s$ denote the probabilities
of these respective edges being included
in a random matching of $G$
(where as usual the probability of an individual matching
is proportional to its weight):
$$
\pspicture(-2.5,-2.5)(2.5,2.5)
\pspolygon(-2,0)(0,2)(2,0)(0,-2)
\psline(2,0)(2.4,0)\psline(-2,0)(-2.4,0)
\psline(0,2)(0,2.4)\psline(0,-2)(0,-2.4)
\psline(.2,2.4)(0,2)(-.2,2.4)
\psline(.2,-2.4)(0,-2)(-.2,-2.4)
\psline(2.4,.2)(2,0)(2.4,-.2)
\psline(-2.4,.2)(-2,0)(-2.4,-.2)
\rput[br](-1.05, 1.05){$w\;\;[p]$} \rput[bl](1.05, 1.05){$x\;\;[q]$}
\rput[tr](-1.05,-1.05){$y\;\;[r]$} \rput[tl](1.05,-1.05){$z\;\;[s]$}
\odisk(0,-2){.1} \odisk(0,2){.1}
\odisk(-2,0){.1} \odisk(2,0){.1}
\rput[r](-.2,2){$A$}
\rput[b](-2,.2){$B$}
\rput[b](2,.2){$C$}
\rput[r](-.2,-2){$D$}
\endpspicture
$$
The probability $P^*$ that a random matching of $G$ 
has an alternating cycle at face $ABDC$
(i.e., either includes edges $AB$ and $CD$
or includes edges $AC$ and $BD$)
is equal to $M(G_{ABCD})(wz+xy)/M(G)$.
Since we have
$p=wM(G_{AB})/M(G)$,
$q=xM(G_{AC})/M(G)$,
$r=yM(G_{BD})/M(G)$, and
$s=zM(G_{CD})/M(G)$,
the preceding lemma tells us that,
in the event that $w$,$x$,$y$,$z$ are all non-zero,
the probability $P^*$ 
is equal to
$(psxy+qrwz)(\frac{1}{xy}+\frac{1}{wz})$.
It follows from this that
the probability that a random matching of $G$ contains
both edge $AB$ and edge $CD$ is $(psxy+qrwz)/xy$, 
while the corresponding probability for edges $AC$ and $BD$ 
is $(psxy+qrwz)/wz$.
(To see that this follows from the formula for $P^*$,
note that their sum is indeed $(wz+xy)(ps/wz+qr/xy)=P^*$,
and that their ratio is $wz/xy$, 
which is the ratio of the weights of any two matchings 
that differ only in that one contains $AB$ and $CD$ 
while the other contains $AC$ and $BD$.)

Now let us go back and give urban renewal a fresh look.  Here are
the graphs $G$ and $G'$, with edges marked with both their weight and
their probability (in the format ``weight [probability]").
Here is $G$:
$$
\pspicture(-2.5,-2.5)(2.5,2.5)
\pspolygon(-1,0)(0,1)(1,0)(0,-1)
\psline(1,0)(2.4,0)\psline(-1,0)(-2.4,0)
\psline(0,1)(0,2.4)\psline(0,-1)(0,-2.4)
\psline(.2,2.4)(0,2)(-.2,2.4)
\psline(.2,-2.4)(0,-2)(-.2,-2.4)
\psline(2.4,.2)(2,0)(2.4,-.2)
\psline(-2.4,.2)(-2,0)(-2.4,-.2)
\rput[br](-.55, .55){$w\;\;[p]$} \rput[bl](.55, .55){$x\;\;[q]$}
\rput[tr](-.55,-.55){$y\;\;[r]$} \rput[tl](.55,-.55){$z\;\;[s]$}
\odisk(0,-2){.1} \odisk(0,-1){.1} \odisk(0, 1){.1} \odisk(0, 2){.1}
\odisk(-2,0){.1} \odisk(-1,0){.1} \odisk( 1,0){.1} \odisk( 2,0){.1}
\rput[r](-.2,2){$A$}
\rput[b](-2,.2){$B$}
\rput[b](2,.2){$C$}
\rput[r](-.2,-2){$D$}
\endpspicture
$$
(The unmarked edges have weight $1$, and their probabilities are
$1-p-q$, $1-q-s$, et cetera.)

Here is $G'$:
$$
\pspicture(-2.5,-2.5)(2.5,2.5)
\pspolygon(-2,0)(0,2)(2,0)(0,-2)
\psline(2,0)(2.4,0)\psline(-2,0)(-2.4,0)
\psline(0,2)(0,2.4)\psline(0,-2)(0,-2.4)
\psline(.2,2.4)(0,2)(-.2,2.4)
\psline(.2,-2.4)(0,-2)(-.2,-2.4)
\psline(2.4,.2)(2,0)(2.4,-.2)
\psline(-2.4,.2)(-2,0)(-2.4,-.2)
\rput[br](-1.05, 1.05){$w'\;\;[p']$} \rput[bl](1.05, 1.05){$x'\;\;[q']$}
\rput[tr](-1.05,-1.05){$y'\;\;[r']$} \rput[tl](1.05,-1.05){$z'\;\;[s']$}
\odisk(0,-2){.1} \odisk(0,2){.1}
\odisk(-2,0){.1} \odisk(2,0){.1}
\rput[r](-.2,2){$A$}
\rput[b](-2,.2){$B$}
\rput[b](2,.2){$C$}
\rput[r](-.2,-2){$D$}
\endpspicture
$$
Recall that we are in the situation where we know $p'$, $q'$, $r'$, and $s'$,
and are trying to compute $p$, $q$, $r$, and $s$.  Recall also that
%align
%\begin{eqnarray*}
%w' = z/(wz+xy) && x' = y/(wz+xy) \\
%y' = x/(wz+xy) && z' = w/(wz+xy).
%\end{eqnarray*}
\begin{align*}
w' &= z/(wz+xy) & x' &= y/(wz+xy) \\
y' &= x/(wz+xy) & z' &= w/(wz+xy).
\end{align*}

Here is our plan: First, we will work out the probabilities of all the
local patterns in $G'$.  Then we will use the urban renewal correspondence
to deduce the probabilities of the local patterns in $G$.  Finally,
we will deduce the probabilities of the individual edges in $G$.

I will write $p'$,$q'$,$r'$,$s'$,$w'$,$x'$,$y'$,$z'$ as
$P$,$Q$,$R$,$S$,$W$,$X$,$Y$,$Z$, to save eye-strain.  
% Keep in mind the motivation that the primed quantities 
% come from a \emph{larger} Aztec diamond graph than the unprimed.
I will also write $\Delta'=XYPS+WZQR$.

Let $S$ denote the set of vertices in $\{A,B,C,D\}$ that are matched to
a vertex inside the patch.  Then here are the respective probabilities
of the local patterns in $G'$:
%align
%\begin{eqnarray*}
%S &=& \{A,B,C,D\}: (WZ+XY)\Delta'/WXYZ \\
%S &=& \{A,B\}:     P-\Delta'/XY \\
%S &=& \{A,C\}:     Q-\Delta'/WZ \\
%S &=& \{B,D\}:     R-\Delta'/WZ \\
%S &=& \{C,D\}:     S-\Delta'/XY \\
%S &=& \{\}:        1-P-Q-R-S+(WZ+XY)\Delta'/WXYZ
%\end{eqnarray*}
\begin{align*}
S &= \{A,B,C,D\}: (WZ+XY)\Delta'/WXYZ \\
S &= \{A,B\}:     P-\Delta'/XY \\
S &= \{A,C\}:     Q-\Delta'/WZ \\
S &= \{B,D\}:     R-\Delta'/WZ \\
S &= \{C,D\}:     S-\Delta'/XY \\
S &= \{\}:        1-P-Q-R-S+(WZ+XY)\Delta'/WXYZ
\end{align*}
(The second formula is obtained by recalling that the probability of
edge $AB$ being present in a random matching, which can happen in two
ways according to whether or not edge $CD$ is present, must be $P$;
the last formula is obtained by recalling that the probabilities of
the six local configurations must sum to 1.)

It follows from the last of these, and the urban renewal correspondence,
that the probability that a random matching of $G$ contains two edges
from the 4-cycle $ABCD$ is
$$1-P-Q-R-S+(WZ+XY)(PS/WZ+QR/XY).$$
The probability that a random matching of $G$ 
contains edges $AB$ and $CD$
must be equal to this quantity times
$$wz/(wz+xy) = WZ/(WZ+XY),$$
which gives
$$(WZ/(WZ+XY))(1-P-Q-R-S) + PS + QR(WZ/XY).$$
The probability that a random matching of $G$ contains edge $AB$ 
but \emph{not} edge $CD$ 
(by another application of the urban renewal correspondence)
equals the probability that a random matching of $G'$ 
contains edge $CD$ but not edge $AB$, 
which is $$S - PS - QR(WZ/XY).$$
Adding, we find that the probability that a random matching of $G$ 
contains edge $AB$ is
$$S + \frac{wz}{wz+xy}(1-P-Q-R-S).$$
Thus we conclude that
$$
p = S + \frac{wz}{wz+xy} (1 - P - Q - R - S) ,
$$
where $wz/(wz+xy)$ is the creation bias and
$1 - P - Q - R - S$ is the deficit.
The formulas for $q$, $r$, and $s$ follow by symmetry.

\section{Generating a random matching: the proof}

Now I will show that (generalized) domino-shuffling works.

First, let us note that the algorithm for generating
random matchings that was presented earlier
really \emph{is} a generalization of the domino-shuffling procedure
described in \cite{EKLP}.  
The operation of removing from a matching those matched edges 
that belong to the same cell as another matched edge 
corresponds to the process of removing odd blocks 
to obtain an odd-deficient tiling;
the operation of swapping the remaining edges 
to the opposite side of the cell 
corresponds to the process of shuffling dominos 
(resulting in the creation of an odd-deficient tiling 
of a larger Aztec diamond);
and the operation of introducing new edges 
corresponds to the creation
of new $2 \times 2$ blocks.

Next, let us recall that a perfect matching
of the Aztec diamond graph of order $n$
determines an $n \times n$ alternating-sign matrix,
as was first described in \cite{EKLP}.
Specifically, for each of the $n^2$ cells of the graph, 
write down the number of edges from that cell 
that participate in the matching and subtract 1.  
For instance:
$$
\pspicture(-4,-4)(4,4)
\psline(-4,3)(-3,4)\psline(-2,3)(-1,4)\psline(1,4)(2,3)\psline(3,4)(4,3)
\psline(-1,2)(0,3)\psline(-3,2)(-2,1)\psline(1,2)(2,1)\psline(3,2)(4,1)
\psline(-4,1)(-3,0)\psline(0,1)(1,0)\psline(-2,-1)(-1,0)\psline(2,-1)(3,0)
\psline(-4,-1)(-3,-2)\psline(0,-1)(1,-2)\psline(3,-2)(4,-1)\psline(-2,-3)(-1,-2)
\psline(-4,-3)(-3,-4)\psline(-1,-4)(0,-3)\psline(1,-4)(2,-3)\psline(3,-4)(4,-3)
\multips(-4,-3)(0,2){4}{\multips(0,0)(2,0){5}{\odisk(0,0){.1}}}
\multips(-3,-4)(0,2){5}{\multips(0,0)(2,0){4}{\odisk(0,0){.1}}}
\rput(-3, 3){$ 0$}\rput(-1, 3){$+1$}\rput(1, 3){$ 0$}\rput(3, 3){$ 0$}
\rput(-3, 1){$+1$}\rput(-1, 1){$-1$}\rput(1, 1){$+1$}\rput(3, 1){$ 0$}
\rput(-3,-1){$ 0$}\rput(-1,-1){$ 0$}\rput(1,-1){$ 0$}\rput(3,-1){$+1$}
\rput(-3,-3){$ 0$}\rput(-1,-3){$+1$}\rput(1,-3){$ 0$}\rput(3,-3){$ 0$}
\endpspicture
$$
Label the weights of the edges of the cell in row $i$ and column $j$ 
with $w_{ij}$, $x_{ij}$, $y_{ij}$, and $z_{ij}$, thus:
$$
\pspicture(-1,-1)(1,1)
\pspolygon(-1,0)(0,1)(1,0)(0,-1)
\rput[br](-.55, .55){$w$} \rput[bl](.55, .55){$x$}
\rput[tr](-.55,-.55){$y$} \rput[tl](.55,-.55){$z$}
\odisk(0,-1){.1} \odisk(0, 1){.1}
\odisk(-1,0){.1} \odisk( 1,0){.1}
\endpspicture
$$
Define also a ``cell-weight"
$$D_{ij} = w_{ij} z_{ij} + x_{ij} y_{ij}$$
(these weights are the same as the cell-factors
considered earlier in this article).
Call two edges in a matching ``parallel" 
if they belong to the same cell.

The bias in the creation rates for generalized shuffling 
was chosen so that the ratio between
the probabilities of choosing 
one pair of parallel edges versus another
($wz$ versus $xy$)
is equal to the ratio of the weights
of the resulting matchings.
Consequently, if two perfect matchings 
of the Aztec graph of order $n$ 
are associated with the same $n \times n$ alternating-sign matrix, 
then their \emph{relative} probabilities are correct.  
So all we need to do is verify that the aggregate probability 
of these matchings (for fixed alternating-sign matrix $A$) 
is what it should be.  

To do this, it is convenient to introduce
certain partial matchings of Aztec diamond graphs
(analogous to the odd-deficient and even-deficient
domino-tilings considered in \cite{EKLP}).
For the Aztec diamond of order $n$,
we consider partial matchings obtained from perfect matchings
by removal of all parallel edges;
that is, pairs of edges that
belong to the same cell.
For the Aztec diamond of order $n-1$,
we consider partial matchings obtained from perfect matchings
by removal of all pairs of edges
that belong to the same ``co-cell''
(defined as the space between four adjoining cells).
The ``destruction'' phase of generalized shuffling
converts a perfect matching of the graph of order $n-1$
into a partial matching $M$ of the graph of order $n-1$,
the ``sliding'' phase converts that partial matching
into a partial matching $M'$ of the graph of order $n$,
and the ``creation'' phase converts that partial matching
into a perfect matching.
Note that $M$ determines $M'$ uniquely, and vice versa.

Define the aggregate cell-weights $D_+$, $D_0$, and $D_-$
to be the products of those cell-weights $D_{i,j}$
associated with locations in the Aztec diamond
at which $+1$, $0$, and $-1$ appear, respectively
(so that $D_+ D_0 D_-$ is just the product of all the cell-weights).
The following three claims can be readily checked:
the sum of the weights of the perfect matchings
of the Aztec diamond of order $n$ that extend the partial matching $M'$ 
is equal to $D_+$ times the weight of $M'$ itself
(defined as the product of the weights of its constituent edges);
the weight of $M'$ is equal to $D_0$ times the weight of $M$
(defined in terms of the weighting of the graph of order $n-1$);
and the weight of $M$ is equal to $D_-$ 
times the sum of the weights of the perfect matchings
of the Aztec diamond of order $n-1$ that extend the partial matching $M$. 
(This relationship between cell-weights
and the entries of alternating-sign matrices
was originally made clear in the work of Ciucu \cite{Ci1}.)

The upshot is, the sum of the weights of the perfect matchings
of the Aztec diamond graph of order $n$ that are associated
with the alternating-sign matrix $A$ equals
$$
D_{1,1} D_{1,2} \ldots D_{n,n}
$$
times the sum of the weights of all the perfect matchings
of the Aztec diamond graph of order $n-1$
that are capable of giving rise to it under shuffling.
This factor is independent of $A$.
It follows that if one takes a random matching of the smaller graph
(in accordance with the edge weights given by urban renewal) and
applies destruction, shuffling, and creation, then one will get a random
matching of the larger graph.
%The logic here could be a little clearer.

\section{Diabolo-tilings of fortresses}

Consider an $n$-by-$n$ array of unit squares,
each of which has been cut by both of its diagonals, 
so that there are $4n^2$ isosceles right triangles in all.
A region called a \emph{fortress of order n}
is obtained by removing some of the triangles
that are at the boundary of the array.
More specifically, one colors the triangles alternately black and white,
and removes all the black (resp.\ white) triangles
that have an edge on the top or bottom (resp.\ left or right) 
boundaries of the array. 
Here, for instance, is a fortress of order 4:
$$
\pspicture(-4,-4)(4,4)
\psset{xunit=.8cm,yunit=.8cm}
\psline(-4,4)(-2,4)(-1,3)(0,4)(2,4)(3,3)
\psline(4,-4)(2,-4)(1,-3)(0,-4)(-2,-4)(-3,-3)
\pspolygon(-4,2)(-2,4)(4,-2)(2,-4)
\pspolygon(4,2)(2,4)(-4,-2)(-2,-4)
\pspolygon(4,0)(0,4)(-4,0)(0,-4)
\multips(-4,0)(2,-2){2}{\pspolygon[fillstyle=solid,fillcolor=black](0,0)(1,-1)(0,-2)}
\multips(-4,4)(2,-2){4}{\pspolygon[fillstyle=solid,fillcolor=black](0,0)(1,-1)(0,-2)}
\multips(0,4)(2,-2){2}{\pspolygon[fillstyle=solid,fillcolor=black](0,0)(1,-1)(0,-2)}
\multips(-3,-1)(2,-2){2}{\pspolygon[fillstyle=solid,fillcolor=black](0,0)(1,1)(1,-1)}
\multips(-3,3)(2,-2){4}{\pspolygon[fillstyle=solid,fillcolor=black](0,0)(1,1)(1,-1)}
\multips(1,3)(2,-2){2}{\pspolygon[fillstyle=solid,fillcolor=black](0,0)(1,1)(1,-1)}
\multips(-4,2)(2,2){1}{\pspolygon[fillstyle=solid,fillcolor=black](0,0)(2,0)(1,-1)}
\multips(-4,-2)(2,2){3}{\pspolygon[fillstyle=solid,fillcolor=black](0,0)(2,0)(1,-1)}
\multips(0,-2)(2,2){2}{\pspolygon[fillstyle=solid,fillcolor=black](0,0)(2,0)(1,-1)}
\multips(-4,0)(2,2){2}{\pspolygon[fillstyle=solid,fillcolor=black](0,0)(2,0)(1,1)}
\multips(-2,-2)(2,2){3}{\pspolygon[fillstyle=solid,fillcolor=black](0,0)(2,0)(1,1)}
\multips(2,-2)(2,2){1}{\pspolygon[fillstyle=solid,fillcolor=black](0,0)(2,0)(1,1)}
\endpspicture
$$
(When $n$ is even, the two ways of coloring the triangles
lead to fortresses that are mirror images of one another;
however, when $n$ is odd, the two sorts of fortresses
one obtains by removing the colored triangles in the
specified fashion are genuinely different.)
The graph dual to a fortress 
(with vertices corresponding to the isosceles right triangles)
is composed of 4-cycles and 8-cycles.
(If one removes the pendant edges
from the final figure in section 5
% kludge; renumber by hand
one obtains the graph dual to a fortress of order 3.)

We call the small isosceles right triangles \emph{monobolos}.
Given our tiling of the fortress by monobolos,
we can (in many different ways) form a new tiling
with half as many tiles
by amalgamating the monobolos in pairs,
where the two monobolos that are paired together
are required to be adjacent.
These new tiles are \emph{diabolos},
and come in two different shapes:
squares and isosceles triangles.
(Note: in the literature on tilings, such as \cite{G},
a third kind of diabolo is recognized,
namely a parallelogram with angles
of 45 and 135 degrees with side-lengths
in the ratio $1:\sqrt{2}$;
however, these diabolos do not arise
in the context being discussed here.)

A tiling obtained from the original monobolo-tiling of the fortress
by amalgamating adjacent pairs of monobolos
will be called, for (comparative) brevity,
a diabolo-tiling of a fortress.
It should, however, be kept in mind that we are tacitly
limiting ourselves to those tilings that can be obtained
by the aforementioned process of amalgamation;
or, if one prefers to use the dual picture,
tilings that correspond to perfect matchings
of the ``squares and octagons'' graph that is dual 
to the original tiling by monobolos.
For instance, the first of the following two tilings
of a fortress of order 3
by means of tiles that are diabolos
is an example of what we mean by a
``diabolo-tiling of a fortress'',
but the second is not,
because the four center diabolos
are not amalgams of the required kind:
$$
\pspicture(-3,-3)(3,3)
\psset{xunit=.8cm,yunit=.8cm}
\psline(-1,3)(1,3)
\psline(1,1)(3,1)
\psline(-3,-1)(-1,-1)
\psline(-1,-3)(1,-3)
\psline(-3,1)(-3,-1)
\psline(-1,-1)(-1,-3)
\psline(1,3)(1,1)
\psline(3,1)(3,-1)
\psline(-3,1)(-1,3)
\psline(-2,0)(0,2)
\psline(0,-2)(2,0)
\psline(1,-3)(3,-1)
\psline(-3,-1)(-1,-3)
\psline(-3,1)(1,-3)
\psline(-2,2)(-1,1)
\psline(1,-1)(2,-2)
\psline(-1,3)(3,-1)
\psline(1,3)(3,1)
\psline(-1,-1)(1,1)
\psline(-1,1)(1,-1)
\endpspicture
$$
$$
\pspicture(-3,-3)(3,3)
\psset{xunit=.8cm,yunit=.8cm}
\psline(-1,3)(1,3)
\psline(1,1)(3,1)
\psline(-3,-1)(-1,-1)
\psline(-1,-3)(1,-3)
\psline(-3,1)(-3,-1)
\psline(-1,-1)(-1,-3)
\psline(1,3)(1,1)
\psline(3,1)(3,-1)
\psline(-3,1)(-1,3)
\psline(-2,0)(0,2)
\psline(0,-2)(2,0)
\psline(1,-3)(3,-1)
\psline(-3,-1)(-1,-3)
\psline(-3,1)(1,-3)
\psline(-2,2)(-1,1)
\psline(1,-1)(2,-2)
\psline(-1,3)(3,-1)
\psline(1,3)(3,1)
\psline(-2,0)(2,0)
\psline(0,2)(0,-2)
\endpspicture
$$

To count the diabolo-tilings of a fortress
(understood in the above sense),
one replaces the underlying monobolo-tiling
by its dual graph and adds pendant edges
along the boundary,
obtaining a graph like the one shown
at the end of section 5.
%kludge; renumber by hand
One can then apply the urban renewal lemma
to turn this into an Aztec diamond graph
with edges of weight 1 arranged in cells
that alternate, checkerboard-style,
with cells whose edges have weight $\frac12$.
In this fashion one can derive
Yang's formula.

Now, however, we set our sights higher.
In section 6, 
%kludge: renumber by hand
we gave a scheme for calculating
the probability that a given edge of a
weighted Aztec diamond graph
is included in a random matching,
where the probability of a matching
is proportional to its weight.
This in fact lets us write down an explicit power series
whose coefficients are precisely
those inclusion-probabilities.
We will show how this goes in a
slightly more general setting,
where the edges of weight $\frac12$
are replaced by edges of weight $t$. 

Here we will find it convenient to use 
a rotated and shifted version of the Aztec diamond graph of order $n$, 
whose edges are all either horizontal or vertical (rather than diagonal).
The vertices of this graph are the integer points $(i,j)$
where $|i+\frac12|+|j+\frac12| \leq n$;
the edges of the graph join vertices at distance 1.
The horizontal edge joining $(i-1,j)$ and $(i,j)$
is called ``north-going'' if $i+j+n$ is odd
and ``south-going'' otherwise,
and the vertical edge joining $(i,j-1)$ and $(i,j)$
is called ``east-going'' if $i+j+n$ is odd
and ``west-going'' otherwise
(this nomenclature is taken from \cite{EKLP}).
The kind of weighting we are considering can be described as follows:
\begin{enumerate}
\item
Each horizontal edge has weight 1 or weight $t$ according to the parity
of its $x$-coordinate.  (That is, if two such edges are related by
a unit vertical displacement, they have same weight, but if they 
are related by a unit horizontal displacement, their weights differ.)
\item
Each vertical edge has weight 1 or weight $t$ according to the parity
of its $y$-coordinate.
\item
If $n$ is 1 or 2 (mod 4), the four extreme-most edges (the northernmost
and southernmost horizontal edges and the easternmost and westernmost
vertical edges) have weight $t$; if $n$ is 0 or 3 (mod 4), those four edges 
have weight 1.
\end{enumerate}
(These four situations are considered together because
each is linked to the next by the shuffling operation.
Technically, this scheme only handles fortresses of odd order,
and indeed, only handles half of those,
but the other case are quite similar.)
We define a generating function $P(x,y,z)$ in which
the coefficient of $x^i y^j z^n$
(with $k \geq 0$, $i+j+k$ odd, and $|i|+|j|<n$)
is the probability that a random matching 
of the Aztec diamond graph of order $n$, 
chosen in accordance with the probability distribution 
determined by the weight $t$, contains 
a horizontal bond joining vertices $(i-1,j)$ and $(i,j)$,
where $i+j+n$ is odd. 
(We are limiting ourselves to northgoing horizontal bonds
but this limitation is unimportant,
since by symmetry the other three sorts of bonds
have the same behavior.)
Note that the coefficients in this generating function
(viewed as a power series in the variables $x$, $y$, and $z$)
are polynomials in $t$,
and that for each $n$,
only finitely many pairs $i,j$
contribute a non-zero term to $P(x,y,z)$.

The presence of $t$ in the pattern of edge-weighting
makes it natural to divide the north-going edges
into four classes, according to how they ``sit''
relative to the weighting
(cells are weighted in two patterns when $n$ is odd
and in two other patterns when $n$ is even).
Correspondingly, we write $P(x,y,z)$ as a sum
of four generating functions,
each corresponding to one of the four classes of north-going edges.
We call these generating functions $E$, $F$, $G$, and $H$.
We also introduce generating functions whose coefficients
are the net creation rates of the four kinds 
of differently-weighted cells,
which we denote by $e$, $f$, $g$, and $h$.
$E$ and $e$ are associated with cells 
in which all edges have weight $t$;
$F$ and $f$ are associated with cells 
in which all edges have weight 1;
$G$ and $g$ are associated with cells 
in which horizontal edges have weight $t$ and vertical edges have weight 1;
and $H$ and $h$ are associated with cells 
in which horizontal edges have weight 1 and vertical edges have weight $t$.
Generalized shuffling implies the following algebraic relationships
among the four generating functions:
\begin{align*}
e &= 1 + \frac{t^2}{1+t^2} z ( (x+x^{-1}) g + (y+y^{-1}) h ) - z^2 f \\
f &=       \frac{1}{1+t^2} z ( (x+x^{-1}) h + (y+y^{-1}) g ) - z^2 e \\
g &=          \frac12      z ( (x+x^{-1}) f + (y+y^{-1}) e ) - z^2 h \\
h &=          \frac12      z ( (x+x^{-1}) e + (y+y^{-1}) f ) - z^2 g
\end{align*}
%%Where do these relations come from?
%I never proved here a general version of the
%autonomous recurrence relation for net creation rates!
%I should fix this in a later article.
These can be solved simultaneously, giving us four three-variable
generating functions $e(x,y,z)$, $f(x,y,z)$, $g(x,y,z)$, $h(x,y,z)$.
We can then solve
\begin{align*}
E &= Hyz + \frac{1}{2}       ez &
F &= Gyz + \frac{1}{2}       fz \\
G &= Eyz + \frac{t^2}{1+t^2} gz &
H &= Fyz + \frac{1}{1+t^2}   hz
\end{align*}
and obtain (messy!) generating functions $E(x,y,z)$, $F(x,y,z)$,
$G(x,y,z)$, $H(x,y,z)$.  The sum $E+F+G+H$, multiplied by $z$,
is the desired generating function $P$.  It is too messy to write 
down here, but it does at least in principle give one a way to 
understand what is going on with random diabolo-tilings of large 
fortresses.

We can also use generalized shuffling to generate a random tiling
of a large fortress.  Recall that when this was done for Aztec
diamonds in the early 1990s, a new phenomenon was discovered:
the ``arctic circle'' effect \cite{JPS}.  Specifically, with 
probability going to 1 as the size of the Aztec diamond graph
increases, a random tiling divides itself up naturally into five 
regions: four outer, ``frozen'' regions in which all the dominos 
line up with their neighbors in a repeating pattern, and a central,
``temperate'' region in which the dominos are jumbled together
in a random-looking way.  One feature of the temperate zone,
rigorously proved in \cite{CEP}, is that the asymptotic local 
statistics, expressed as a function of normalized position,
are nowhere constant; that is, the probability of seeing a
particular local pattern of dominos in a random tiling changes
as one shifts one view over macroscopic distances (i.e.,
distances comparable to the size of the Aztec diamond graph).
Strikingly, the boundary of the temperate zone, rescaled,
tends in probability to a perfect circle.

One might expect random diabolo-tilings of fortresses to exhibit
much the same sort of phenomena, albeit with the circular
temperate zone probably replaced by a temperate zone of
some other shape.  However, when the generalized shuffling
algorithm was used to generate random tilings of large
fortresses, a startling new phenomenon appeared: within the
very inmost part of the fortress, local statistics do \emph{not}
appear to undergo variation.  That is to say, within this
region, dubbed the ``tropical astroid'', the local statistics
of a random tiling appear to be shielded from the boundary,
so that the (normalized) position of a tile relative to the
boundary does not matter (as long as it stays fairly close
to the center of the region).  Figure \ref{figfort} shows a
random diabolo-tiling of the fortress of order 200; 
the square diabolos have been shaded, to highlight
the shape of the curve that separates the tropical zone
from the temperate zone.

\begin{figure*}
\begin{center}
\scalebox{.9428}{\includegraphics{fort200.eps}}
\caption{A fortress of order 200 randomly tiled with diabolos}
\label{figfort}
\end{center}
\end{figure*}

Suppose we put coordinates on the fortress so that the corners are
at $(0,2)$, $(0,-2)$, $(2,0)$, and $(-2,0)$.  Then it appears
that the boundary of the frozen region
is given by one real component of the curve
%%One-column version (kludge):
%\begin{eqnarray*}
%& 400x^8 + 400y^8 +3400x^2y^6 + 3400y^2x^6 + 8025x^4y^4
%+ 1000x^6 + 1000y^6 -17250x^4y^2 & \\
%& -17250x^2y^4 -1431x^4 - 1431y^4 +25812x^2y^2
%- 3402x^2 -3402y^2 +729 = 0 &
%\end{eqnarray*}
%%Two-column version:
\begin{multline*}
  400x^8 + 400y^8 +3400x^2y^6 + 3400y^2x^6 + 8025x^4y^4 \\
+ 1000x^6 + 1000y^6 -17250x^4y^2 -17250x^2y^4 -1431x^4 \\
-1431y^4 +25812x^2y^2 -3402x^2 -3402y^2 +729 = 0
\end{multline*}
%% Check to make sure that the above looks okay
(the ``octic circle'')
and that the boundary of the tropical region
is given by the other real component.
Henry Cohn and Robin Pemantle, as of this writing,
are working on a proof of these two assertions,
by giving an asymptotic analysis of the coefficients
of the generating functions
obtained via generalized shuffling. 

\section{Last thoughts}

Here are some last thoughts 
concerning urban renewal, domino-shuffling et cetera.

\begin{description}
\item[1.] This article has glossed over an important point,
namely, anomalies that arise when one attempts to apply
the algorithm to Aztec diamond graphs 
in which some edges have been assigned weight 0.  
Even if the weighted Aztec diamond in question has matchings
of positive weight,
it is possible that somewhere in the reduction process
one will encounter cells with cell-weight 0;
this leads to blow-up problems when one attempts to
divide by the cell-weight.
In such a case, one should replace edge-weights equal to $0$
in the original graph with edge-weights equal to $\epsilon$; 
the result will be a rational function of $\epsilon$ 
whose limiting value as $\epsilon$ goes to zero is desired.  
For this purpose, every rational function of $\epsilon$
can be written as a polynomial or power series in $\epsilon$ 
and replaced by its leading term, 
so calculations are not as bad as one might think.
%% FIX: It would be good to explain why all the edge-weights
%% and cell-weights that arise in the course of the algorithm 
%% are guaranteed to be power series in epsilon with positive 
%% coefficients.  It would probably help if I could state and prove
%% a combinatorial interpretation of all these weights.
This will work as long as the original weighted Aztec diamond graph
has at least one matching of positive weight.

\item[2.] These algorithms arose partly in response to work of
Kuperberg (see \cite{Ku1}), 
which took a more algebraic perspective on enumeration, 
using the approach pioneered by Kasteleyn \cite{Ka}.
Kasteleyn's method requires making some arbitrary choices
that end up not affecting the final answers
to meaningful enumerative questions.
This new work arose out of an attempt to find the invariant
combinatorial core of the Kasteleyn method.
In particular, graph-rewriting is a combinatorial substitute
for algebraic operations like row-reduction 
applied to a Kasteleyn matrix.
However, this analogy was never worked out in any kind
of rigorous detail.
It would be helpful to see this explained.

\item[3.] Continuing the above remark:
One strength of the algebraic approach,
exploited by Kenyon \cite{Ke1} and others,
is that edge-inclusion probabilities,
and, more generally, ``pattern-occurrence probabilities'',
can be expressed in terms of determinants
of minors of the inverse of the Kasteleyn matrix.
Here again, the answer must be independent of
the arbitrary choices that were made
in forming the matrix.
So it is natural to hope that there will be
a similar canonical scheme for calculating
such pattern-occurrence probabilities as well.
This may be similar to the problem of 
finding an extension of Dodgson's condensation scheme \cite{D}
that permits one to efficiently compute the inverse of a matrix
and not just compute its determinant.

\item[4.] Generalized shuffling
bears a strong resemblance
to an algorithm described in recent work of Viennot \cite{V}.
I have not studied the matter deeply enough
to be able to identify the relationship,
but I strongly believe that the resemblance
is more than coincidental.

\item[5.] It would also be desirable to extend urban renewal to 
matchings of \emph{non}-bipartite planar graphs.  This is
equivalent to asking for routinized matrix-reduction schemes 
for Kasteleyn's Pfaffians.

\item[6.] As described in \cite{CEP},
Ionescu's recurrence gives rise to edge-inclusion probabilities
for uniformly-weighted perfect matchings of Aztec diamond graphs,
and it is observed that if two edges $e$, $e'$
are close to one another (relative to the overall dimensions
of the large Aztec diamond graph they both inhabit),
\emph{and} $e$ and $e'$ occupy identical positions
within their respective cells
(i.e., both are either the northwest, northeast,
southwest, or southeast edges
in their cells),
then the edge-inclusion probabilities for $e$ and $e'$
are very close numerically.
Indeed, this phenomenon is a rigorously-proved consequence
of the detailed analysis given in \cite{CEP}.
However, it would be good to have a conceptual explanation
for this continuity property.
In particular, it seems plausible that
the recurrence relation for edge-inclusion probabilities
has the property of smoothing out differences.
A clear formulation of such a smoothing-out property,
and a rigorous proof that it holds,
would be very desirable,
since it might lead to a proof
that this kind of continuity property holds
for lozenge tilings of hexagons.
(Numerical evidence supports this continuity conjecture,
but the method used in \cite{CLP}
does not permit one to draw conclusions of this nature.) 
On the other hand, it should be noted that
these issues are subtle;
for instance, net creation rates
(viewed as a function of position)
tend not to vary as smoothly
as edge-inclusion probabilities. 

\item[7.] As is explained in \cite{EKLP},
enumeration of perfect matchings of Aztec diamond graphs
corresponds to ``2-enumeration'' of alternating-sign matrices,
where the weight assigned to a particular ASM
is 2 to the power of the number of $-1$'s it contains.
One can more generally consider $x$-enumeration,
where 2 is replaced by a general quantity $x$;
ordinary enumeration corresponds to 1-enumeration,
and 3-enumeration of ASMs leads to
interesting exact formulas
(see e.g.\ \cite{Ku2}).
Could shuffling be extended to give a scheme for
sampling from the set of ASMs with uniform distribution
or more generally an $x$-weighted distribution?

\end{description}

\begin{thebibliography}{99}
\bibitem{Ci1} Mihai Ciucu, Perfect matchings of cellular
graphs, \emph{J.\ Alg.\ Combin.} {\bf 5} (1996), 87--103.
\bibitem{Ci2} Mihai Ciucu, A complementation theorem
for perfect matchings of graphs having a cellular
completion, \emph{J.\ Combin.\ Theory\/} Ser.\ A
{\bf 81} (1998), 34--68.
\bibitem{CEP} Henry Cohn, Noam Elkies and James Propp,
Local statistics for random domino tilings of the Aztec
diamond, \emph{Duke Math.\ J.} {\bf 85} (1996), 117--166;
{\tt math.CO/0008243}
\bibitem{CLP} Henry Cohn, Michael Larsen and James Propp,
The shape of a typical boxed plane partition,
\emph{New York J.\ Math.} {\bf 4} (1998), 137--165;
{\tt math.CO/9801059}
\bibitem{CPV} Charles J.\ Colbourn, J.\ Scott Provan
and Dirk Vertigan, A new approach to solving three
combinatorial enumeration problems on planar graphs,
\emph{Disc.\ Appl.\ Math.} {\bf 60} (1995), 119--129.
\bibitem{CG} S.J.\ Cyvin and I.\ Gutman, Kekul\'e Structures
in Benzenoid Hydrocarbons (Lecture Notes in Chemistry {\bf 46}),
Springer-Verlag, 1988.
\bibitem{D} C.L.\ Dodgson, Condensation of determinants,
\emph{Proc.\ Royal Soc.\ London} {\bf 15} (1866), 150--155.
\bibitem{EKLP} Noam Elkies, Greg Kuperberg, Michael Larsen
and James Propp, Alternating sign matrices and domino tilings
\emph{J.\ Alg.\ Combin.}{\bf 1} (1992), 111--132, 219--234;
currently available from
{\tt http://www.math.wisc.edu/$\sim$propp/}.
%FIX Give xxx identifier
\bibitem{G} Martin Gardner, Polyhexes and polyabolos, chapter 11 in: 
Mathematical Magic Show, Vintage Books, 1978.
\bibitem{GCZ} D.\ Grensing, I.\ Carlsen and H.C\ Zapp,
%%FIX Is it really _I_ Carlsen?
Some exact results for the dimer problem on plane lattices
with non-standard boundaries,
\emph{Phil.\ Mag.} A {\bf 41} (1980), 777--781.
\bibitem{JPS} William Jockusch, James Propp and Peter Shor,
Random domino tilings and the arctic circle theorem,
preprint 1995;
{\tt math.CO/9801068}
\bibitem{Ka} P.W.\ Kasteleyn, Graph theory and crystal physics,
in: Graph Theory and Theoretical Physics,
F.\ Harary, ed., Academic Press, 1967.
\bibitem{Ke1} Richard Kenyon, Local statistics of lattice dimers,
\emph{Ann.\ Ins.\ H.\ Poincar\'e Probab.\ Statist.} {\bf 33}
(1997), 591--618;
currently available from
{\tt http://topo.math.u-psud.fr/$\sim$kenyon/}.
\bibitem{Ke2} Richard Kenyon, The planar dimer model with boundary: a survey, Directions in mathematical quasicrystals, 307--328, CRM Monogr. Ser. 13, 
Amer.\ Math.\ Soc.\ 2000; currently available from
{\tt http://topo.math.u-psud.fr/$\sim$kenyon/}.
%FIX KLUDGE!
\bibitem{Kuo} Eric Kuo, personal communication;
preliminary write-up currently available from
{\tt http://www.cs.berkeley.edu/$\sim$ekuo/}.
%FIX KLUDGE!
\bibitem{Ku1} Greg Kuperberg, An exploration of the
permanent-determinant method; {\tt math.CO/9810091}.
\bibitem{Ku2} Greg Kuperberg, Symmetry class of alternating-sign
matrices under one roof, to appear in Ann.\ of Math.; 
{\tt math.CO/0008184}.
\bibitem{Pe} Jerome Percus, One more technique for the
dimer problem, \emph{J.\ Math.\ Phys.} {\bf 10} (1969),
1881--1888.
\bibitem{RR} David P.\ Robbins and Howard Rumsey, Jr.,
Determinants and alternating sign matrices,
\emph{Adv.\ in Math.}\ {\bf 62} (1986), 169--184.
\bibitem{V} X.G.\ Viennot, A combinatorial interpretation
of the quotient-difference algorithm, in: Formal Power Series
and Algebraic Combinatorics, 12th International Conference,
D.\ Krob, A.A.\ Mikhalev and A.V.\ Mikhalev, eds., Springer, 2000.
\bibitem{W} David Wilson,
Determinant algorithms for random planar structures, in:
Proceedings of the Eighth Annual ACM-SIAM Symposium on
Discrete Algorithms (SODA 1997), 258--267;
currently available from
{\tt http://www.research.microsoft.com/$\sim$dbwilson/}.
\bibitem{Y} Bo-Yin Yang, Three enumeration problems concerning
Aztec diamonds, Ph.D.\ thesis, Department of Mathematics,
Massachusetts Institute of Technology, Cambridge, Massachusetts,
1991.
\bibitem{ZLH} C.\ Zeng, P.L.\ Leath and T.\ Hwa,
Thermodynamics of Mesoscopic Vortex Systems in $1+1$ Dimensions,
Phys.\ Rev.\ Letts. {\bf 83} (1999), 4860--4683.

\end{thebibliography}

\end{document}


math0111034.extracted_bib
\begin{thebibliography}{99}
\bibitem{Ci1} Mihai Ciucu, Perfect matchings of cellular
graphs, \emph{J.\ Alg.\ Combin.} {\bf 5} (1996), 87--103.
\bibitem{Ci2} Mihai Ciucu, A complementation theorem
for perfect matchings of graphs having a cellular
completion, \emph{J.\ Combin.\ Theory\/} Ser.\ A
{\bf 81} (1998), 34--68.
\bibitem{CEP} Henry Cohn, Noam Elkies and James Propp,
Local statistics for random domino tilings of the Aztec
diamond, \emph{Duke Math.\ J.} {\bf 85} (1996), 117--166;
{\tt math.CO/0008243}
\bibitem{CLP} Henry Cohn, Michael Larsen and James Propp,
The shape of a typical boxed plane partition,
\emph{New York J.\ Math.} {\bf 4} (1998), 137--165;
{\tt math.CO/9801059}
\bibitem{CPV} Charles J.\ Colbourn, J.\ Scott Provan
and Dirk Vertigan, A new approach to solving three
combinatorial enumeration problems on planar graphs,
\emph{Disc.\ Appl.\ Math.} {\bf 60} (1995), 119--129.
\bibitem{CG} S.J.\ Cyvin and I.\ Gutman, Kekul\'e Structures
in Benzenoid Hydrocarbons (Lecture Notes in Chemistry {\bf 46}),
Springer-Verlag, 1988.
\bibitem{D} C.L.\ Dodgson, Condensation of determinants,
\emph{Proc.\ Royal Soc.\ London} {\bf 15} (1866), 150--155.
\bibitem{EKLP} Noam Elkies, Greg Kuperberg, Michael Larsen
and James Propp, Alternating sign matrices and domino tilings
\emph{J.\ Alg.\ Combin.}{\bf 1} (1992), 111--132, 219--234;
currently available from
{\tt http://www.math.wisc.edu/$\sim$propp/}.
%FIX Give xxx identifier
\bibitem{G} Martin Gardner, Polyhexes and polyabolos, chapter 11 in: 
Mathematical Magic Show, Vintage Books, 1978.
\bibitem{GCZ} D.\ Grensing, I.\ Carlsen and H.C\ Zapp,
%%FIX Is it really _I_ Carlsen?
Some exact results for the dimer problem on plane lattices
with non-standard boundaries,
\emph{Phil.\ Mag.} A {\bf 41} (1980), 777--781.
\bibitem{JPS} William Jockusch, James Propp and Peter Shor,
Random domino tilings and the arctic circle theorem,
preprint 1995;
{\tt math.CO/9801068}
\bibitem{Ka} P.W.\ Kasteleyn, Graph theory and crystal physics,
in: Graph Theory and Theoretical Physics,
F.\ Harary, ed., Academic Press, 1967.
\bibitem{Ke1} Richard Kenyon, Local statistics of lattice dimers,
\emph{Ann.\ Ins.\ H.\ Poincar\'e Probab.\ Statist.} {\bf 33}
(1997), 591--618;
currently available from
{\tt http://topo.math.u-psud.fr/$\sim$kenyon/}.
\bibitem{Ke2} Richard Kenyon, The planar dimer model with boundary: a survey, Directions in mathematical quasicrystals, 307--328, CRM Monogr. Ser. 13, 
Amer.\ Math.\ Soc.\ 2000; currently available from
{\tt http://topo.math.u-psud.fr/$\sim$kenyon/}.
%FIX KLUDGE!
\bibitem{Kuo} Eric Kuo, personal communication;
preliminary write-up currently available from
{\tt http://www.cs.berkeley.edu/$\sim$ekuo/}.
%FIX KLUDGE!
\bibitem{Ku1} Greg Kuperberg, An exploration of the
permanent-determinant method; {\tt math.CO/9810091}.
\bibitem{Ku2} Greg Kuperberg, Symmetry class of alternating-sign
matrices under one roof, to appear in Ann.\ of Math.; 
{\tt math.CO/0008184}.
\bibitem{Pe} Jerome Percus, One more technique for the
dimer problem, \emph{J.\ Math.\ Phys.} {\bf 10} (1969),
1881--1888.
\bibitem{RR} David P.\ Robbins and Howard Rumsey, Jr.,
Determinants and alternating sign matrices,
\emph{Adv.\ in Math.}\ {\bf 62} (1986), 169--184.
\bibitem{V} X.G.\ Viennot, A combinatorial interpretation
of the quotient-difference algorithm, in: Formal Power Series
and Algebraic Combinatorics, 12th International Conference,
D.\ Krob, A.A.\ Mikhalev and A.V.\ Mikhalev, eds., Springer, 2000.
\bibitem{W} David Wilson,
Determinant algorithms for random planar structures, in:
Proceedings of the Eighth Annual ACM-SIAM Symposium on
Discrete Algorithms (SODA 1997), 258--267;
currently available from
{\tt http://www.research.microsoft.com/$\sim$dbwilson/}.
\bibitem{Y} Bo-Yin Yang, Three enumeration problems concerning
Aztec diamonds, Ph.D.\ thesis, Department of Mathematics,
Massachusetts Institute of Technology, Cambridge, Massachusetts,
1991.
\bibitem{ZLH} C.\ Zeng, P.L.\ Leath and T.\ Hwa,
Thermodynamics of Mesoscopic Vortex Systems in $1+1$ Dimensions,
Phys.\ Rev.\ Letts. {\bf 83} (1999), 4860--4683.

\end{thebibliography}