|
|
Boost : |
From: jsiek_at_[hidden]
Date: 1999-12-09 04:18:50
jsiek_at_[hidden] writes:
> Shall we start on a more formal write up of the interface? Which
> format do you prefer, latex? html? (please not MS word :) Do you want
> to focus on the write up for PropertyAccessor, and I on the traversal
> interface? One request that I have for the document format. The
> "concepts" should be documented similarly to Matt Austern's book
> (though perhaps using requirement tables closer to how they look in
> the standard).
I started thinking about how to split up the parts of the graph
interface into "concepts" but then realized the "definition" of this
graph interface is so intertwined that it's better to define just a
graph "module" that includes a collection of types and functions.
I've attached a first draft of a more formal write-up of the graph
structure interface. Since there was a vertices() function, for
consistency I went with "Vertex" instead of "Node" throughout. If
popular opinion goes the other way a simple search-and-replace can be
done :)
Comments and suggestions are welcome!
Cheers,
Jeremy
----------------------------------------------------------------------
Jeremy Siek
Ph.D. Candidate email: jsiek_at_[hidden]
Univ. of Notre Dame work phone: (650) 933-8724
and cell phone: (415) 377-5814
C++ Library & Compiler Group fax: (650) 932-0127
SGI www: http://www.lsc.nd.edu/~jsiek/
----------------------------------------------------------------------
\documentclass{llncs}
\usepackage{times}
\usepackage{german}
\usepackage{psfig}
\usepackage{fancybox}
\newcommand{\concept}[1]{\textsf{#1}}
\newcommand{\code}[1]{{\footnotesize \texttt{#1}}}
\title{An Interface Proposal for \\ Graph Data Structures and Algorithms}
\author{
Dietmar K\"uhl \qquad
Jeremy G.\ Siek \qquad
Lie-Quan Lee \qquad
Andrew Lumsdaine
}
\begin{document}
\maketitle
\section{The Graph Module}
Graphs are mathematical abstractions that are useful for solving many
problems, and therefore it is often necessary to represent graphs in
C++ computer programs. A standardized interface for manipulating
graphs is of upmost importance to encourage reuse of graph
algorithms and data structures. Here we define an interface for how
the structure of a graph is accessed. In this definition we will make
a distinction between an instance of a graph abstraction (in the
mathematical sense), and the representation of that abstraction in
software. The following section gives a review of the formal
definition of a graph abstraction.
\subsection{The Mathematical Definition of a Graph}
A \emph{graph} \emph{G} is a pair \emph{(V,E)}, where \emph{V} is a
finite set and \emph{E} is a binary relation on \emph{V}. \emph{V} is
called a
\emph{vertex} \emph{set} whose elements are called \emph{vertices}.
\emph{E} is called an \emph{edge} \emph{set} whose elements are called
\emph{edges}. An edge is a pair \emph{(u,v)}
where \emph{u,v} $\in$ \emph{V}. If \emph{(u,v)} is and edge in graph
\emph{G}, then vertex \emph{v} is \emph{adjacent} to vertex \emph{u}.
Edge \emph{(u,v)} is an \emph{out-edge} of vertex \emph{u} and an
\emph{in-edge} of vertex \emph{v}.
An edge \emph{(u,v)} leaves from the \emph{source} vertex \emph{u} to
the \emph{target} vertex \emph{v}.
\subsection{Representations of Graphs in C++}
We represent an instance of an abstract \emph{graph} \emph{G} with an
instance of a graph module. A graph module consists of a
\concept{Graph} type \code{G} together with an associated
set of types and functions. A graph module \emph{instance} consists of
an object \code{g} of type \code{G}, and other objects created by the graph
module's functions.
\subsection{Description and Requirements for the Graph Module}
The following gives a description and some of the
requirements for the types associated with \code{G}. The rest of the
requirements are given in Table~\ref{fig:Graph_module}. The
requirements are not assigned to the individual types within a graph
module, for most of the requirements deal with several types at
once. Instead the requirements are for the graph module as a whole.
\begin{itemize}
\item The \concept{VertexDescriptor} type \code{V} of \code{G}.
Objects of type \code{V} have a one-to-one correspondence with a
particular \emph{vertex} in the abstract graph instance \emph{G}.
\code{V} is shorthand for
\code{typename graph\_traits<G>::vertex\_descriptor}.
\item The \concept{EdgeDescriptor} type \code{E}.
Objects of type \code{E} have a one-to-one
correspondence with a particular \emph{edge} $(u,v)$ in the graph
\emph{G}.
\code{E} is shorthand for
\code{typename graph\_\-traits<G>\-::edge\_descriptor}.
\item The \concept{AdjacencyIterator} type \code{AdjIt}.
The pair of iterators of type \code{AdjIt} associated with
a particular vertex \emph{v} (obtained via \code{adj(v,g)}) provide
access to a range of objects of type \code{V} which represent
the vertices adjacent to \emph{v}. An \concept{AdjacencyIterator}
type must meet the requirements of \concept{InputIterator}.
\code{AdjIt} is shorthand for
\code{typename graph\_\-traits<G>\-::adjacency\_\-iterator}.
\item The \concept{IncidenceIterator} type \code{InIt}.
The pair of iterators of type \code{InIt} associated with
a particular vertex \emph{v} (obtained via \code{out\_edges(v,g)}) provide
access to a range of objects of type \code{E} which represent
the \emph{out edges} of \emph{v}. An \concept{IncidenceIterator}
type must meet the requirements of \concept{InputIterator}.
\code{InIt} is shorthand for
\code{typename graph\_\-traits<G>\-::incidence\_\-iterator}.
\item The \concept{VertexIterator} type \code{VIt}.
The pair of iterators of type \code{VIt} associated with
a graph \emph{G} (obtained via \code{vertices(g)})
provide access to a range of objects of type \code{V} which
represent the vertex set \emph{V} of \emph{G}.
A \concept{VertexIterator}
type must meet the requirements of \concept{InputIterator}.
\code{VIt} is shorthand for
\code{typename graph\_\-traits<G>\-::vertex\_\-iterator}.
\item The \concept{EdgeIterator} type \code{EIt}.
The pair of iterators of type \code{EIt} associated with
a graph \emph{G} (obtained via \code{edges(g)})
provide access to a range of objects of type \code{E} which
represent the edge set \emph{E} of \emph{G}.
An \concept{EdgeIterator}
type must meet the requirements of \concept{InputIterator}.
\code{EIt} is shorthand for
\code{typename graph\_\-traits<G>\-::edge\_\-iterator}.
\end{itemize}
In Table~\ref{fig:Graph_module}, \code{g} is an object of type \code{G},
\code{v} is an object of type \code{V}, and \code{e} is an object of
type \code{E}. All of the functions in the graph module are guaranteed
to be constant time and space.
\begin{table*}[hbt]
\begin{center}
{\footnotesize
\begin{tabular}{|p{1.1in}|p{1.3in}|p{2.5in}|} \hline
\textbf{operation} & \textbf{type} & \textbf{semantics} \\ \hline \hline
\code{adj(v,g)} & \code{pair<AdjIt,AdjIt>} & An iterator-range providing access to the vertices adjacent to vertex \code{v} in graph \code{g} \\
\code{out\_edges(v,g)} & \code{pair<InIt,InIt>} & An iterator-range providing access to the out-edges of vertex \code{v} in graph \code{g} \\
\code{source(e,g)} & \code{V} & Returns the vertex descriptor for $u$ of the edge $(u,v)$ represented by \code{e}. \\
\code{target(e,g)} & \code{V} & Returns the vertex descriptor for $v$ of the edge $(u,v)$ represented by \code{e}. \\
\code{vertices(g)} & \code{pair<VIt,VIt>} & An iterator-range providing access to all the vertices in the graph \code{g}. \\
\code{edges(g)} & \code{pair<EIt,EIt>} & An iterator-range providing access to all the edges in the graph \code{g}. \\ \hline
\end{tabular}
}
\end{center}
\caption{The graph module requirements.
\label{fig:Graph_module}}
\end{table*}
\subsection{Graph Module Variants}
There are several graph module variants, the \concept{GraphEL} (for
graph with ``edge list''), \concept{GraphVL} (for graph with ``vertex
list''), and \concept{Graph}. The requirements for a \concept{Graph}
are all of those described above and in Table~\ref{fig:Graph_module}.
\concept{GraphVL} has the same requirements as \concept{Graph}
minus the function \code{edges()}. The \code{graph\_traits}
specialization for a \concept{GraphVL} type can define
\code{edge\_iterator} to be \code{void}.
\concept{GraphEL} only requires the \code{edges()}, \code{source()},
and \code{target()} functions. The \code{graph\_traits}
specialization for a
\concept{GraphEL} type can define the \code{vertex\_iterator},
the \code{adjacency\_iterator}, and the \code{incidence\_iterator} to
be \code{void}.
\subsection{Graph Traits}
The types associated with a \concept{Graph} type are accessible
through the \code{graph\_traits} class.
{\small
\begin{verbatim}
template <class Graph> struct graph_traits {
typedef typename Graph::vertex_descriptor vertex_descriptor;
typedef typename Graph::edge_descriptor edge_descriptor;
typedef typename Graph::adjacency_iterator adjacency_iterator;
typedef typename Graph::incidence_iterator incidence_iterator;
typedef typename Graph::vertex_iterator vertex_iterator;
typedef typename Graph::edge_iterator edge_iterator;
};
\end{verbatim}
}
\end{document}
% LocalWords: VertexDescriptor typename raits escriptor EdgeDescriptor AdjIt
% LocalWords: AdjacencyIterator adj InputIterator terator IncidenceIterator
% LocalWords: InIt dges VertexIterator VIt EdgeIterator EIt hbt GraphEL struct
% LocalWords: GraphVL
% LLNCS DOCUMENT CLASS -- version 2.6
% for LaTeX2e
%
\NeedsTeXFormat{LaTeX2e}[1995/12/01]
\ProvidesClass{llncs}[1999/04/27 v2.6
^^JLaTeX document class for Lecture Notes in Computer Science]
% Options
\let\if_at_envcntreset\iffalse
\DeclareOption{envcountreset}{\let\if_at_envcntreset\iftrue}
\DeclareOption{citeauthoryear}{\let\citeauthoryear=Y}
\DeclareOption{oribibl}{\let\oribibl=Y}
\let\if_at_envcntsame\iffalse
\DeclareOption{envcountsame}{\let\if_at_envcntsame\iftrue}
\let\if_at_envcntsect\iffalse
\DeclareOption{envcountsect}{\let\if_at_envcntsect\iftrue}
\let\if_at_runhead\iffalse
\DeclareOption{runningheads}{\let\if_at_runhead\iftrue}
\let\if_at_openbib\iffalse
\DeclareOption{openbib}{\let\if_at_openbib\iftrue}
\DeclareOption*{\PassOptionsToClass{\CurrentOption}{article}}
\ProcessOptions
\LoadClass[twoside]{article}
\RequirePackage{multicol} % needed for the list of participants, index
\setlength{\textwidth}{12.2cm}
\setlength{\textheight}{19.3cm}
% Ragged bottom for the actual page
\def\thisbottomragged{\def\@textbottom{\vskip\z@ plus.0001fil
\global\let\@textbottom\relax}}
\renewcommand\small{%
\@setfontsize\small\@ixpt{11}%
\abovedisplayskip 8.5\p@ \@plus3\p@ \@minus4\p@
\abovedisplayshortskip \z@ \@plus2\p@
\belowdisplayshortskip 4\p@ \@plus2\p@ \@minus2\p@
\def\@listi{\leftmargin\leftmargini
\parsep 0\p@ \@plus1\p@ \@minus\p@
\topsep 8\p@ \@plus2\p@ \@minus4\p@
\itemsep0\p@}%
\belowdisplayskip \abovedisplayskip
}
\frenchspacing
\widowpenalty=10000
\clubpenalty=10000
\setlength\oddsidemargin {63\p@}
\setlength\evensidemargin {63\p@}
\setlength\marginparwidth {90\p@}
\setlength\headsep {16\p@}
\setlength\footnotesep{7.7\p@}
\setlength\textfloatsep{8mm\@plus 2\p@ \@minus 4\p@}
\setlength\intextsep {8mm\@plus 2\p@ \@minus 2\p@}
\setcounter{secnumdepth}{2}
\newcounter {chapter}
\renewcommand\thechapter {\@arabic\c_at_chapter}
\newif\if_at_mainmatter \@mainmattertrue
\newcommand\frontmatter{\cleardoublepage
\@mainmatterfalse\pagenumbering{Roman}}
\newcommand\mainmatter{\cleardoublepage
\@mainmattertrue\pagenumbering{arabic}}
\newcommand\backmatter{\if_at_openright\cleardoublepage\else\clearpage\fi
\@mainmatterfalse}
\renewcommand\part{\cleardoublepage
\thispagestyle{empty}%
\if_at_twocolumn
\onecolumn
\@tempswatrue
\else
\@tempswafalse
\fi
\null\vfil
\secdef\@part\@spart}
\def\@part[#1]#2{%
\ifnum \c_at_secnumdepth >-2\relax
\refstepcounter{part}%
\addcontentsline{toc}{part}{\thepart\hspace{1em}#1}%
\else
\addcontentsline{toc}{part}{#1}%
\fi
\markboth{}{}%
{\centering
\interlinepenalty \@M
\normalfont
\ifnum \c_at_secnumdepth >-2\relax
\huge\bfseries \partname~\thepart
\par
\vskip 20\p@
\fi
\Huge \bfseries #2\par}%
\@endpart}
\def\@spart#1{%
{\centering
\interlinepenalty \@M
\normalfont
\Huge \bfseries #1\par}%
\@endpart}
\def\@endpart{\vfil\newpage
\if_at_twoside
\null
\thispagestyle{empty}%
\newpage
\fi
\if_at_tempswa
\twocolumn
\fi}
\newcommand\chapter{\clearpage
\thispagestyle{empty}%
\global\@topnum\z@
\@afterindentfalse
\secdef\@chapter\@schapter}
\def\@chapter[#1]#2{\ifnum \c_at_secnumdepth >\m_at_ne
\if_at_mainmatter
\refstepcounter{chapter}%
\typeout{\@chapapp\space\thechapter.}%
\addcontentsline{toc}{chapter}%
{\protect\numberline{\thechapter}#1}%
\else
\addcontentsline{toc}{chapter}{#1}%
\fi
\else
\addcontentsline{toc}{chapter}{#1}%
\fi
\chaptermark{#1}%
\addtocontents{lof}{\protect\addvspace{10\p@}}%
\addtocontents{lot}{\protect\addvspace{10\p@}}%
\if_at_twocolumn
\@topnewpage[\@makechapterhead{#2}]%
\else
\@makechapterhead{#2}%
\@afterheading
\fi}
\def\@makechapterhead#1{%
% \vspace*{50\p@}%
{\centering
\ifnum \c_at_secnumdepth >\m_at_ne
\if_at_mainmatter
\large\bfseries \@chapapp{} \thechapter
\par\nobreak
\vskip 20\p@
\fi
\fi
\interlinepenalty\@M
\Large \bfseries #1\par\nobreak
\vskip 40\p@
}}
\def\@schapter#1{\if_at_twocolumn
\@topnewpage[\@makeschapterhead{#1}]%
\else
\@makeschapterhead{#1}%
\@afterheading
\fi}
\def\@makeschapterhead#1{%
% \vspace*{50\p@}%
{\centering
\normalfont
\interlinepenalty\@M
\Large \bfseries #1\par\nobreak
\vskip 40\p@
}}
\renewcommand\section{\@startsection{section}{1}{\z@}%
{-18\p@ \@plus -4\p@ \@minus -4\p@}%
{12\p@ \@plus 4\p@ \@minus 4\p@}%
{\normalfont\large\bfseries\boldmath
\rightskip=\z@ \@plus 8em\pretolerance=10000 }}
\renewcommand\subsection{\@startsection{subsection}{2}{\z@}%
{-18\p@ \@plus -4\p@ \@minus -4\p@}%
{8\p@ \@plus 4\p@ \@minus 4\p@}%
{\normalfont\normalsize\bfseries\boldmath
\rightskip=\z@ \@plus 8em\pretolerance=10000 }}
\renewcommand\subsubsection{\@startsection{subsubsection}{3}{\z@}%
{-18\p@ \@plus -4\p@ \@minus -4\p@}%
{-0.5em \@plus -0.22em \@minus -0.1em}%
{\normalfont\normalsize\bfseries\boldmath}}
\renewcommand\paragraph{\@startsection{paragraph}{4}{\z@}%
{-12\p@ \@plus -4\p@ \@minus -4\p@}%
{-0.5em \@plus -0.22em \@minus -0.1em}%
{\normalfont\normalsize\itshape}}
\renewcommand\subparagraph[1]{\typeout{LLNCS warning: You should not use
\string\subparagraph\space with this class}\vskip0.5cm
You should not use \verb|\subparagraph| with this class.\vskip0.5cm}
\DeclareMathSymbol{\Gamma}{\mathalpha}{letters}{"00}
\DeclareMathSymbol{\Delta}{\mathalpha}{letters}{"01}
\DeclareMathSymbol{\Theta}{\mathalpha}{letters}{"02}
\DeclareMathSymbol{\Lambda}{\mathalpha}{letters}{"03}
\DeclareMathSymbol{\Xi}{\mathalpha}{letters}{"04}
\DeclareMathSymbol{\Pi}{\mathalpha}{letters}{"05}
\DeclareMathSymbol{\Sigma}{\mathalpha}{letters}{"06}
\DeclareMathSymbol{\Upsilon}{\mathalpha}{letters}{"07}
\DeclareMathSymbol{\Phi}{\mathalpha}{letters}{"08}
\DeclareMathSymbol{\Psi}{\mathalpha}{letters}{"09}
\DeclareMathSymbol{\Omega}{\mathalpha}{letters}{"0A}
\let\footnotesize\small
\def\vec#1{\mathchoice{\mbox{\boldmath$\displaystyle#1$}}
{\mbox{\boldmath$\textstyle#1$}}
{\mbox{\boldmath$\scriptstyle#1$}}
{\mbox{\boldmath$\scriptscriptstyle#1$}}}
\def\squareforqed{\hbox{\rlap{$\sqcap$}$\sqcup$}}
\def\qed{\ifmmode\squareforqed\else{\unskip\nobreak\hfil
\penalty50\hskip1em\null\nobreak\hfil\squareforqed
\parfillskip=0pt\finalhyphendemerits=0\endgraf}\fi}
\def\getsto{\mathrel{\mathchoice {\vcenter{\offinterlineskip
\halign{\hfil
$\displaystyle##$\hfil\cr\gets\cr\to\cr}}}
{\vcenter{\offinterlineskip\halign{\hfil$\textstyle##$\hfil\cr\gets
\cr\to\cr}}}
{\vcenter{\offinterlineskip\halign{\hfil$\scriptstyle##$\hfil\cr\gets
\cr\to\cr}}}
{\vcenter{\offinterlineskip\halign{\hfil$\scriptscriptstyle##$\hfil\cr
\gets\cr\to\cr}}}}}
\def\lid{\mathrel{\mathchoice {\vcenter{\offinterlineskip\halign{\hfil
$\displaystyle##$\hfil\cr<\cr\noalign{\vskip1.2pt}=\cr}}}
{\vcenter{\offinterlineskip\halign{\hfil$\textstyle##$\hfil\cr<\cr
\noalign{\vskip1.2pt}=\cr}}}
{\vcenter{\offinterlineskip\halign{\hfil$\scriptstyle##$\hfil\cr<\cr
\noalign{\vskip1pt}=\cr}}}
{\vcenter{\offinterlineskip\halign{\hfil$\scriptscriptstyle##$\hfil\cr
<\cr
\noalign{\vskip0.9pt}=\cr}}}}}
\def\gid{\mathrel{\mathchoice {\vcenter{\offinterlineskip\halign{\hfil
$\displaystyle##$\hfil\cr>\cr\noalign{\vskip1.2pt}=\cr}}}
{\vcenter{\offinterlineskip\halign{\hfil$\textstyle##$\hfil\cr>\cr
\noalign{\vskip1.2pt}=\cr}}}
{\vcenter{\offinterlineskip\halign{\hfil$\scriptstyle##$\hfil\cr>\cr
\noalign{\vskip1pt}=\cr}}}
{\vcenter{\offinterlineskip\halign{\hfil$\scriptscriptstyle##$\hfil\cr
>\cr
\noalign{\vskip0.9pt}=\cr}}}}}
\def\grole{\mathrel{\mathchoice {\vcenter{\offinterlineskip
\halign{\hfil
$\displaystyle##$\hfil\cr>\cr\noalign{\vskip-1pt}<\cr}}}
{\vcenter{\offinterlineskip\halign{\hfil$\textstyle##$\hfil\cr
>\cr\noalign{\vskip-1pt}<\cr}}}
{\vcenter{\offinterlineskip\halign{\hfil$\scriptstyle##$\hfil\cr
>\cr\noalign{\vskip-0.8pt}<\cr}}}
{\vcenter{\offinterlineskip\halign{\hfil$\scriptscriptstyle##$\hfil\cr
>\cr\noalign{\vskip-0.3pt}<\cr}}}}}
\def\bbbr{{\rm I\!R}} %reelle Zahlen
\def\bbbm{{\rm I\!M}}
\def\bbbn{{\rm I\!N}} %natuerliche Zahlen
\def\bbbf{{\rm I\!F}}
\def\bbbh{{\rm I\!H}}
\def\bbbk{{\rm I\!K}}
\def\bbbp{{\rm I\!P}}
\def\bbbone{{\mathchoice {\rm 1\mskip-4mu l} {\rm 1\mskip-4mu l}
{\rm 1\mskip-4.5mu l} {\rm 1\mskip-5mu l}}}
\def\bbbc{{\mathchoice {\setbox0=\hbox{$\displaystyle\rm C$}\hbox{\hbox
to0pt{\kern0.4\wd0\vrule height0.9\ht0\hss}\box0}}
{\setbox0=\hbox{$\textstyle\rm C$}\hbox{\hbox
to0pt{\kern0.4\wd0\vrule height0.9\ht0\hss}\box0}}
{\setbox0=\hbox{$\scriptstyle\rm C$}\hbox{\hbox
to0pt{\kern0.4\wd0\vrule height0.9\ht0\hss}\box0}}
{\setbox0=\hbox{$\scriptscriptstyle\rm C$}\hbox{\hbox
to0pt{\kern0.4\wd0\vrule height0.9\ht0\hss}\box0}}}}
\def\bbbq{{\mathchoice {\setbox0=\hbox{$\displaystyle\rm
Q$}\hbox{\raise
0.15\ht0\hbox to0pt{\kern0.4\wd0\vrule height0.8\ht0\hss}\box0}}
{\setbox0=\hbox{$\textstyle\rm Q$}\hbox{\raise
0.15\ht0\hbox to0pt{\kern0.4\wd0\vrule height0.8\ht0\hss}\box0}}
{\setbox0=\hbox{$\scriptstyle\rm Q$}\hbox{\raise
0.15\ht0\hbox to0pt{\kern0.4\wd0\vrule height0.7\ht0\hss}\box0}}
{\setbox0=\hbox{$\scriptscriptstyle\rm Q$}\hbox{\raise
0.15\ht0\hbox to0pt{\kern0.4\wd0\vrule height0.7\ht0\hss}\box0}}}}
\def\bbbt{{\mathchoice {\setbox0=\hbox{$\displaystyle\rm
T$}\hbox{\hbox to0pt{\kern0.3\wd0\vrule height0.9\ht0\hss}\box0}}
{\setbox0=\hbox{$\textstyle\rm T$}\hbox{\hbox
to0pt{\kern0.3\wd0\vrule height0.9\ht0\hss}\box0}}
{\setbox0=\hbox{$\scriptstyle\rm T$}\hbox{\hbox
to0pt{\kern0.3\wd0\vrule height0.9\ht0\hss}\box0}}
{\setbox0=\hbox{$\scriptscriptstyle\rm T$}\hbox{\hbox
to0pt{\kern0.3\wd0\vrule height0.9\ht0\hss}\box0}}}}
\def\bbbs{{\mathchoice
{\setbox0=\hbox{$\displaystyle \rm S$}\hbox{\raise0.5\ht0\hbox
to0pt{\kern0.35\wd0\vrule height0.45\ht0\hss}\hbox
to0pt{\kern0.55\wd0\vrule height0.5\ht0\hss}\box0}}
{\setbox0=\hbox{$\textstyle \rm S$}\hbox{\raise0.5\ht0\hbox
to0pt{\kern0.35\wd0\vrule height0.45\ht0\hss}\hbox
to0pt{\kern0.55\wd0\vrule height0.5\ht0\hss}\box0}}
{\setbox0=\hbox{$\scriptstyle \rm S$}\hbox{\raise0.5\ht0\hbox
to0pt{\kern0.35\wd0\vrule height0.45\ht0\hss}\raise0.05\ht0\hbox
to0pt{\kern0.5\wd0\vrule height0.45\ht0\hss}\box0}}
{\setbox0=\hbox{$\scriptscriptstyle\rm S$}\hbox{\raise0.5\ht0\hbox
to0pt{\kern0.4\wd0\vrule height0.45\ht0\hss}\raise0.05\ht0\hbox
to0pt{\kern0.55\wd0\vrule height0.45\ht0\hss}\box0}}}}
\def\bbbz{{\mathchoice {\hbox{$\mathsf\textstyle Z\kern-0.4em Z$}}
{\hbox{$\mathsf\textstyle Z\kern-0.4em Z$}}
{\hbox{$\mathsf\scriptstyle Z\kern-0.3em Z$}}
{\hbox{$\mathsf\scriptscriptstyle Z\kern-0.2em Z$}}}}
\let\ts\,
\setlength\leftmargini {17\p@}
\setlength\leftmargin {\leftmargini}
\setlength\leftmarginii {\leftmargini}
\setlength\leftmarginiii {\leftmargini}
\setlength\leftmarginiv {\leftmargini}
\setlength \labelsep {.5em}
\setlength \labelwidth{\leftmargini}
\addtolength\labelwidth{-\labelsep}
\def\@listI{\leftmargin\leftmargini
\parsep 0\p@ \@plus1\p@ \@minus\p@
\topsep 8\p@ \@plus2\p@ \@minus4\p@
\itemsep0\p@}
\let\@listi\@listI
\@listi
\def\@listii {\leftmargin\leftmarginii
\labelwidth\leftmarginii
\advance\labelwidth-\labelsep
\topsep 0\p@ \@plus2\p@ \@minus\p@}
\def\@listiii{\leftmargin\leftmarginiii
\labelwidth\leftmarginiii
\advance\labelwidth-\labelsep
\topsep 0\p@ \@plus\p@\@minus\p@
\parsep \z@
\partopsep \p@ \@plus\z@ \@minus\p@}
\renewcommand\labelitemi{\normalfont\bfseries --}
\renewcommand\labelitemii{$\m_at_th\bullet$}
\setlength\arraycolsep{1.4\p@}
\setlength\tabcolsep{1.4\p@}
\def\tableofcontents{\chapter*{\contentsname\@mkboth{{\contentsname}}%
{{\contentsname}}}
\def\authcount##1{\setcounter{auco}{##1}\setcounter{@auth}{1}}
\def\lastand{\ifnum\value{auco}=2\relax
\unskip{} \andname\
\else
\unskip \lastandname\
\fi}%
\def\and{\stepcounter{@auth}\relax
\ifnum\value{@auth}=\value{auco}%
\lastand
\else
\unskip,
\fi}%
\@starttoc{toc}\if_at_restonecol\twocolumn\fi}
\def\l_at_part#1#2{\addpenalty{\@secpenalty}%
\addvspace{2em plus\p@}% % space above part line
\begingroup
\parindent \z@
\rightskip \z@ plus 5em
\hrule\vskip5pt
\bfseries\boldmath % set line in boldface
\leavevmode % TeX command to enter horizontal mode.
#1\par
\vskip5pt
\hrule
\vskip1pt
\nobreak % Never break after part entry
\endgroup}
\def\@dotsep{2}
\def\hyperhrefextend{\ifx\hyper_at_anchor\@undefined\else
{chapter.\thechapter}\fi}
\def\addnumcontentsmark#1#2#3{%
\addtocontents{#1}{\protect\contentsline{#2}{\protect\numberline
{\thechapter}#3}{\thepage}\hyperhrefextend}}
\def\addcontentsmark#1#2#3{%
\addtocontents{#1}{\protect\contentsline{#2}{#3}{\thepage}\hyperhrefextend}}
\def\addcontentsmarkwop#1#2#3{%
\addtocontents{#1}{\protect\contentsline{#2}{#3}{0}\hyperhrefextend}}
\def\@adcmk[#1]{\ifcase #1 \or
\def\@gtempa{\addnumcontentsmark}%
\or \def\@gtempa{\addcontentsmark}%
\or \def\@gtempa{\addcontentsmarkwop}%
\fi\@gtempa{toc}{chapter}}
\def\addtocmark{\@ifnextchar[{\@adcmk}{\@adcmk[3]}}
\def\l_at_chapter#1#2{\addpenalty{-\@highpenalty}
\vskip 1.0em plus 1pt \@tempdima 1.5em \begingroup
\parindent \z@ \rightskip \@pnumwidth
\parfillskip -\@pnumwidth
\leavevmode \advance\leftskip\@tempdima \hskip -\leftskip
{\large\bfseries\boldmath#1}\ifx0#2\hfil\null
\else
\nobreak
\leaders\hbox{$\m_at_th \mkern \@dotsep mu.\mkern
\@dotsep mu$}\hfill
\nobreak\hbox to\@pnumwidth{\hss #2}%
\fi\par
\penalty\@highpenalty \endgroup}
\def\l_at_title#1#2{\addpenalty{-\@highpenalty}
\addvspace{8pt plus 1pt}
\@tempdima \z@
\begingroup
\parindent \z@ \rightskip \@tocrmarg
\parfillskip -\@tocrmarg
\leavevmode \advance\leftskip\@tempdima \hskip -\leftskip
#1\nobreak
\leaders\hbox{$\m_at_th \mkern \@dotsep mu.\mkern
\@dotsep mu$}\hfill
\nobreak\hbox to\@pnumwidth{\hss #2}\par
\penalty\@highpenalty \endgroup}
\setcounter{tocdepth}{0}
\newdimen\tocchpnum
\newdimen\tocsecnum
\newdimen\tocsectotal
\newdimen\tocsubsecnum
\newdimen\tocsubsectotal
\newdimen\tocsubsubsecnum
\newdimen\tocsubsubsectotal
\newdimen\tocparanum
\newdimen\tocparatotal
\newdimen\tocsubparanum
\tocchpnum=\z@ % no chapter numbers
\tocsecnum=15\p@ % section 88. plus 2.222pt
\tocsubsecnum=23\p@ % subsection 88.8 plus 2.222pt
\tocsubsubsecnum=27\p@ % subsubsection 88.8.8 plus 1.444pt
\tocparanum=35\p@ % paragraph 88.8.8.8 plus 1.666pt
\tocsubparanum=43\p@ % subparagraph 88.8.8.8.8 plus 1.888pt
\def\calctocindent{%
\tocsectotal=\tocchpnum
\advance\tocsectotal by\tocsecnum
\tocsubsectotal=\tocsectotal
\advance\tocsubsectotal by\tocsubsecnum
\tocsubsubsectotal=\tocsubsectotal
\advance\tocsubsubsectotal by\tocsubsubsecnum
\tocparatotal=\tocsubsubsectotal
\advance\tocparatotal by\tocparanum}
\calctocindent
\def\l_at_section{\@dottedtocline{1}{\tocchpnum}{\tocsecnum}}
\def\l_at_subsection{\@dottedtocline{2}{\tocsectotal}{\tocsubsecnum}}
\def\l_at_subsubsection{\@dottedtocline{3}{\tocsubsectotal}{\tocsubsubsecnum}}
\def\l_at_paragraph{\@dottedtocline{4}{\tocsubsubsectotal}{\tocparanum}}
\def\l_at_subparagraph{\@dottedtocline{5}{\tocparatotal}{\tocsubparanum}}
\def\listoffigures{\@restonecolfalse\if_at_twocolumn\@restonecoltrue\onecolumn
\fi\section*{\listfigurename\@mkboth{{\listfigurename}}{{\listfigurename}}}
\@starttoc{lof}\if_at_restonecol\twocolumn\fi}
\def\l_at_figure{\@dottedtocline{1}{0em}{1.5em}}
\def\listoftables{\@restonecolfalse\if_at_twocolumn\@restonecoltrue\onecolumn
\fi\section*{\listtablename\@mkboth{{\listtablename}}{{\listtablename}}}
\@starttoc{lot}\if_at_restonecol\twocolumn\fi}
\let\l_at_table\l_at_figure
\renewcommand\listoffigures{%
\section*{\listfigurename
\@mkboth{\listfigurename}{\listfigurename}}%
\@starttoc{lof}%
}
\renewcommand\listoftables{%
\section*{\listtablename
\@mkboth{\listtablename}{\listtablename}}%
\@starttoc{lot}%
}
\ifx\oribibl\undefined
\ifx\citeauthoryear\undefined
\renewenvironment{thebibliography}[1]
{\section*{\refname}
\def\@biblabel##1{##1.}
\small
\list{\@biblabel{\@arabic\c_at_enumiv}}%
{\settowidth\labelwidth{\@biblabel{#1}}%
\leftmargin\labelwidth
\advance\leftmargin\labelsep
\if_at_openbib
\advance\leftmargin\bibindent
\itemindent -\bibindent
\listparindent \itemindent
\parsep \z@
\fi
\usecounter{enumiv}%
\let\p_at_enumiv\@empty
\renewcommand\theenumiv{\@arabic\c_at_enumiv}}%
\if_at_openbib
\renewcommand\newblock{\par}%
\else
\renewcommand\newblock{\hskip .11em \@plus.33em \@minus.07em}%
\fi
\sloppy\clubpenalty4000\widowpenalty4000%
\sfcode`\.=\@m}
{\def\@noitemerr
{\@latex_at_warning{Empty `thebibliography' environment}}%
\endlist}
\def\@lbibitem[#1]#2{\item[{[#1]}\hfill]\if_at_filesw
{\let\protect\noexpand\immediate
\write\@auxout{\string\bibcite{#2}{#1}}}\fi\ignorespaces}
\newcount\@tempcntc
\def\@citex[#1]#2{\if_at_filesw\immediate\write\@auxout{\string\citation{#2}}\fi
\@tempcnta\z@\@tempcntb\m_at_ne\def\@citea{}\@cite{\@for\@citeb:=#2\do
{\@ifundefined
{b@\@citeb}{\@citeo\@tempcntb\m_at_ne\@citea\def\@citea{,}{\bfseries
?}\@warning
{Citation `\@citeb' on page \thepage \space undefined}}%
{\setbox\z@\hbox{\global\@tempcntc0\csname b@\@citeb\endcsname\relax}%
\ifnum\@tempcntc=\z@ \@citeo\@tempcntb\m_at_ne
\@citea\def\@citea{,}\hbox{\csname b@\@citeb\endcsname}%
\else
\advance\@tempcntb\@ne
\ifnum\@tempcntb=\@tempcntc
\else\advance\@tempcntb\m_at_ne\@citeo
\@tempcnta\@tempcntc\@tempcntb\@tempcntc\fi\fi}}\@citeo}{#1}}
\def\@citeo{\ifnum\@tempcnta>\@tempcntb\else
\@citea\def\@citea{,\,\hskip\z_at_skip}%
\ifnum\@tempcnta=\@tempcntb\the\@tempcnta\else
{\advance\@tempcnta\@ne\ifnum\@tempcnta=\@tempcntb \else
\def\@citea{--}\fi
\advance\@tempcnta\m_at_ne\the\@tempcnta\@citea\the\@tempcntb}\fi\fi}
\else
\renewenvironment{thebibliography}[1]
{\section*{\refname}
\small
\list{}%
{\settowidth\labelwidth{}%
\leftmargin\parindent
\itemindent=-\parindent
\labelsep=\z@
\if_at_openbib
\advance\leftmargin\bibindent
\itemindent -\bibindent
\listparindent \itemindent
\parsep \z@
\fi
\usecounter{enumiv}%
\let\p_at_enumiv\@empty
\renewcommand\theenumiv{}}%
\if_at_openbib
\renewcommand\newblock{\par}%
\else
\renewcommand\newblock{\hskip .11em \@plus.33em \@minus.07em}%
\fi
\sloppy\clubpenalty4000\widowpenalty4000%
\sfcode`\.=\@m}
{\def\@noitemerr
{\@latex_at_warning{Empty `thebibliography' environment}}%
\endlist}
\def\@cite#1{#1}%
\def\@lbibitem[#1]#2{\item[]\if_at_filesw
{\def\protect##1{\string ##1\space}\immediate
\write\@auxout{\string\bibcite{#2}{#1}}}\fi\ignorespaces}
\fi
\else
\@cons\@openbib_at_code{\noexpand\small}
\fi
\def\idxquad{\hskip 10\p@}% space that divides entry from number
\def\@idxitem{\par\hangindent 10\p@}
\def\subitem{\par\setbox0=\hbox{--\enspace}% second order
\noindent\hangindent\wd0\box0}% index entry
\def\subsubitem{\par\setbox0=\hbox{--\,--\enspace}% third
\noindent\hangindent\wd0\box0}% order index entry
\def\indexspace{\par \vskip 10\p@ plus5\p@ minus3\p@\relax}
\renewenvironment{theindex}
{\@mkboth{\indexname}{\indexname}%
\thispagestyle{empty}\parindent\z@
\parskip\z@ \@plus .3\p@\relax
\let\item\par
\def\,{\relax\ifmmode\mskip\thinmuskip
\else\hskip0.2em\ignorespaces\fi}%
\normalfont\small
\begin{multicols}{2}[\@makeschapterhead{\indexname}]%
}
{\end{multicols}}
\renewcommand\footnoterule{%
\kern-3\p@
\hrule\@width 2truecm
\kern2.6\p@}
\newdimen\fnindent
\fnindent1em
\long\def\@makefntext#1{%
\parindent \fnindent%
\leftskip \fnindent%
\noindent
\llap{\hb_at_xt@1em{\hss\@makefnmark\ }}\ignorespaces#1}
\long\def\@makecaption#1#2{%
\vskip\abovecaptionskip
\sbox\@tempboxa{{\bfseries #1.} #2}%
\ifdim \wd\@tempboxa >\hsize
{\bfseries #1.} #2\par
\else
\global \@minipagefalse
\hb_at_xt@\hsize{\hfil\box\@tempboxa\hfil}%
\fi
\vskip\belowcaptionskip}
\def\fps_at_figure{htbp}
\def\fnum_at_figure{\figurename\thefigure}
\def \@floatboxreset {%
\reset_at_font
\small
\@setnobreak
\@setminipage
}
\def\fps_at_table{htbp}
\def\fnum_at_table{\tablename\thetable}
\renewenvironment{table}
{\setlength\abovecaptionskip{0\p@}%
\setlength\belowcaptionskip{10\p@}%
\@float{table}}
{\end_at_float}
\renewenvironment{table*}
{\setlength\abovecaptionskip{0\p@}%
\setlength\belowcaptionskip{10\p@}%
\@dblfloat{table}}
{\end_at_dblfloat}
\long\def\@caption#1[#2]#3{\par\addcontentsline{\csname
ext@#1\endcsname}{#1}{\protect\numberline{\csname
the#1\endcsname}{\ignorespaces #2}}\begingroup
\@parboxrestore
\@makecaption{\csname fnum@#1\endcsname}{\ignorespaces #3}\par
\endgroup}
% LaTeX does not provide a command to enter the authors institute
% addresses. The \institute command is defined here.
\newcounter{@inst}
\newcounter{@auth}
\newcounter{auco}
\def\andname{and}
\def\lastandname{\unskip, and}
\newdimen\instindent
\newbox\authrun
\newtoks\authorrunning
\newtoks\tocauthor
\newbox\titrun
\newtoks\titlerunning
\newtoks\toctitle
\def\clearheadinfo{\gdef\@author{No Author Given}%
\gdef\@title{No Title Given}%
\gdef\@subtitle{}%
\gdef\@institute{No Institute Given}%
\gdef\@thanks{}%
\global\titlerunning={}\global\authorrunning={}%
\global\toctitle={}\global\tocauthor={}}
\def\institute#1{\gdef\@institute{#1}}
\def\institutename{\par
\begingroup
\parskip=\z@
\parindent=\z@
\setcounter{@inst}{1}%
\def\and{\par\stepcounter{@inst}%
\noindent$^{\the_at_inst}$\enspace\ignorespaces}%
\setbox0=\vbox{\def\thanks##1{}\@institute}%
\ifnum\c@@inst=1\relax
\else
\setcounter{footnote}{\c@@inst}%
\setcounter{@inst}{1}%
\noindent$^{\the_at_inst}$\enspace
\fi
\ignorespaces
\@institute\par
\endgroup}
\def\@fnsymbol#1{\ensuremath{\ifcase#1\or\star\or{\star\star}\or
{\star\star\star}\or \dagger\or \ddagger\or
\mathchar "278\or \mathchar "27B\or \|\or **\or \dagger\dagger
\or \ddagger\ddagger \else\@ctrerr\fi}}
\def\inst#1{\unskip$^{#1}$}
\def\fnmsep{\unskip$^,$}
\def\email#1{{\tt#1}}
\def\url#1{#1}
\def\homedir{\~{ }}
\def\subtitle#1{\gdef\@subtitle{#1}}
\clearheadinfo
\renewcommand\maketitle{\newpage
\refstepcounter{chapter}%
\stepcounter{section}%
\setcounter{section}{0}%
\setcounter{subsection}{0}%
\setcounter{figure}{0}
\setcounter{table}{0}
\setcounter{equation}{0}
\setcounter{footnote}{0}%
\begingroup
\parindent=\z@
\renewcommand\thefootnote{\@fnsymbol\c_at_footnote}%
\if_at_twocolumn
\ifnum \col_at_number=\@ne
\@maketitle
\else
\twocolumn[\@maketitle]%
\fi
\else
\newpage
\global\@topnum\z@ % Prevents figures from going at top of page.
\@maketitle
\fi
\thispagestyle{empty}\@thanks
%
\def\\{\unskip\ \ignorespaces}\def\inst##1{\unskip{}}%
\def\thanks##1{\unskip{}}\def\fnmsep{\unskip}%
\instindent=\hsize
\advance\instindent by-\headlineindent
\if!\the\toctitle!\addcontentsline{toc}{title}{\@title}\else
\addcontentsline{toc}{title}{\the\toctitle}\fi
\if_at_runhead
\if!\the\titlerunning!\else
\edef\@title{\the\titlerunning}%
\fi
\global\setbox\titrun=\hbox{\small\rm\unboldmath\ignorespaces\@title}%
\ifdim\wd\titrun>\instindent
\typeout{Title too long for running head. Please supply}%
\typeout{a shorter form with \string\titlerunning\space prior to
\string\maketitle}%
\global\setbox\titrun=\hbox{\small\rm
Title Suppressed Due to Excessive Length}%
\fi
\xdef\@title{\copy\titrun}%
\fi
%
\if!\the\tocauthor!\relax
{\def\and{\noexpand\protect\noexpand\and}%
\protected_at_xdef\toc_at_uthor{\@author}}%
\else
\def\\{\noexpand\protect\noexpand\newline}%
\protected_at_xdef\scratch{\the\tocauthor}%
\protected_at_xdef\toc_at_uthor{\scratch}%
\fi
\addtocontents{toc}{{\protect\raggedright\protect\leftskip15\p@
\protect\rightskip\@tocrmarg
\protect\itshape\toc_at_uthor\protect\endgraf}}%
\if_at_runhead
\if!\the\authorrunning!
\value{@inst}=\value{@auth}%
\setcounter{@auth}{1}%
\else
\edef\@author{\the\authorrunning}%
\fi
\global\setbox\authrun=\hbox{\small\unboldmath\@author\unskip}%
\ifdim\wd\authrun>\instindent
\typeout{Names of authors too long for running head. Please supply}%
\typeout{a shorter form with \string\authorrunning\space prior to
\string\maketitle}%
\global\setbox\authrun=\hbox{\small\rm
Authors Suppressed Due to Excessive Length}%
\fi
\xdef\@author{\copy\authrun}%
\markboth{\@author}{\@title}%
\fi
\endgroup
\setcounter{footnote}{0}%
\clearheadinfo}
%
\def\@maketitle{\newpage
\markboth{}{}%
\def\lastand{\ifnum\value{@inst}=2\relax
\unskip{} \andname\
\else
\unskip \lastandname\
\fi}%
\def\and{\stepcounter{@auth}\relax
\ifnum\value{@auth}=\value{@inst}%
\lastand
\else
\unskip,
\fi}%
\begin{center}%
{\Large \bfseries\boldmath
\pretolerance=10000
\@title \par}\vskip .8cm
\if!\@subtitle!\else {\large \bfseries\boldmath
\vskip -.65cm
\pretolerance=10000
\@subtitle \par}\vskip .8cm\fi
\setbox0=\vbox{\setcounter{@auth}{1}\def\and{\stepcounter{@auth}}%
\def\thanks##1{}\@author}%
\global\value{@inst}=\value{@auth}%
\global\value{auco}=\value{@auth}%
\setcounter{@auth}{1}%
{\lineskip .5em
\noindent\ignorespaces
\@author\vskip.35cm}
{\small\institutename}
\end{center}%
}
% definition of the "\spnewtheorem" command.
%
% Usage:
%
% \spnewtheorem{env_nam}{caption}[within]{cap_font}{body_font}
% or \spnewtheorem{env_nam}[numbered_like]{caption}{cap_font}{body_font}
% or \spnewtheorem*{env_nam}{caption}{cap_font}{body_font}
%
% New is "cap_font" and "body_font". It stands for
% fontdefinition of the caption and the text itself.
%
% "\spnewtheorem*" gives a theorem without number.
%
% A defined spnewthoerem environment is used as described
% by Lamport.
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\@thmcountersep{}
\def\@thmcounterend{.}
\def\spnewtheorem{\@ifstar{\@sthm}{\@Sthm}}
% definition of \spnewtheorem with number
\def\@spnthm#1#2{%
\@ifnextchar[{\@spxnthm{#1}{#2}}{\@spynthm{#1}{#2}}}
\def\@Sthm#1{\@ifnextchar[{\@spothm{#1}}{\@spnthm{#1}}}
\def\@spxnthm#1#2[#3]#4#5{\expandafter\@ifdefinable\csname #1\endcsname
{\@definecounter{#1}\@addtoreset{#1}{#3}%
\expandafter\xdef\csname the#1\endcsname{\expandafter\noexpand
\csname the#3\endcsname \noexpand\@thmcountersep \@thmcounter{#1}}%
\expandafter\xdef\csname #1name\endcsname{#2}%
\global\@namedef{#1}{\@spthm{#1}{\csname #1name\endcsname}{#4}{#5}}%
\global\@namedef{end#1}{\@endtheorem}}}
\def\@spynthm#1#2#3#4{\expandafter\@ifdefinable\csname #1\endcsname
{\@definecounter{#1}%
\expandafter\xdef\csname the#1\endcsname{\@thmcounter{#1}}%
\expandafter\xdef\csname #1name\endcsname{#2}%
\global\@namedef{#1}{\@spthm{#1}{\csname #1name\endcsname}{#3}{#4}}%
\global\@namedef{end#1}{\@endtheorem}}}
\def\@spothm#1[#2]#3#4#5{%
\@ifundefined{c@#2}{\@latexerr{No theorem environment `#2' defined}\@eha}%
{\expandafter\@ifdefinable\csname #1\endcsname
{\global\@namedef{the#1}{\@nameuse{the#2}}%
\expandafter\xdef\csname #1name\endcsname{#3}%
\global\@namedef{#1}{\@spthm{#2}{\csname #1name\endcsname}{#4}{#5}}%
\global\@namedef{end#1}{\@endtheorem}}}}
\def\@spthm#1#2#3#4{\topsep 7\p@ \@plus2\p@ \@minus4\p@
\refstepcounter{#1}%
\@ifnextchar[{\@spythm{#1}{#2}{#3}{#4}}{\@spxthm{#1}{#2}{#3}{#4}}}
\def\@spxthm#1#2#3#4{\@spbegintheorem{#2}{\csname the#1\endcsname}{#3}{#4}%
\ignorespaces}
\def\@spythm#1#2#3#4[#5]{\@spopargbegintheorem{#2}{\csname
the#1\endcsname}{#5}{#3}{#4}\ignorespaces}
\def\@spbegintheorem#1#2#3#4{\trivlist
\item[\hskip\labelsep{#3#1\ #2\@thmcounterend}]#4}
\def\@spopargbegintheorem#1#2#3#4#5{\trivlist
\item[\hskip\labelsep{#4#1\ #2}]{#4(#3)\@thmcounterend\ }#5}
% definition of \spnewtheorem* without number
\def\@sthm#1#2{\@Ynthm{#1}{#2}}
\def\@Ynthm#1#2#3#4{\expandafter\@ifdefinable\csname #1\endcsname
{\global\@namedef{#1}{\@Thm{\csname #1name\endcsname}{#3}{#4}}%
\expandafter\xdef\csname #1name\endcsname{#2}%
\global\@namedef{end#1}{\@endtheorem}}}
\def\@Thm#1#2#3{\topsep 7\p@ \@plus2\p@ \@minus4\p@
\@ifnextchar[{\@Ythm{#1}{#2}{#3}}{\@Xthm{#1}{#2}{#3}}}
\def\@Xthm#1#2#3{\@Begintheorem{#1}{#2}{#3}\ignorespaces}
\def\@Ythm#1#2#3[#4]{\@Opargbegintheorem{#1}
{#4}{#2}{#3}\ignorespaces}
\def\@Begintheorem#1#2#3{#3\trivlist
\item[\hskip\labelsep{#2#1\@thmcounterend}]}
\def\@Opargbegintheorem#1#2#3#4{#4\trivlist
\item[\hskip\labelsep{#3#1}]{#3(#2)\@thmcounterend\ }}
\if_at_envcntsect
\def\@thmcountersep{.}
\spnewtheorem{theorem}{Theorem}[section]{\bfseries}{\itshape}
\else
\spnewtheorem{theorem}{Theorem}{\bfseries}{\itshape}
\if_at_envcntreset
\@addtoreset{theorem}{section}
\else
\@addtoreset{theorem}{chapter}
\fi
\fi
%definition of divers theorem environments
\spnewtheorem*{claim}{Claim}{\itshape}{\rmfamily}
\spnewtheorem*{proof}{Proof}{\itshape}{\rmfamily}
\if_at_envcntsame % alle Umgebungen wie Theorem.
\def\spn_at_wtheorem#1#2#3#4{\@spothm{#1}[theorem]{#2}{#3}{#4}}
\else % alle Umgebungen mit eigenem Zaehler
\if_at_envcntsect % mit section numeriert
\def\spn_at_wtheorem#1#2#3#4{\@spxnthm{#1}{#2}[section]{#3}{#4}}
\else % nicht mit section numeriert
\if_at_envcntreset
\def\spn_at_wtheorem#1#2#3#4{\@spynthm{#1}{#2}{#3}{#4}
\@addtoreset{#1}{section}}
\else
\def\spn_at_wtheorem#1#2#3#4{\@spynthm{#1}{#2}{#3}{#4}
\@addtoreset{#1}{chapter}}%
\fi
\fi
\fi
\spn_at_wtheorem{case}{Case}{\itshape}{\rmfamily}
\spn_at_wtheorem{conjecture}{Conjecture}{\itshape}{\rmfamily}
\spn_at_wtheorem{corollary}{Corollary}{\bfseries}{\itshape}
\spn_at_wtheorem{definition}{Definition}{\bfseries}{\itshape}
\spn_at_wtheorem{example}{Example}{\itshape}{\rmfamily}
\spn_at_wtheorem{exercise}{Exercise}{\itshape}{\rmfamily}
\spn_at_wtheorem{lemma}{Lemma}{\bfseries}{\itshape}
\spn_at_wtheorem{note}{Note}{\itshape}{\rmfamily}
\spn_at_wtheorem{problem}{Problem}{\itshape}{\rmfamily}
\spn_at_wtheorem{property}{Property}{\itshape}{\rmfamily}
\spn_at_wtheorem{proposition}{Proposition}{\bfseries}{\itshape}
\spn_at_wtheorem{question}{Question}{\itshape}{\rmfamily}
\spn_at_wtheorem{solution}{Solution}{\itshape}{\rmfamily}
\spn_at_wtheorem{remark}{Remark}{\itshape}{\rmfamily}
\def\@takefromreset#1#2{%
\def\@tempa{#1}%
\let\@tempd\@elt
\def\@elt##1{%
\def\@tempb{##1}%
\ifx\@tempa\@tempb\else
\@addtoreset{##1}{#2}%
\fi}%
\expandafter\expandafter\let\expandafter\@tempc\csname cl@#2\endcsname
\expandafter\def\csname cl@#2\endcsname{}%
\@tempc
\let\@elt\@tempd}
\def\theopargself{\def\@spopargbegintheorem##1##2##3##4##5{\trivlist
\item[\hskip\labelsep{##4##1\ ##2}]{##4##3\@thmcounterend\ }##5}
\def\@Opargbegintheorem##1##2##3##4{##4\trivlist
\item[\hskip\labelsep{##3##1}]{##3##2\@thmcounterend\ }}
}
\renewenvironment{abstract}{%
\list{}{\advance\topsep by0.35cm\relax\small
\leftmargin=1cm
\labelwidth=\z@
\listparindent=\z@
\itemindent\listparindent
\rightmargin\leftmargin}\item[\hskip\labelsep
\bfseries\abstractname]}
{\endlist}
\renewcommand{\abstractname}{Abstract.}
\renewcommand{\contentsname}{Table of Contents}
\renewcommand{\figurename}{Fig.\thinspace}
\renewcommand{\tablename}{Table~}
\newdimen\headlineindent % dimension for space between
\headlineindent=1.166cm % number and text of headings.
\def\ps_at_headings{\let\@mkboth\@gobbletwo
\let\@oddfoot\@empty\let\@evenfoot\@empty
\def\@evenhead{\normalfont\small\rlap{\thepage}\hspace{\headlineindent}%
\leftmark\hfil}
\def\@oddhead{\normalfont\small\hfil\rightmark\hspace{\headlineindent}%
\llap{\thepage}}
\def\chaptermark##1{}%
\def\sectionmark##1{}%
\def\subsectionmark##1{}}
\def\ps_at_titlepage{\let\@mkboth\@gobbletwo
\let\@oddfoot\@empty\let\@evenfoot\@empty
\def\@evenhead{\normalfont\small\rlap{\thepage}\hspace{\headlineindent}%
\hfil}
\def\@oddhead{\normalfont\small\hfil\hspace{\headlineindent}%
\llap{\thepage}}
\def\chaptermark##1{}%
\def\sectionmark##1{}%
\def\subsectionmark##1{}}
\if_at_runhead\ps_at_headings\else
\ps_at_empty\fi
\setlength\arraycolsep{1.4\p@}
\setlength\tabcolsep{1.4\p@}
\endinput
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk