\input cwebmac
\datethis % print date on listing

\def\cite#1{[{\bf #1}]}

\centerline{\bf Generating 3D Discrete Morse Functions from Point Data}
\medskip
\centerline{\bf Henry C. King}
\bigskip

This code is a companion to the paper \cite{KKM} by King, Knudson, and Mramor
which explains the theory behind why it works.
It takes a simplicial complex $K$,
which is a subcomplex of a compact 3 dimensional manifold\footnote{$^1$}
{Actually $M$ does not have to be a manifold as long as $M$
minus its vertices is a manifold and the link of each vertex is connected.
But probably in practice $M$ will be $S^3$ anyway.} $M$,
and an integer valued function $h$ on the vertices of $K$
and extends it to a discrete Morse function on $K$ in
the sense of Forman \cite{F}.
It also cancels pairs of critical $j$ and $j-1$ simplices
if they are joined by a single gradient path
and the maximum values of $h$ on the two simplices
differ by less than a given persistence $p$.


We do not actually calculate a discrete Morse function on $K$,
but instead determine the crucial information given by a discrete Morse
function.
This crucial information is the designation of some simplices as critical,
and a pairing of the remaining simplices so that each noncritical simplex is
either
paired to one of its codimension one faces or is paired to a simplex
of which it is a codimension one face.

While \cite{KKM} assumes that $h$ is injective, this program does not.
The program gets around this assumption by, in effect, perturbing $h$.

We have tested this program with $M$ a triangulation of $B\times S^1$ where
$B$ is a fixed triangulation of the Klein bottle and we vary the triangulation
of the circle $S^1$ and take a product triangulation. Then we let $K$ be $M$
minus a disc
and put a random function on the vertices of $K$.
On a 933 MHz PowerPC G4 with 640 MB running Mac OS X with 11,960,000 simplices
it runs in about 30 seconds with persistence set at 5000 out of a total
range of 65536 for the value of $h$ on the vertices.
A average run took 19.44 seconds to generate a discrete Morse function,
.57 seconds to cancel 0 and 1 simplices, 1.71 seconds to cancel 2 and 3
simplices,
and 2.92 seconds to cancel 1 and 2 simplices.
An average run with half the number of simplices, 5,980,000 and the same
persistence of 5000
took 9.21 seconds to generate a discrete Morse function,
.25 seconds to cancel 0 and 1 simplices, .46 seconds to cancel 2 and 3
simplices,
and 1.42 seconds to cancel 1 and 2 simplices.
All the above times are with the slower\_and\_finer option, which takes a bit
longer
to determine critical simplices around a given edge, but does it in such a way
that
the critical triangles descend as steeply as possible from the edge.
For 11,960,000 simplices without the slower\_and\_finer option it's about .12
seconds
faster to generate a discrete Morse function but canceling 1 and 2 simplices
is about .39 seconds slower and canceling 2 and 3 simplices is .09 seconds
slower.
For what it's worth, in the end about 4\% of the vertices were critical,
about 2.8\% of the edges were critical, about 1.7\% of the triangles were
critical, and
about .7\% of the tetrahedra were critical.


In practice, the code looks linear in the number of simplices of $M$.
The major portion of the time is spent generating a discrete Morse function.
This is linear in the number of simplices if there is an a priori bound on the
number
of simplices in the Star of a vertex.  Without such a bound I expect the time
to
be proportional to the number of vertices times the average square of the
number of
simplices in the Star of a vertex.
This square comes from local cancelation of critical simplices in the Star of a
vertex,
since presumably the number of critical simplices in the Star of a vertex is on
average
proportional to the number of all simplices in the Star of a vertex and the
average path length
is likewise proportional.
I presume that cancelling critical points would tend to be quadratic in the
number of
simplices since I would expect the number of cancelled critical points to be
proportional to the number of simplices and for each pair of cancelled critical
points the gradient path between them presumably has length proportional to the
number of simplices.  In experiments this is not evident except possibly when
cancelling 2 and 3 simplices.  I only say ``possibly" because there was a weird
phenomenon
where the time to cancel 2 and 3 simplices for the same 11,960,000 simplex
complex
was either about 1 second or about 1.8 seconds depending on when it was run.
Always the lower figure right after compilation and maybe a few more runs,
then the higher figure.  Go figure.




\bigskip
\centerline{Bibliography}
\medskip

\item{\cite{F}} R.~Forman, {\it A User's Guide to Discrete Morse Theory}\/.

\smallskip
\item{\cite{KKM}} H.~King, K.~Knudson, and N.~Mramor,
{\it Generating Discrete Morse Functions from Point Data}\/, preprint.



\N{1}{1}Extract.
Portability issue: This code requires \PB{$\&{sizeof}(\&{int})\K{}$\&{sizeof}(%
\&{void} ${}{*})$}.
This could be fixed by duplicating the ordered list routines so that there is a
version using
pointer keys rather than integer keys, or else always converting any address
keys
(which are always pointers to simplexes) to the index of the simplex.

This documentation is produced by cweave which uses the following symbols:
\item{}\PB{$\NULL$} is a NULL pointer
\item{}\PB{$\W$} is logical and (\AM\AM)
\item{} \PB{$\V$} is logical or ($\mid\mid$)
\item{} \PB{$\R$} is logical not (!)

The program has the following structure:

\Y\B\X18:Header files to include\X\6
\X19:Subroutine prototypes\X\6
\X2:Global variables\X\6
\X84:List functions\X\6
\X102:Simplex functions\X\6
\X115:Debugging output\X\6
\X117:Subroutines for constructing complexes\X\6
\X51:Subroutines finding gradient paths\X\6
\X47:Subroutines canceling a single pair of critical simplices\X\6
\X21:Subroutines canceling many pairs of critical simplices\X\6
\X3:The main routine \PB{\\{Extract}}\X\par
\fi

\M{2}\B\X2:Global variables\X${}\E{}$\6
\&{list} ${}{*}\\{crit}[\T{4}]{}$;\SHC{ lists of critical simplices of
dimensions 0,1,2, and 3 }\6
\&{long} \\{num\_simp}[\T{4}];\SHC{ number of simplices }\6
\&{vertex} ${}{*}\\{vertexlist};{}$\6
\&{edge} ${}{*}\\{elist};{}$\6
\&{triangle} ${}{*}\\{flist};{}$\6
\&{tetrahedron} ${}{*}\\{tlist}{}$;\par
\U1.\fi

\M{3}And now the main routine \PB{\\{Extract}}.
The parameter \PB{\\{vfirst}} is the first vertex of the ambient manifold $M$
containing $K$,
and \PB{\|p} is the persistence.
The complex $M$ will have information in it which allows us to determine $K$
and the function $h$ on the vertices of $K$.
We cancel 1 and 2 simplices last because this cancelation takes longer,
so it is best to reduce the number of 1 and 2 simplices as much as possible
beforehand.

\Y\B\4\X3:The main routine \PB{\\{Extract}}\X${}\E{}$\6
\&{void} \\{Extract}(\&{int} \|p)\1\1\2\2\6
${}\{{}$\1\6
\&{long} \|i;\6
\&{long} \\{t1}${},{}$ \\{t2}${},{}$ \\{t3}${},{}$ \\{t4}${},{}$ \\{t5}${},{}$ %
\\{t6};\7
${}\\{t1}\K\\{clock}(\,);{}$\6
\&{for} ${}(\|i\K\T{0};{}$ ${}\|i<\T{4};{}$ ${}\|i\PP){}$\1\5
${}\\{list\_initialize}(\\{crit}+\|i,\39{}$\&{sizeof}(\&{void} ${}{*})){}$;\2\6
\X4:Find a nonoptimized discrete Morse function on $K$\X;\6
${}\\{t2}\K\\{clock}(\,);{}$\6
\\{ExtractCancel1}(\|p);\SHC{Cancel 0 and 1 simplices with persistence less
than \PB{\|p} }\6
${}\\{t3}\K\\{clock}(\,);{}$\6
\\{ExtractCancel3}(\|p);\SHC{Cancel 2 and 3 simplices with persistence less
than \PB{\|p} }\6
${}\\{t4}\K\\{clock}(\,);{}$\6
\\{ExtractCancel2}(\|p);\SHC{Cancel 1 and 2 simplices with persistence less
than \PB{\|p} }\6
${}\\{t5}\K\\{clock}(\,);{}$\6
\8\#\&{ifdef} \\{verbose}\6
${}\\{printf}(\.{"\\nExtract\ Raw\ =\ \%d,}\)\.{\ Cancel1\ =\ \%d,\ Cance}\)%
\.{l2\ =\ \%d,\ Cancel3\ =\ \%}\)\.{d\\n"},\39\\{t2}-\\{t1},\39\\{t3}-\\{t2},%
\39\\{t5}-\\{t4},\39\\{t4}-\\{t3});{}$\6
\8\#\&{endif}\6
\4${}\}{}$\2\par
\U1.\fi

\M{4}We called this section of code \PB{\\{ExtractRaw}} in \cite{KKM}.
For each vertex \PB{\|v} of $K$,
it finds an optimal discrete Morse function on the lower Star of \PB{\|v}.
(The lower Star of \PB{\|v} is all simplices for which \PB{\|v}
is the vertex of maximal value.)
It then takes one critical edge \PB{\\{beste}} in the lower Star of \PB{\|v},
makes it noncritical, and pairs it with \PB{\|v}.
It cancels all pairs of critical simplices it can
in the lower Star so that in the end you get as few of them
as possible.  There are other algorithms which find optimal
discrete Morse functions and are presumably faster if the
lower Star has a great many simplices, but this is simple
and works fine for reasonably sized links.
It also chooses critical simplices based on the given
function values on the vertices
(especially if \PB{\\{slower\_and\_finer}} is set), which other
algorithms we know of do not.
Note that if the lower Star of \PB{\|v} is empty, you make the
vertex \PB{\|v} critical, since \PB{\|v} is a local minimum.

When we say ``steepest" below we are assuming all edges
have equal length.
If we wish to account for edges of unequal length
and pick steepest edges, triangles, etc., it would be necessary
to modify the algorithm.


\Y\B\4\X4:Find a nonoptimized discrete Morse function on $K$\X${}\E{}$\6
${}\{{}$\1\6
\&{edge} ${}{*}\\{beste}{}$;\SHC{ this will be the steepest edge from \PB{\|v}
}\6
\&{vertex} ${}{*}\|v;{}$\6
\&{int} \\{is\_lower\_Star\_empty};\6
\&{long} \\{vid};\6
\&{list} ${}{*}\\{lcrit2}{}$;\SHC{ list of critical 2 simplices in lower Star
of \PB{\|v} }\6
\&{list} ${}{*}\\{edges\_todo}{}$;\SHC{ list of unprocessed edges containing %
\PB{\|v} }\7
${}\\{list\_initialize}({\AND}\\{lcrit2},\39{}$\&{sizeof}(\&{triangle}
${}{*}));{}$\6
${}\\{list\_initialize}({\AND}\\{edges\_todo},\39{}$\&{sizeof}(\&{edge}
${}{*}));{}$\6
\&{for} ${}(\\{vid}\K\T{0};{}$ ${}\\{vid}<\\{num\_simp}[\T{0}];{}$ ${}\\{vid}%
\PP){}$\5
${}\{{}$\1\6
${}\|v\K\\{id2vertex}(\\{vid});{}$\6
\&{if} ${}(\R\\{is\_in\_K}(\|v)){}$\1\5
\&{continue};\2\6
${}\\{beste}\K\NULL;{}$\6
\X5:extract the lower Star of \PB{\|v}\X;\6
\&{if} (\\{is\_lower\_Star\_empty})\1\5
\\{make\_critical}(\|v);\2\6
\&{else}\5
${}\{{}$\1\6
${}\\{pair01}(\|v,\39\\{beste}){}$;\SHC{ pair \PB{\|v} with the steepest edge
down }\6
${}\\{LocalCancel}(\|v,\39\\{lcrit2}){}$;\SHC{ cancel critical simplices in the
lower Star of \PB{\|v} }\6
\4${}\}{}$\2\6
\4${}\}{}$\2\6
${}\\{list\_abandon}({\AND}\\{lcrit2});{}$\6
${}\\{list\_abandon}({\AND}\\{edges\_todo});{}$\6
\4${}\}{}$\2\par
\U3.\fi

\M{5}Now we determine the lower Star of \PB{\|v} and
find a discrete Morse function on it.
We do this by taking each edge \PB{\|e} in the lower Star of \PB{\|v}
and putting a discrete Morse function on its lower Star.
The lower Star of \PB{\|e} is all simplices $\sigma$ of $K$ containing
\PB{\|e} so that the maximal and next--to--maximal vertices
of $\sigma$ are in \PB{\|e}.
\Y\B\4\D$\\{mark\_edge\_done}(\|v,\|e)$ \5
$((\|e)\MG\\{type}\MRL{{\OR}{\K}}(((\|v)\E\\{get\_vertex}(\|e,\39\T{0}))\?\T{%
\^200}:\T{\^400}){}$)\par
\B\4\D$\\{edge\_marked\_done}(\|v,\|e)$ \5
$((\|e)\MG\\{type}\AND(((\|v)\E\\{get\_vertex}(\|e,\39\T{0}))\?\T{\^200}:\T{%
\^400}){}$)\par
\Y\B\4\X5:extract the lower Star of \PB{\|v}\X${}\E{}$\6
${}\{{}$\1\6
\&{edge} ${}{*}\|e;{}$\6
\&{vertex} ${}{*}\|w;{}$\6
\&{int} \\{val}${},{}$ \\{bestval}${},{}$ \\{flag};\7
${}\\{val}\K\\{value}(\|v);{}$\6
\\{list\_clear}(\\{edges\_todo});\6
${}\\{plist\_push}(\\{edges\_todo},\39\|v\MG\\{links}[\T{0}]){}$;\SHC{ push an
edge containing \PB{\|v} }\6
${}\\{is\_lower\_Star\_empty}\K\T{1}{}$;\SHC{ flag to test if lower Star(v) is
empty }\6
\&{while} ${}(\R\\{list\_is\_empty}(\\{edges\_todo})){}$\5
${}\{{}$\1\6
\X6:pop the next item \PB{\|e} from \PB{\\{edges\_todo}} which we haven't
processed yet\X\6
\X7:set \PB{\\{flag}} and reset \PB{\\{is\_lower\_Star\_empty}} if \PB{\|e} is
in lower Star(v)\X\6
\X8:add adjacent edges of \PB{\|e} to \PB{\\{edges\_todo}} and Extract lower
Star(e) if \PB{\\{flag}} is set\X\6
\4${}\}{}$\2\6
\4${}\}{}$\2\par
\Q100.
\U4.\fi

\M{6}\B\X6:pop the next item \PB{\|e} from \PB{\\{edges\_todo}} which we
haven't processed yet\X${}\E{}$\6
$\|e\K\\{plist\_pop}(\\{edges\_todo});{}$\6
\&{if} ${}(\\{edge\_marked\_done}(\|v,\39\|e)){}$\1\5
\&{continue};\2\6
${}\\{mark\_edge\_done}(\|v,\39\|e){}$;\par
\U5.\fi

\M{7}\B\X7:set \PB{\\{flag}} and reset \PB{\\{is\_lower\_Star\_empty}} if \PB{%
\|e} is in lower Star(v)\X${}\E{}$\6
$\\{flag}\K\T{0}{}$;\SHC{ default }\6
\&{if} (\\{is\_in\_K}(\|e))\5
${}\{{}$\1\6
${}\|w\K\\{smallest\_vertex\_in\_edge}(\|e);{}$\6
\&{if} ${}(\|w\I\|v{}$)\SHC{ is \PB{\|e} in lower Star(v)? }\6
${}\{{}$\1\6
${}\\{set\_value}(\|e,\39\\{val}){}$;\SHC{ fill in max value on e }\6
${}\\{is\_lower\_Star\_empty}\K\T{0}{}$;\SHC{ indicate that lower Star(v) is
not empty }\6
${}\\{flag}\K\T{1};{}$\6
\4${}\}{}$\2\6
\4${}\}{}$\2\par
\U5.\fi

\M{8}This section of code puts a discrete Morse function on the lower Star of
the edge \PB{\|e}.
Since this essentially means putting a discrete Morse function on a
subcomplex of a circle, we can use a quick algorithm to do this.
The drawback is that the choice of critical simplices has little to
do with the values of the given function on the vertices, beyond
the fact that this is used to determine the lower Star of \PB{\|e}.
A slightly slower algorithm is used if you define \PB{\\{slower\_and\_finer}}.
It chooses critical triangles
so that the value at the vertex opposite \PB{\|e} is a minimum in its connected
component of lower Star(e).
It takes a bit longer here, but experiments indicate it tends to speed up
canceling 1 and 2 simplices, presumably by making descending discs descend
faster.

The \PB{\\{state}} variable has the following significance:
\item{0} means a triangle in lower Star(e) has not yet been encountered.
\item{1} means all triangles and tetrahedra so far are in lower Star(e)
\item{2} means the last triangle was not in lower Star(e), but some previous
triangle was.
\item{3} means the last triangle was in lower Star(e),
but some previous triangles or tetrahedra weren't.

\Y\B\4\D$\\{slower\_and\_finer}$ \5
\T{1}\par
\Y\B\4\X8:add adjacent edges of \PB{\|e} to \PB{\\{edges\_todo}} and Extract
lower Star(e) if \PB{\\{flag}} is set\X${}\E{}$\6
${}\{{}$\1\6
\&{triangle} ${}{*}\|s,{}$ ${}{*}\\{bests},{}$ ${}{*}\\{sp};{}$\6
\&{tetrahedron} ${}{*}\|t;{}$\6
\&{edge} ${}{*}\\{ep};{}$\6
\&{int} \\{state}${}\K\T{0};{}$\6
\&{int} \\{bestsval};\6
\&{int} \\{first\_in\_lower\_Star};\6
\&{vertex} ${}{*}\\{min\_vertex}{}$;\SHC{  the vertex of \PB{\|s} with minimum
value }\6
\8\#\&{ifdef} \\{slower\_and\_finer}\6
\&{triangle} ${}{*}\\{bests\_in\_run},{}$ ${}{*}\\{first\_bests\_in\_run};{}$\6
\&{tetrahedron} ${}{*}\\{bestt\_in\_run},{}$ ${}{*}\\{first\_bestt\_in%
\_run};{}$\6
\&{int} \\{bestsval\_in\_run}${},{}$ \\{first\_bestsval};\6
\8\#\&{else}\6
\&{vertex} ${}{*}\\{first\_min\_vertex}{}$;\SHC{  the vertex of \PB{\\{sp}}
with minimum value }\6
\8\#\&{endif}\7
${}\|s\K\\{sp}\K\|e\MG\\{links}[\T{2}]{}$;\SHC{ a triangle containing \PB{\|e}
}\6
${}\|t\K\\{coface}(\|s,\39\T{0}){}$;\SHC{ a tetrahedron containing \PB{\|s} }\6
\&{do}\5
${}\{{}$\1\6
${}\\{ep}\K\\{other\_edge}(\|v,\39\|e,\39\|s);{}$\6
\&{if} ${}(\R\\{edge\_marked\_done}(\|v,\39\\{ep})){}$\1\5
${}\\{plist\_push}(\\{edges\_todo},\39\\{ep});{}$\2\6
\8\#\&{ifdef} \\{slower\_and\_finer}\6
\&{if} (\\{flag})\1\5
\X14:xextract s and t\X\2\6
\8\#\&{else}\6
\&{if} (\\{flag})\1\5
\X9:extract s and t\X\2\6
\8\#\&{endif}\6
${}\|t\K\\{other\_coface}(\|s,\39\|t);{}$\6
${}\|s\K\\{other\_face}(\|e,\39\|s,\39\|t);{}$\6
\4${}\}{}$\2\5
\&{while} ${}(\|s\I\\{sp});{}$\6
\8\#\&{ifdef} \\{slower\_and\_finer}\6
\&{if} (\\{flag})\1\5
\X17:xlast extract of s and t\X\2\6
\8\#\&{else}\6
\&{if} (\\{flag})\1\5
\X12:last extract of s and t\X\2\6
\8\#\&{endif}\6
\4${}\}{}$\2\par
\U5.\fi

\M{9}\B\X9:extract s and t\X${}\E{}$\6
${}\{{}$\1\6
\&{int} \\{in\_lower\_Star\_of\_e};\7
\X10:see if \PB{\|s} is in lower Star(e) and set \PB{\\{min\_vertex}} and \PB{%
\\{in\_lower\_Star\_of\_e}} accordingly\X;\6
\&{switch} (\\{state})\5
${}\{{}$\1\6
\4\&{case} \T{0}:\6
\&{if} (\\{in\_lower\_Star\_of\_e})\5
${}\{{}$\1\6
${}\\{first\_in\_lower\_Star}\K(\|s\E\\{sp}\W\\{is\_in\_K}(\|t));{}$\6
\&{if} (\\{first\_in\_lower\_Star})\5
${}\{{}$\1\6
${}\\{state}\K\T{1};{}$\6
${}\\{bests}\K\NULL;{}$\6
${}\\{first\_min\_vertex}\K\\{min\_vertex};{}$\6
\4${}\}{}$\2\6
\&{else}\5
${}\{{}$\1\6
${}\\{state}\K\T{3};{}$\6
${}\\{bests}\K\|s;{}$\6
${}\\{bestsval}\K\\{value}(\\{min\_vertex});{}$\6
\4${}\}{}$\2\6
\4${}\}{}$\2\6
\&{break};\6
\4\&{case} \T{1}:\5
\&{case} \T{3}:\6
\&{if} ${}(\R\\{in\_lower\_Star\_of\_e}){}$\5
${}\{{}$\1\6
${}\\{state}\K\T{2};{}$\6
\&{break};\6
\4${}\}{}$\2\6
\&{else} \&{if} (\\{is\_in\_K}(\|t))\5
${}\{{}$\1\6
${}\\{set\_value}(\|t,\39\\{val}){}$;\SHC{ max value on \PB{\|t} must be at
vertex \PB{\|v} }\6
${}\\{pair23}(\|s,\39\|t);{}$\6
\&{break};\6
\4${}\}{}$\SHC{ else pass through to case 2 }\2\6
\4\&{case} \T{2}:\6
\&{if} (\\{in\_lower\_Star\_of\_e})\5
${}\{{}$\1\6
\X11:make s critical xor make \PB{\\{bests}} critical and replace \PB{%
\\{bests}}\X\6
${}\\{state}\K\T{3};{}$\6
\4${}\}{}$\2\6
\&{break};\6
\4${}\}{}$\2\6
\4${}\}{}$\2\par
\U8.\fi

\M{10}\B\X10:see if \PB{\|s} is in lower Star(e) and set \PB{\\{min\_vertex}}
and \PB{\\{in\_lower\_Star\_of\_e}} accordingly\X${}\E{}$\6
$\\{in\_lower\_Star\_of\_e}\K\T{0}{}$;\SHC{ default }\6
\&{if} (\\{is\_in\_K}(\|s))\5
${}\{{}$\1\6
\&{vertex} ${}{*}\\{vlist}[\T{3}];{}$\7
${}\\{get\_triangle\_vertices}(\|s,\39\\{vlist});{}$\6
${}\\{min\_vertex}\K\\{vlist}[\\{smallest\_vertex}(\\{vlist},\39\T{3})];{}$\6
${}\\{in\_lower\_Star\_of\_e}\K(\\{vertex\_in\_edge}(\\{min\_vertex},\39\|e)<%
\T{0});{}$\6
\&{if} (\\{in\_lower\_Star\_of\_e})\1\5
${}\\{set\_value}(\|s,\39\\{val});{}$\2\6
\4${}\}{}$\2\par
\Us9\ET14.\fi

\M{11}\B\X11:make s critical xor make \PB{\\{bests}} critical and replace \PB{%
\\{bests}}\X${}\E{}$\6
\&{if} ${}(\\{bests}\E\NULL){}$\5
${}\{{}$\1\6
${}\\{bests}\K\|s;{}$\6
${}\\{bestsval}\K\\{value}(\\{min\_vertex});{}$\6
\4${}\}{}$\2\6
\&{else} \&{if} ${}(\\{value}(\\{min\_vertex})<\\{bestval}){}$\5
${}\{{}$\1\6
\\{make\_critical}(\\{bests});\6
${}\\{plist\_push}(\\{lcrit2},\39\\{bests});{}$\6
${}\\{bests}\K\|s;{}$\6
${}\\{bestsval}\K\\{value}(\\{min\_vertex});{}$\6
\4${}\}{}$\2\6
\&{else}\5
${}\{{}$\1\6
\\{make\_critical}(\|s);\6
${}\\{plist\_push}(\\{lcrit2},\39\|s){}$;\SHC{ remember all critical triangles
for \PB{\\{LocalCancel}} }\6
\4${}\}{}$\2\par
\Us9\ET12.\fi

\M{12}\B\X12:last extract of s and t\X${}\E{}$\6
\&{switch} (\\{state})\5
${}\{{}$\1\6
\4\&{case} \T{0}:\5
\X13:make \PB{\|e} critical unless it is the best candidate so far to pair with
\PB{\|v}\X\6
\&{break};\6
\4\&{case} \T{1}:\6
\\{make\_critical}(\|t);\6
${}\\{set\_value}(\|t,\39\\{val});{}$\6
${}\\{pair12}(\|e,\39\|s);{}$\6
\&{break};\6
\4\&{case} \T{3}:\6
\&{if} (\\{first\_in\_lower\_Star})\5
${}\{{}$\1\6
${}\\{pair23}(\|s,\39\|t);{}$\6
${}\\{set\_value}(\|t,\39\\{val});{}$\6
\4${}\}{}$\2\6
${}\\{pair12}(\|e,\39\\{bests});{}$\6
\&{break};\6
\4\&{case} \T{2}:\6
\&{if} (\\{first\_in\_lower\_Star})\5
${}\{{}$\1\6
${}\\{min\_vertex}\K\\{first\_min\_vertex};{}$\6
\X11:make s critical xor make \PB{\\{bests}} critical and replace \PB{%
\\{bests}}\X\6
\4${}\}{}$\2\6
${}\\{pair12}(\|e,\39\\{bests});{}$\6
\&{break};\6
\4${}\}{}$\2\par
\U8.\fi

\M{13}\B\X13:make \PB{\|e} critical unless it is the best candidate so far to
pair with \PB{\|v}\X${}\E{}$\6
\&{if} ${}(\\{beste}\E\NULL{}$)\SHC{ is it the first? }\6
${}\{{}$\1\6
${}\\{beste}\K\|e;{}$\6
${}\\{bestval}\K\\{value}(\|w);{}$\6
\4${}\}{}$\2\6
\&{else} \&{if} ${}(\\{value}(\|w)<\\{bestval}){}$\5
${}\{{}$\1\6
\\{make\_critical}(\\{beste});\6
${}\\{beste}\K\|e;{}$\6
${}\\{bestval}\K\\{value}(\|w);{}$\6
\4${}\}{}$\2\6
\&{else}\1\5
\\{make\_critical}(\|e);\2\par
\Us12\ET17.\fi

\M{14}\B\X14:xextract s and t\X${}\E{}$\6
${}\{{}$\1\6
\&{int} \\{in\_lower\_Star\_of\_e};\7
\X10:see if \PB{\|s} is in lower Star(e) and set \PB{\\{min\_vertex}} and \PB{%
\\{in\_lower\_Star\_of\_e}} accordingly\X;\6
\&{switch} (\\{state})\5
${}\{{}$\1\6
\4\&{case} \T{0}:\6
\&{if} (\\{in\_lower\_Star\_of\_e})\5
${}\{{}$\1\6
${}\\{first\_in\_lower\_Star}\K(\|s\E\\{sp}\W\\{is\_in\_K}(\|t));{}$\6
\&{if} (\\{first\_in\_lower\_Star})\1\5
${}\\{state}\K\T{1};{}$\2\6
\&{else}\1\5
${}\\{state}\K\T{3};{}$\2\6
${}\\{bests}\K\NULL;{}$\6
${}\\{bests\_in\_run}\K\|s;{}$\6
${}\\{bestt\_in\_run}\K\|t;{}$\6
${}\\{bestsval\_in\_run}\K\\{value}(\\{min\_vertex});{}$\6
\4${}\}{}$\2\6
\&{break};\6
\4\&{case} \T{1}:\5
\&{case} \T{3}:\6
\&{if} ${}(\R\\{in\_lower\_Star\_of\_e}\V\R\\{is\_in\_K}(\|t)){}$\5
${}\{{}$\1\6
\X15:make \PB{\\{bests\_in\_run}} or \PB{\\{bests}} critical and update \PB{%
\\{bests}}\X\6
\4${}\}{}$\2\6
\&{if} ${}(\R\\{in\_lower\_Star\_of\_e}){}$\5
${}\{{}$\1\6
${}\\{state}\K\T{2};{}$\6
\&{break};\6
\4${}\}{}$\2\6
\&{else} \&{if} (\\{is\_in\_K}(\|t))\5
${}\{{}$\1\6
${}\\{set\_value}(\|t,\39\\{val}){}$;\SHC{ max value on \PB{\|t} must be at
vertex \PB{\|v} }\6
\&{if} ${}(\\{value}(\\{min\_vertex})<\\{bestsval\_in\_run}){}$\1\5
\X16:replace \PB{\\{bests\_in\_run}} by \PB{\|s}\X\2\6
\&{else}\1\5
${}\\{pair23}(\|s,\39\|t);{}$\2\6
\&{break};\6
\4${}\}{}$\SHC{ else pass through to case 2 }\2\6
\4\&{case} \T{2}:\6
\&{if} (\\{in\_lower\_Star\_of\_e})\5
${}\{{}$\1\6
${}\\{bests\_in\_run}\K\|s;{}$\6
${}\\{bestt\_in\_run}\K\|t;{}$\6
${}\\{bestsval\_in\_run}\K\\{value}(\\{min\_vertex});{}$\6
${}\\{state}\K\T{3};{}$\6
\4${}\}{}$\2\6
\&{break};\6
\4${}\}{}$\2\6
\4${}\}{}$\2\par
\U8.\fi

\M{15}\B\X15:make \PB{\\{bests\_in\_run}} or \PB{\\{bests}} critical and update
\PB{\\{bests}}\X${}\E{}$\6
\&{if} ${}(\\{bests}\E\NULL){}$\5
${}\{{}$\1\6
\&{if} ${}(\\{state}\E\T{1}){}$\5
${}\{{}$\1\6
${}\\{first\_bests\_in\_run}\K\\{bests\_in\_run};{}$\6
${}\\{first\_bestt\_in\_run}\K\\{bestt\_in\_run};{}$\6
${}\\{first\_bestsval}\K\\{bestsval\_in\_run};{}$\6
\4${}\}{}$\2\6
\&{else}\5
${}\{{}$\1\6
${}\\{bests}\K\\{bests\_in\_run};{}$\6
${}\\{bestsval}\K\\{bestsval\_in\_run};{}$\6
\4${}\}{}$\2\6
\4${}\}{}$\2\6
\&{else} \&{if} ${}(\\{bestsval\_in\_run}<\\{bestval}){}$\5
${}\{{}$\1\6
\\{make\_critical}(\\{bests});\6
${}\\{plist\_push}(\\{lcrit2},\39\\{bests});{}$\6
${}\\{bests}\K\\{bests\_in\_run};{}$\6
${}\\{bestsval}\K\\{bestsval\_in\_run};{}$\6
\4${}\}{}$\2\6
\&{else}\5
${}\{{}$\1\6
\\{make\_critical}(\\{bests\_in\_run});\6
${}\\{plist\_push}(\\{lcrit2},\39\\{bests\_in\_run}){}$;\SHC{ remember all
critical triangles for \PB{\\{LocalCancel}} }\6
\4${}\}{}$\2\par
\Us14\ET17.\fi

\M{16}\B\X16:replace \PB{\\{bests\_in\_run}} by \PB{\|s}\X${}\E{}$\6
${}\{{}$\1\6
\&{triangle} ${}{*}\\{ss};{}$\6
\&{tetrahedron} ${}{*}\\{tt};{}$\7
\&{do}\5
${}\{{}$\1\6
${}\\{tt}\K\\{other\_coface}(\\{bests\_in\_run},\39\\{bestt\_in\_run});{}$\6
${}\\{ss}\K\\{r32}(\\{tt});{}$\6
${}\\{pair23}(\\{bests\_in\_run},\39\\{tt});{}$\6
${}\\{bests\_in\_run}\K\\{ss};{}$\6
${}\\{bestt\_in\_run}\K\\{tt};{}$\6
\4${}\}{}$\2\5
\&{while} ${}(\\{bestt\_in\_run}\I\|t);{}$\6
${}\\{bests\_in\_run}\K\|s;{}$\6
${}\\{bestsval\_in\_run}\K\\{value}(\\{min\_vertex});{}$\6
\4${}\}{}$\2\par
\Us14\ET17.\fi

\M{17}\B\X17:xlast extract of s and t\X${}\E{}$\6
${}\{{}$\1\6
\&{triangle} ${}{*}\\{sss};{}$\7
\&{switch} (\\{state})\5
${}\{{}$\1\6
\4\&{case} \T{0}:\5
\X13:make \PB{\|e} critical unless it is the best candidate so far to pair with
\PB{\|v}\X\6
\&{break};\6
\4\&{case} \T{1}:\6
\\{make\_critical}(\|t);\6
${}\\{set\_value}(\|t,\39\\{val});{}$\6
${}\\{pair12}(\|e,\39\\{bests\_in\_run});{}$\6
\&{break};\6
\4\&{case} \T{3}:\6
\&{if} (\\{first\_in\_lower\_Star})\5
${}\{{}$\1\6
${}\\{set\_value}(\|t,\39\\{val});{}$\6
\&{if} ${}(\\{first\_bestsval}>\\{bestsval\_in\_run}){}$\5
${}\{{}$\1\6
${}\\{sss}\K\\{bests\_in\_run};{}$\6
${}\\{bestt\_in\_run}\K\\{other\_coface}(\\{first\_bests\_in\_run},\39\\{first%
\_bestt\_in\_run});{}$\6
${}\\{bests\_in\_run}\K\\{first\_bests\_in\_run};{}$\6
\4${}\}{}$\2\6
\&{else}\1\5
${}\\{sss}\K\\{first\_bests\_in\_run};{}$\2\6
\X16:replace \PB{\\{bests\_in\_run}} by \PB{\|s}\X\6
${}\\{bests\_in\_run}\K\\{sss};{}$\6
\4${}\}{}$\2\6
\X15:make \PB{\\{bests\_in\_run}} or \PB{\\{bests}} critical and update \PB{%
\\{bests}}\X\6
${}\\{pair12}(\|e,\39\\{bests});{}$\6
\&{break};\6
\4\&{case} \T{2}:\6
\&{if} (\\{first\_in\_lower\_Star})\5
${}\{{}$\1\6
${}\\{bests\_in\_run}\K\\{first\_bests\_in\_run};{}$\6
${}\\{bestsval\_in\_run}\K\\{first\_bestsval};{}$\6
\X15:make \PB{\\{bests\_in\_run}} or \PB{\\{bests}} critical and update \PB{%
\\{bests}}\X\6
\4${}\}{}$\2\6
${}\\{pair12}(\|e,\39\\{bests});{}$\6
\&{break};\6
\4${}\}{}$\2\6
\4${}\}{}$\2\par
\U8.\fi

\M{18}A few helpful functions.

\Y\B\4\D$\\{min}(\|x,\|y)$ \5
$(((\|x)>(\|y))\?\|y:\|x{}$)\par
\B\4\D$\\{max}(\|x,\|y)$ \5
$(((\|x)>(\|y))\?\|x:\|y{}$)\par
\B\4\D$\\{in\_MorseExtract}$ \5
\T{1}\par
\Y\B\4\X18:Header files to include\X${}\E{}$\6
\8\#\&{include} \.{<stdio.h>}\6
\8\#\&{include} \.{"MorseExtract.h"}\par
\U1.\fi

\M{19}\B\X19:Subroutine prototypes\X${}\E{}$\6
\&{void} \\{abort\_message}(\&{char} ${}{*}\|s){}$;\par
\U1.\fi

\N{1}{20}Cancel Routines.
Sometimes a critical $m-1$ simplex and a critical $m$ simplex can be cancelled.
You can do this if there is exactly one gradient path between them.
A gradient path is a sequence of simplices
$\sigma_i,\sigma_{i+1},\sigma_{i+2},\ldots ,\sigma_k$ so that
for $j$ even, $\sigma_j$ is an $m$ simplex,
and $\sigma_{j-1}$ is paired with $\sigma_j$, and $\sigma_{j+1}$
is a codimension one face of $\sigma_j$.
To cancel a pair of critical simplices $\sigma$ and $\tau$,
you take the unique gradient path
$\sigma = \sigma_0,\ldots ,\sigma_{2k-1}=\tau$,
and you pair each $\sigma_{2i}$ with $\sigma_{2i+1}$
(rather than with $\sigma_{2i-1}$ as was done formerly).

\fi

\N{3}{21}Local Cancellation.
\PB{\\{LocalCancel}} cancels simplices in the lower Star of a vertex.
After doing it, you can show that you are left with a
minimal number of critical simplices.
For example, at a local maximum you would end up with only one
critical simplex, a 3 simplex.
Likewise at PL approximations of traditional smooth
Morse saddles of index $i$ you would end up with a single critical
simplex, an $i$ simplex.
\Y\B\4\X21:Subroutines canceling many pairs of critical simplices\X${}\E{}$\6
\&{void} \\{LocalCancel}(\&{vertex} ${}{*}\|v,\39{}$\&{list} ${}{*}%
\\{lcrit2}){}$\1\1\2\2\6
${}\{{}$\1\6
\&{triangle} ${}{*}\|t,{}$ ${}{*}\|s;{}$\6
\&{tetrahedron} ${}{*}\\{te}[\T{2}];{}$\6
\&{edge} ${}{*}\|e[\T{2}],{}$ ${}{*}\\{ep}[\T{2}];{}$\6
\&{int} \|j${},{}$ \|i${},{}$ \\{in};\7
\&{while} ${}(\R\\{list\_is\_empty}(\\{lcrit2}){}$)\SHC{ run through the list
of new critical 2 simplices }\6
${}\{{}$\1\6
${}\|t\K\\{plist\_pop}(\\{lcrit2});{}$\6
\X22:find the edges \PB{\|e[\T{0}]} and \PB{\|e[\T{1}]} of \PB{\|t} containing %
\PB{\|v}\X;\6
\X23:find the ends \PB{\\{ep}[\|i]} of the gradient paths starting at \PB{\|e[%
\|i]}\X;\6
\&{if} ${}(\\{ep}[\T{0}]\I\\{ep}[\T{1}]{}$)\SHC{ can we cancel? }\6
${}\{{}$\1\6
\X25:Cancel the \PB{\|t} with the best of the two edges\X;\6
\4${}\}{}$\2\6
\&{else}\5
${}\{{}$\SHC{ We can't cancel with an edge, so see if we can cancel with a 3
simplex }\1\6
\&{for} ${}(\|i\K\T{0};{}$ ${}\|i<\T{2};{}$ ${}\|i\PP){}$\5
${}\{{}$\1\6
\X24:find the 3 simplex \PB{\\{te}[\|i]} connected to \PB{$\\{coface}(\|t,%
\|i)$} by a gradient path\X;\6
\4${}\}{}$\2\6
\&{if} ${}(\\{te}[\T{0}]\I\\{te}[\T{1}]){}$\5
${}\{{}$\1\6
\X26:Cancel the \PB{\|t} with the best of the two tetrahedra\X;\6
\4${}\}{}$\2\6
\4${}\}{}$\2\6
\4${}\}{}$\2\6
\4${}\}{}$\2\par
\As27, 35\ETs43.
\U1.\fi

\M{22}\B\X22:find the edges \PB{\|e[\T{0}]} and \PB{\|e[\T{1}]} of \PB{\|t}
containing \PB{\|v}\X${}\E{}$\6
\&{for} ${}(\|i\K\T{0},\39\|j\K\T{0};{}$ ${}\|j<\T{3};{}$ ${}\|j\PP){}$\5
${}\{{}$\1\6
\&{if} ${}(\\{vertex\_in\_edge}(\|v,\39\\{get\_edge}(\|t,\39\|j))\G\T{0}){}$\5
${}\{{}$\1\6
${}\|e[\|i\PP]\K\\{get\_edge}(\|t,\39\|j);{}$\6
\4${}\}{}$\2\6
\4${}\}{}$\2\par
\U21.\fi

\M{23}\B\X23:find the ends \PB{\\{ep}[\|i]} of the gradient paths starting at %
\PB{\|e[\|i]}\X${}\E{}$\6
\&{for} ${}(\|i\K\T{0};{}$ ${}\|i<\T{2};{}$ ${}\|i\PP){}$\5
${}\{{}$\1\6
${}\\{ep}[\|i]\K\|e[\|i];{}$\6
\&{while} ${}(\R\\{is\_critical}(\\{ep}[\|i])){}$\5
${}\{{}$\1\6
\&{if} (\\{is\_paired\_down}(\\{ep}[\|i]))\5
${}\{{}$\1\6
${}\\{ep}[\|i]\K\NULL{}$;\SHC{ runs into $B_1$ so no cancelation possible }\6
\&{break};\6
\4${}\}{}$\2\6
${}\|s\K\\{r12}(\\{ep}[\|i]){}$;\SHC{ get paired triangle }\6
${}\\{ep}[\|i]\K\\{other\_edge}(\|v,\39\\{ep}[\|i],\39\|s);{}$\6
\4${}\}{}$\2\6
\4${}\}{}$\2\par
\U21.\fi

\M{24}\B\X24:find the 3 simplex \PB{\\{te}[\|i]} connected to \PB{$\\{coface}(%
\|t,\|i)$} by a gradient path\X${}\E{}$\6
$\\{te}[\|i]\K\\{coface}(\|t,\39\|i);{}$\6
${}\|s\K\|t;{}$\6
\&{while} (\\{is\_in\_K}(\\{te}[\|i]))\SHC{ while we are in K }\6
${}\{{}$\1\6
${}\\{in}\K\\{is\_in\_lower\_Star}(\\{te}[\|i],\39\|v);{}$\6
\&{if} ${}(\R\\{in}){}$\1\5
\&{break};\SHC{ see if exit lower Star }\2\6
\&{if} (\\{is\_critical}(\\{te}[\|i]))\1\5
\&{break};\SHC{ see if reached critical }\2\6
${}\|s\K\\{r32}(\\{te}[\|i]);{}$\6
${}\\{te}[\|i]\K\\{other\_coface}(\|s,\39\\{te}[\|i]);{}$\6
\4${}\}{}$\2\6
\&{if} ${}(\R\\{is\_in\_K}(\\{te}[\|i])\V\R\\{in}){}$\1\5
${}\\{te}[\|i]\K\NULL{}$;\2\par
\U21.\fi

\M{25}\B\X25:Cancel the \PB{\|t} with the best of the two edges\X${}\E{}$\6
\&{if} ${}(\\{ep}[\T{0}]\E\NULL){}$\1\5
${}\\{LocalCancel12}(\|v,\39\\{ep}[\T{1}],\39\|e[\T{1}],\39\|t);{}$\2\6
\&{else} \&{if} ${}(\\{ep}[\T{1}]\E\NULL){}$\1\5
${}\\{LocalCancel12}(\|v,\39\\{ep}[\T{0}],\39\|e[\T{0}],\39\|t);{}$\2\6
\&{else} \&{if} ${}(\\{min\_value}(\\{ep}[\T{0}],\39\T{1})>\\{min\_value}(%
\\{ep}[\T{1}],\39\T{1})){}$\1\5
${}\\{LocalCancel12}(\|v,\39\\{ep}[\T{0}],\39\|e[\T{0}],\39\|t);{}$\2\6
\&{else}\1\5
${}\\{LocalCancel12}(\|v,\39\\{ep}[\T{1}],\39\|e[\T{1}],\39\|t){}$;\2\par
\U21.\fi

\M{26}\B\X26:Cancel the \PB{\|t} with the best of the two tetrahedra\X${}\E{}$\6
\&{if} ${}(\\{te}[\T{0}]\E\NULL){}$\1\5
${}\\{Cancel23}(\|t,\39\T{1},\39\\{te}[\T{1}]);{}$\2\6
\&{else} \&{if} ${}(\\{te}[\T{1}]\E\NULL){}$\1\5
${}\\{Cancel23}(\|t,\39\T{0},\39\\{te}[\T{0}]);{}$\2\6
\&{else} \&{if} ${}(\\{min\_value}(\\{te}[\T{1}],\39\T{3})>\\{min\_value}(%
\\{te}[\T{0}],\39\T{3})){}$\1\5
${}\\{Cancel23}(\|t,\39\T{0},\39\\{te}[\T{0}]);{}$\2\6
\&{else}\1\5
${}\\{Cancel23}(\|t,\39\T{1},\39\\{te}[\T{1}]){}$;\2\par
\U21.\fi

\N{3}{27}Canceling vertices and edges.
Find all critical edges and vertices connected by a single gradient path.
Cancel the pair with smallest difference in value, as long as it's less than %
\PB{\|p}.
Keep on doing this until you can't do any more.


\Y\B\4\X21:Subroutines canceling many pairs of critical simplices\X${}\mathrel+%
\E{}$\6
\&{void} \\{ExtractCancel1}(\&{int} \|p)\1\1 $\{{}$\6
\&{olist} ${}{*}\\{c0}{}$;\SHC{ list of vertices to cancel with }\6
\&{olist} ${}{*}\\{c1}{}$;\SHC{ list of edges which can be cancelled with
vertices }\6
\&{struct} \&{ccrit1} ${}\{{}$\1\6
\&{edge} ${}{*}\|s;{}$\6
\&{long} \|c[\T{2}];\2\6
${}\}{}$ \|s;\6
\&{int} \|i;\6
\&{vertex} ${}{*}\|v[\T{2}];{}$\6
\&{int} \\{thisk};\7
${}\\{olist\_initialize}({\AND}\\{c0},\39\&{sizeof}(\&{long}));{}$\6
${}\\{olist\_initialize}({\AND}\\{c1},\39{}$\&{sizeof}(\&{struct} \&{ccrit1}));%
\6
\X28:Find all cancelable pairs and put them on lists \PB{\\{c0}} and \PB{%
\\{c1}}\X;\6
\&{while} ${}(\R\\{olist\_is\_empty}(\\{c1}))$ $\{{}$\hbox{\1}\6
$\\{thisk}\K\\{olist\_min}(\\{c1},\39{\AND}\|s){}$;\SHC{ put best candidate in %
\PB{\|s} }\6
\X30:let \PB{\|v[\|i]} be the two vertices with which \PB{\|s} can cancel\X\6
\|i $\K$ \X34:index of best vertex of \PB{$\|s.\|s$} to cancel\X;\6
\&{if} ${}(\\{is\_critical}(\|v[\|i])\W\\{thisk}\E\\{value}(\|s.\|s)-\\{value}(%
\|v[\|i])){}$\1\5
\X31:cancel with the vertex\X\2\6
\&{else}\1\5
\X32:see if we can still cancel with some other vertex and replace \PB{\|s} on %
\PB{\\{c1}}\X\hbox{\2}\2\6
$\}{}$\6
$\\{olist\_abandon}({\AND}\\{c0});{}$\6
${}\\{olist\_abandon}({\AND}\\{c1}){}$;\hbox{\2}\6
$\}{}$\par
\fi

\M{28}\B\X28:Find all cancelable pairs and put them on lists \PB{\\{c0}} and %
\PB{\\{c1}}\X${}\E{}$\6
${}\{{}$\1\6
\&{edge} ${}{*}\|e;{}$\7
\\{list\_read\_init}(\\{crit}[\T{1}]);\6
\&{while} ${}((\|e\K{}$(\&{edge} ${}{*}){}$ \\{plist\_read}(\\{crit}[%
\T{1}]))${}\I\NULL{}$)\SHC{ run through all critical edges }\6
${}\{{}$\1\6
\&{if} ${}(\R\\{is\_critical}(\|e)){}$\1\5
\\{list\_read\_delete}(\\{crit}[\T{1}]);\2\6
\&{else}\5
${}\{{}$\SHC{ find the two gradient paths descending from \PB{\|e} }\1\6
${}\|v[\T{0}]\K\\{FindGrad01}(\\{get\_vertex}(\|e,\39\T{0}),\39\\{value}(\|e)-%
\|p);{}$\6
${}\|v[\T{1}]\K\\{FindGrad01}(\\{get\_vertex}(\|e,\39\T{1}),\39\\{value}(\|e)-%
\|p);{}$\6
\&{if} ${}(\|v[\T{0}]\I\|v[\T{1}]){}$\5
${}\{{}$\1\6
\X29:put \PB{\|e} on the list \PB{\\{c1}} and put \PB{\|v[\|i]} on the list %
\PB{\\{c0}}\X;\6
\4${}\}{}$\2\6
\4${}\}{}$\2\6
\4${}\}{}$\2\6
\4${}\}{}$\2\par
\U27.\fi

\M{29}\B\X29:put \PB{\|e} on the list \PB{\\{c1}} and put \PB{\|v[\|i]} on the
list \PB{\\{c0}}\X${}\E{}$\6
$\{{}$\hbox{\1}\6
\&{long} \\{link};\7
${}\\{link}\K{-}\T{1};{}$\6
${}\|s.\|s\K\|e;{}$\6
${}\|s.\|c[\T{0}]\K(\|v[\T{0}]\E\NULL)\?{-}\T{1}:\\{olist\_find\_add}(\\{c0},%
\39{}$(\&{long}) \|v[\T{0}]${},\39{\AND}\\{link},\39\NULL);{}$\6
${}\|s.\|c[\T{1}]\K(\|v[\T{1}]\E\NULL)\?{-}\T{1}:\\{olist\_find\_add}(\\{c0},%
\39{}$(\&{long}) \|v[\T{1}]${},\39{\AND}\\{link},\39\NULL){}$;\6
\|i $\K$ \X34:index of best vertex of \PB{$\|s.\|s$} to cancel\X;\6
${}\\{olist\_add}(\\{c1},\39\\{value}(\|e)-\\{value}(\|v[\|i]),\39{\AND}%
\|s){}$;\hbox{\2}\6
$\}{}$\par
\U28.\fi

\M{30}\B\X30:let \PB{\|v[\|i]} be the two vertices with which \PB{\|s} can
cancel\X${}\E{}$\6
$\|v[\T{0}]\K(\|s.\|c[\T{0}]<\T{0})\?\NULL:{}$(\&{vertex} ${}{*}){}$ \\{olist%
\_get\_key}${}(\\{c0},\39\|s.\|c[\T{0}]);{}$\6
${}\|v[\T{1}]\K(\|s.\|c[\T{1}]<\T{0})\?\NULL:{}$(\&{vertex} ${}{*}){}$ \\{olist%
\_get\_key}${}(\\{c0},\39\|s.\|c[\T{1}]){}$;\par
\U27.\fi

\M{31}\B\X31:cancel with the vertex\X${}\E{}$\6
${}\{{}$\1\6
${}\\{Cancel01}(\|v[\|i],\39\|i,\39\|s.\|s);{}$\6
${}{*}{}$((\&{long} ${}{*}){}$ \\{olist\_entry}${}(\\{c0},\39\|s.\|c[\|i]))\K%
\|s.\|c[\T{1}-\|i]{}$;\SHC{ now any gradient path to \PB{\|v[\|i]} goes to
other vertex \PB{$\|v[\T{1}-\|i]$} }\6
\4${}\}{}$\2\par
\U27.\fi

\M{32}\B\X32:see if we can still cancel with some other vertex and replace \PB{%
\|s} on \PB{\\{c1}}\X${}\E{}$\6
$\{{}$\hbox{\1}\6
\&{int} \|m;\7
\&{for} ${}(\|i\K\T{0};{}$ ${}\|i<\T{2};{}$ ${}\|i\PP){}$\5
${}\{{}$\1\6
\&{if} ${}(\|s.\|c[\|i]<\T{0}){}$\1\5
\&{continue};\2\6
\X33:update \PB{$\|s.\|c[\|i]$} to point to a critical vertex\X\6
\4${}\}{}$\2\6
\&{if} ${}(\|s.\|c[\T{1}]\I\|s.\|c[\T{0}])$ $\{{}$\hbox{\1}\6
\|i $\K$ \X34:index of best vertex of \PB{$\|s.\|s$} to cancel\X;\6
${}\|m\K\\{value}(\|s.\|s)-\\{value}(\|v[\|i]);{}$\6
\&{if} ${}(\|m<\|p){}$\1\5
${}\\{olist\_add}(\\{c1},\39\|m,\39{\AND}\|s){}$;\hbox{\2}\2\6
$\}{}$\hbox{\2}\6
$\}{}$\par
\U27.\fi

\M{33}\B\X33:update \PB{$\|s.\|c[\|i]$} to point to a critical vertex\X${}\E{}$%
\6
${}\{{}$\1\6
\&{long} \|a;\7
\&{for} ${}(\|a\K\|s.\|c[\|i];{}$ ${}\|a\G\T{0};{}$ \,)\5
${}\{{}$\1\6
${}\|v[\|i]\K{}$(\&{vertex} ${}{*}){}$ \\{olist\_get\_key}${}(\\{c0},\39%
\|a);{}$\6
\&{if} (\\{is\_critical}(\|v[\|i]))\1\5
\&{break};\2\6
${}\|a\K{*}{}$((\&{long} ${}{*}){}$ \\{olist\_entry}${}(\\{c0},\39\|a));{}$\6
\4${}\}{}$\2\6
${}{*}{}$((\&{long} ${}{*}){}$ \\{olist\_entry}${}(\\{c0},\39\|s.\|c[\|i]))\K%
\|a;{}$\6
\&{if} ${}(\\{value}(\|v[\|i])\Z\\{value}(\|s.\|s)-\|p){}$\5
${}\{{}$\1\6
${}\|v[\|i]\K\NULL;{}$\6
${}\|s.\|c[\|i]\K{-}\T{1};{}$\6
\4${}\}{}$\2\6
\&{else}\1\5
${}\|s.\|c[\|i]\K\|a;{}$\2\6
\4${}\}{}$\2\par
\U32.\fi

\M{34}\B\X34:index of best vertex of \PB{$\|s.\|s$} to cancel\X${}\E{}$\6
$(\|v[\T{0}]\E\NULL)\?\T{1}:\hbox{}$\par${}(\|v[\T{1}]\E\NULL)\?\T{0}:\hbox{}$%
\par${}(\\{value}(\|v[\T{0}])>\\{value}(\|v[\T{1}]))\?\T{0}:\hbox{}$\par${}(%
\\{value}(\|v[\T{0}])<\\{value}(\|v[\T{1}]))\?\T{1}:\hbox{}$\par${}\\{is%
\_critical}(\|v[\T{0}])\?\T{1}:{}$\T{0}\par
\Us27, 29\ETs32.\fi

\N{3}{35}Canceling triangles and tetrahedra.
Find all critical triangles and tetrahedra connected by a single gradient path.
Cancel the pair with smallest difference in value, as long as it's less than %
\PB{\|p}.
Keep on doing this until you can't do any more.
The code is essentially the same as that used to cancel edges and vertices.

\Y\B\4\X21:Subroutines canceling many pairs of critical simplices\X${}\mathrel+%
\E{}$\6
\&{void} \\{ExtractCancel3}(\&{int} \|p)\1\1 $\{{}$\6
\&{olist} ${}{*}\\{c3}{}$;\SHC{ list of tetrahedra to cancel }\6
\&{olist} ${}{*}\\{c2}{}$;\SHC{ list of triangles which cancel with tetrahedra
}\6
\&{struct} \&{ccrit2} ${}\{{}$\1\6
\&{triangle} ${}{*}\|s;{}$\6
\&{long} \|c[\T{2}];\2\6
${}\}{}$ \|r;\6
\&{int} \|i;\6
\&{tetrahedron} ${}{*}\|t[\T{2}];{}$\6
\&{int} \\{thisk};\7
${}\\{olist\_initialize}({\AND}\\{c2},\39{}$\&{sizeof}(\&{struct} \&{ccrit2}));%
\6
${}\\{olist\_initialize}({\AND}\\{c3},\39\&{sizeof}(\&{long}));{}$\6
\X36:Find all cancelable pairs and put them on lists \PB{\\{c2}} and \PB{%
\\{c3}}\X;\6
\&{while} ${}(\R\\{olist\_is\_empty}(\\{c2}))$ $\{{}$\hbox{\1}\6
$\\{thisk}\K\\{olist\_min}(\\{c2},\39{\AND}\|r);{}$\6
\X38:let \PB{\|t[\|i]} be the two tetrahedra with which we can cancel\X\6
\|i $\K$ \X42:index of best coface of \PB{$\|r.\|s$} to cancel\X;\6
\&{if} ${}(\\{is\_critical}(\|t[\|i])\W\\{thisk}\E\\{value}(\|t[\|i])-%
\\{value}(\|r.\|s)){}$\1\5
\X39:cancel with the tetrahedron\X\2\6
\&{else}\1\5
\X40:see if we can still cancel with some other tetrahedron and replace on \PB{%
\\{c2}}\X\hbox{\2}\2\6
$\}{}$\6
$\\{olist\_abandon}({\AND}\\{c2});{}$\6
${}\\{olist\_abandon}({\AND}\\{c3}){}$;\hbox{\2}\6
$\}{}$\par
\fi

\M{36}\B\X36:Find all cancelable pairs and put them on lists \PB{\\{c2}} and %
\PB{\\{c3}}\X${}\E{}$\6
${}\{{}$\hbox{\1}\1\6
\&{triangle} ${}{*}\|s;{}$\7
\\{list\_read\_init}(\\{crit}[\T{2}]);\6
\&{while} ${}((\|s\K{}$(\&{triangle} ${}{*}){}$ \\{plist\_read}(\\{crit}[%
\T{2}]))${}\I\NULL{}$)\SHC{ go through all critical triangles }\6
${}\{{}$\1\6
\&{if} ${}(\R\\{is\_critical}(\|s)){}$\1\5
\\{list\_read\_delete}(\\{crit}[\T{2}]);\2\6
\&{else}\5
${}\{{}$\SHC{ find the beginnings of the two gradient paths ending at \PB{\|s}
}\1\6
${}\|t[\T{0}]\K\\{FindGrad23}(\\{coface}(\|s,\39\T{0}),\39\\{value}(\|s)+%
\|p);{}$\6
${}\|t[\T{1}]\K\\{FindGrad23}(\\{coface}(\|s,\39\T{1}),\39\\{value}(\|s)+%
\|p){}$;\6
\&{if} ${}(\|t[\T{0}]\I\|t[\T{1}]){}$\1\5
\X37:put \PB{\|s} on \PB{\\{c2}} and \PB{\|t[\T{0}]} and \PB{\|t[\T{1}]} on %
\PB{\\{c3}}\X\2\6
\4${}\}{}$\2\6
\4${}\}{}$\hbox{\2}\2\6
\4${}\}{}$\2\par
\U35.\fi

\M{37}\B\X37:put \PB{\|s} on \PB{\\{c2}} and \PB{\|t[\T{0}]} and \PB{\|t[%
\T{1}]} on \PB{\\{c3}}\X${}\E{}$\6
$\{{}$\hbox{\1}\6
\&{long} \\{link};\7
${}\\{link}\K{-}\T{1};{}$\6
${}\|r.\|s\K\|s;{}$\6
${}\|r.\|c[\T{0}]\K(\|t[\T{0}]\E\NULL)\?{-}\T{1}:\\{olist\_find\_add}(\\{c3},%
\39{}$(\&{long}) \|t[\T{0}]${},\39{\AND}\\{link},\39\NULL);{}$\6
${}\|r.\|c[\T{1}]\K(\|t[\T{1}]\E\NULL)\?{-}\T{1}:\\{olist\_find\_add}(\\{c3},%
\39{}$(\&{long}) \|t[\T{1}]${},\39{\AND}\\{link},\39\NULL){}$;\6
\|i $\K$ \X42:index of best coface of \PB{$\|r.\|s$} to cancel\X;\6
${}\\{olist\_add}(\\{c2},\39\\{value}(\|t[\|i])-\\{value}(\|s),\39{\AND}%
\|r){}$;\hbox{\2}\6
$\}{}$\par
\U36.\fi

\M{38}\B\X38:let \PB{\|t[\|i]} be the two tetrahedra with which we can cancel%
\X${}\E{}$\6
$\|t[\T{0}]\K(\|r.\|c[\T{0}]<\T{0})\?\NULL:{}$(\&{tetrahedron} ${}{*}){}$ %
\\{olist\_get\_key}${}(\\{c3},\39\|r.\|c[\T{0}]);{}$\6
${}\|t[\T{1}]\K(\|r.\|c[\T{1}]<\T{0})\?\NULL:{}$(\&{tetrahedron} ${}{*}){}$ %
\\{olist\_get\_key}${}(\\{c3},\39\|r.\|c[\T{1}]){}$;\par
\U35.\fi

\M{39}\B\X39:cancel with the tetrahedron\X${}\E{}$\6
${}\{{}$\1\6
${}\\{Cancel23}(\|r.\|s,\39\|i,\39\|t[\|i]);{}$\6
${}{*}{}$((\&{long} ${}{*}){}$ \\{olist\_entry}${}(\\{c3},\39\|r.\|c[\|i]))\K%
\|r.\|c[\T{1}-\|i];{}$\6
\4${}\}{}$\2\par
\U35.\fi

\M{40}\B\X40:see if we can still cancel with some other tetrahedron and replace
on \PB{\\{c2}}\X${}\E{}$\6
$\{{}$\hbox{\1}\6
\&{int} \|m;\7
\&{for} ${}(\|i\K\T{0};{}$ ${}\|i<\T{2};{}$ ${}\|i\PP){}$\5
${}\{{}$\1\6
\&{if} ${}(\|r.\|c[\|i]<\T{0}){}$\1\5
\&{continue};\2\6
\X41:update \PB{$\|r.\|c[\|i]$} to point to a critical tetrahedron\X\6
\4${}\}{}$\2\6
\&{if} ${}(\|r.\|c[\T{1}]\I\|r.\|c[\T{0}])$ $\{{}$\hbox{\1}\6
\|i $\K$ \X42:index of best coface of \PB{$\|r.\|s$} to cancel\X;\6
${}\|m\K\\{value}(\|t[\|i])-\\{value}(\|r.\|s);{}$\6
\&{if} ${}(\|m<\|p){}$\1\5
${}\\{olist\_add}(\\{c2},\39\|m,\39{\AND}\|r){}$;\hbox{\2}\2\6
$\}{}$\hbox{\2}\6
$\}{}$\par
\U35.\fi

\M{41}\B\X41:update \PB{$\|r.\|c[\|i]$} to point to a critical tetrahedron\X${}%
\E{}$\6
${}\{{}$\1\6
\&{long} \|a;\7
\&{for} ${}(\|a\K\|r.\|c[\|i];{}$ ${}\|a\G\T{0};{}$ \,)\5
${}\{{}$\1\6
${}\|t[\|i]\K{}$(\&{tetrahedron} ${}{*}){}$ \\{olist\_get\_key}${}(\\{c3},\39%
\|a);{}$\6
\&{if} (\\{is\_critical}(\|t[\|i]))\1\5
\&{break};\2\6
${}\|a\K{*}{}$((\&{long} ${}{*}){}$ \\{olist\_entry}${}(\\{c3},\39\|a));{}$\6
\4${}\}{}$\2\6
${}{*}{}$((\&{long} ${}{*}){}$ \\{olist\_entry}${}(\\{c3},\39\|r.\|c[\|i]))\K%
\|a;{}$\6
\&{if} ${}(\\{value}(\|t[\|i])\G\\{value}(\|r.\|s)+\|p){}$\5
${}\{{}$\1\6
${}\|t[\|i]\K\NULL;{}$\6
${}\|r.\|c[\|i]\K{-}\T{1};{}$\6
\4${}\}{}$\2\6
\&{else}\1\5
${}\|r.\|c[\|i]\K\|a;{}$\2\6
\4${}\}{}$\2\par
\U40.\fi

\M{42}\B\X42:index of best coface of \PB{$\|r.\|s$} to cancel\X${}\E{}$\6
$(\|t[\T{0}]\E\NULL)\?\T{1}:\hbox{}$\par${}(\|t[\T{1}]\E\NULL)\?\T{0}:\hbox{}$%
\par${}(\\{value}(\|t[\T{0}])>\\{value}(\|t[\T{1}]))\?\T{1}:\hbox{}$\par${}(%
\\{value}(\|t[\T{0}])<\\{value}(\|t[\T{1}]))\?\T{0}:\hbox{}$\par${}\\{is%
\_critical}(\|t[\T{0}])\?\T{1}:{}$\T{0}\par
\Us35, 37\ETs40.\fi

\N{3}{43}Canceling edges and triangles.
Find and cancel pairs of 1 and 2 simplices whose values differ by less than p.
This version speeds things up by not always canceling the pair with least
persistence.
In particular, after one cancelation it may become possible for
some other pair of critical simplices to cancel which could not have been
cancelled
before.  If this happens, this routine could be unaware until it has
cancelled all the pairs it knows about already.
Checking for this situation would slow down this routine dramatically.
In fact such occurrences appear to be quite rare.
For random functions on \PB{\|K} with millions of simplices and persistence
1/13 of
the range of the values of vertices, it tends to happen at most once or twice.

\Y\B\4\X21:Subroutines canceling many pairs of critical simplices\X${}\mathrel+%
\E{}$\6
\&{void} \\{ExtractCancel2}(\&{int} \|p)\1\1\2\2\6
${}\{{}$\1\6
\&{list} ${}{*}\\{changed}{}$;\SHC{ triangles whose pairing was changed by
Cancel12 }\6
\&{list} ${}{*}\\{grad\_path}{}$;\SHC{ edges in gradient path of a canceling
pair }\6
\&{olist} ${}{*}\\{goodpairs}{}$;\SHC{ cancelable critical triangles }\6
\&{int} \\{lastp};\7
${}\\{list\_initialize}({\AND}\\{changed},\39{}$\&{sizeof}(\&{triangle}
${}{*}));{}$\6
${}\\{list\_initialize}({\AND}\\{grad\_path},\39{}$\&{sizeof}(\&{edge}
${}{*}));{}$\6
${}\\{olist\_initialize}({\AND}\\{goodpairs},\39{}$\&{sizeof}(\&{triangle}
${}{*}));{}$\6
${}\\{lastp}\K\T{0};{}$\6
\&{do}\5
${}\{{}$\1\6
\X44:fill list \PB{\\{goodpairs}} with possible cancels\X\6
\&{if} (\\{olist\_is\_empty}(\\{goodpairs}))\1\5
\&{break};\2\6
\X45:cancel all pairs on \PB{\\{goodpairs}}\X\6
\4${}\}{}$\2\5
\&{while} (\T{1});\6
${}\\{list\_abandon}({\AND}\\{changed});{}$\6
${}\\{list\_abandon}({\AND}\\{grad\_path});{}$\6
${}\\{olist\_abandon}({\AND}\\{goodpairs});{}$\6
\4${}\}{}$\2\par
\fi

\M{44}\B\X44:fill list \PB{\\{goodpairs}} with possible cancels\X${}\E{}$\6
${}\{{}$\1\6
\&{triangle} ${}{*}\|t;{}$\6
\&{edge} ${}{*}\|e;{}$\7
\\{list\_read\_init}(\\{crit}[\T{2}]);\6
\&{while} ${}((\|t\K{}$(\&{triangle} ${}{*}){}$ \\{plist\_read}(\\{crit}[%
\T{2}]))${}\I\NULL{}$)\SHC{ go through all critical triangles }\6
${}\{{}$\1\6
\&{if} ${}(\R\\{is\_critical}(\|t)){}$\1\5
\\{list\_read\_delete}(\\{crit}[\T{2}]);\2\6
\&{else}\5
${}\{{}$\1\6
${}\|e\K\\{FindGradPaths12}(\|t,\39\|p,\39\NULL,\39\T{0});{}$\6
\&{if} ${}(\|e\I\NULL{}$)\SHC{ if there is a gradient path from \PB{\|t} to %
\PB{\|e} }\1\6
${}\\{olist\_add}(\\{goodpairs},\39\\{value}(\|t)-\\{value}(\|e),\39{\AND}%
\|t);{}$\2\6
\4${}\}{}$\2\6
\4${}\}{}$\2\6
\4${}\}{}$\2\par
\U43.\fi

\M{45}\B\X45:cancel all pairs on \PB{\\{goodpairs}}\X${}\E{}$\6
${}\{{}$\1\6
\&{triangle} ${}{*}\|t;{}$\6
\&{edge} ${}{*}\|e;{}$\6
\&{int} \\{bp}${},{}$ \\{thisp};\7
\&{while} ${}(\R\\{olist\_is\_empty}(\\{goodpairs})){}$\5
${}\{{}$\1\6
${}\\{bp}\K\\{olist\_min}(\\{goodpairs},\39{\AND}\|t);{}$\6
${}\|e\K\\{FindGradPaths12}(\|t,\39\|p,\39\\{grad\_path},\39\T{0});{}$\6
\&{if} ${}(\|e\E\NULL){}$\1\5
\&{continue};\SHC{ no gradient paths from \PB{\|t} found }\2\6
${}\\{thisp}\K\\{value}(\|t)-\\{value}(\|e);{}$\6
\&{if} ${}(\\{thisp}\Z\\{bp}){}$\5
${}\{{}$\1\6
\\{list\_clear}(\\{changed});\6
${}\\{Cancel12}(\|e,\39\|t,\39\\{grad\_path},\39\\{changed}){}$;\SHC{ cancel %
\PB{\|e} and \PB{\|t} }\6
\X46:fix up split-rejoin paths\X;\6
\8\#\&{ifdef} \\{verbose}\6
\&{if} ${}(\\{thisp}<\\{lastp}){}$\1\5
${}\\{printf}(\.{"\\n\ persistence\ out\ }\)\.{of\ order:\ \%d\ >\ \%d\\n"},\39%
\\{lastp},\39\\{thisp});{}$\2\6
\8\#\&{endif}\6
${}\\{lastp}\K\\{thisp};{}$\6
\4${}\}{}$\2\6
\&{else}\1\5
${}\\{olist\_add}(\\{goodpairs},\39\\{thisp},\39{\AND}\|t);{}$\2\6
\4${}\}{}$\2\6
\4${}\}{}$\2\par
\U43.\fi

\M{46}After canceling a pair of one and two simplices,
there may be new pairs of gradient paths which differ only on the
boundary of a single tetrahedron.
This code modifies the simplex pairings to eliminate this happening.
It is not clear whether it is worth doing this.
Experiments show that this tends to allow cancellation of a few more pairs
of critical one and two simplices, but not many.
Experiments also show that very little time is spent in this code.
So I have left it in.
We have not yet attempted to prove that this fixing up process always
terminates, so to be careful I have put a limit of 10000 iterations which has
so far never
been exceeded.

\Y\B\4\X46:fix up split-rejoin paths\X${}\E{}$\6
${}\{{}$\1\6
\&{int} \|i${},{}$ \|j${},{}$ \|k;\6
\&{tetrahedron} ${}{*}\\{te};{}$\7
${}\|k\K\T{0};{}$\6
\&{while} ${}(\R\\{list\_is\_empty}(\\{changed})\W\|k<\T{10000}){}$\5
${}\{{}$\1\6
${}\|t\K\\{plist\_pop}(\\{changed});{}$\6
\&{if} ${}(\|t\E\NULL){}$\1\5
\&{continue};\2\6
\&{for} ${}(\|i\K\T{0};{}$ ${}\|i<\T{2};{}$ ${}\|i\PP){}$\5
${}\{{}$\1\6
${}\\{te}\K\\{coface}(\|t,\39\|i);{}$\6
\&{if} ${}(\\{is\_in\_K}(\\{te})\W\R\\{is\_critical}(\\{te})){}$\5
${}\{{}$\1\6
${}\|j\K\\{splitrejoin}(\\{te});{}$\6
\&{if} ${}(\|j\G\T{0}){}$\5
${}\{{}$\1\6
${}\\{plist\_push}(\\{changed},\39\\{unsplitrejoin}(\\{te},\39\|j));{}$\6
${}\|k\PP;{}$\6
\4${}\}{}$\2\6
\4${}\}{}$\2\6
\4${}\}{}$\2\6
\4${}\}{}$\2\6
\&{if} ${}(\R\\{list\_is\_empty}(\\{changed})){}$\1\5
\\{printf}(\.{"May\ be\ infinite\ loo}\)\.{p\ in\ split-rejoin"});\2\6
\4${}\}{}$\2\par
\U45.\fi

\N{2}{47}Canceling pairs of Critical Simplices.
The following routine cancels a critical 1 simplex $\sigma$ containing \PB{\|v}
with a critical 2 simplex $\tau$ containing \PB{\|v}.
It speeds up the ordinary Cancel12 by assuming that
the unique gradient path from $\tau$ to $\sigma$
has all of its simplices containing \PB{\|v}.
The gradient path from $\tau$ to $\sigma$ goes through the face \PB{\\{sigmap}}
of $\tau$.

\Y\B\4\X47:Subroutines canceling a single pair of critical simplices\X${}\E{}$\6
\&{void} \\{LocalCancel12}(\&{vertex} ${}{*}\|v,\39{}$\&{edge} ${}{*}\\{sigma},%
\39{}$\&{edge} ${}{*}\\{sigmap},\39{}$\&{triangle} ${}{*}\\{tau}){}$\1\1\2\2\6
${}\{{}$\1\6
\&{edge} ${}{*}\|u;{}$\6
\&{triangle} ${}{*}\|w,{}$ ${}{*}\\{wp};{}$\7
${}\|u\K\\{sigmap};{}$\6
${}\|w\K\\{tau};{}$\6
\\{unmake\_critical}(\\{tau});\6
\&{while} ${}(\R\\{is\_critical}(\|u){}$)\SHC{ while u is noncritical }\6
${}\{{}$\1\6
${}\\{wp}\K\\{r12}(\|u);{}$\6
${}\\{pair12}(\|u,\39\|w);{}$\6
${}\|w\K\\{wp};{}$\6
${}\|u\K\\{other\_edge}(\|v,\39\|u,\39\|w);{}$\6
\4${}\}{}$\2\6
\\{unmake\_critical}(\\{sigma});\6
${}\\{pair12}(\\{sigma},\39\|w);{}$\6
\4${}\}{}$\2\par
\As48, 49\ETs50.
\U1.\fi

\M{48}The following routine cancels a critical 2 simplex $\sigma$
with a critical 3 simplex $\tau$.
The n is such that  the gradient path from $\tau$ to $\sigma$
goes through \PB{$\\{coface}(\\{sigma},\|n)$}.
It does not delete $\sigma$ and $\tau$
from \PB{\\{crit}[\T{2}]} and \PB{\\{crit}[\T{3}]}.

\Y\B\4\X47:Subroutines canceling a single pair of critical simplices\X${}%
\mathrel+\E{}$\6
\&{void} \\{Cancel23}(\&{triangle} ${}{*}\\{sigma},\39{}$\&{int} \|n${},\39{}$%
\&{tetrahedron} ${}{*}\\{tau}){}$\1\1\2\2\6
${}\{{}$\1\6
\&{triangle} ${}{*}\|s,{}$ ${}{*}\\{sp};{}$\6
\&{tetrahedron} ${}{*}\|t;{}$\7
${}\|s\K\\{sigma};{}$\6
${}\|t\K\\{coface}(\|s,\39\|n);{}$\6
\\{unmake\_critical}(\\{sigma});\6
\&{while} ${}(\R\\{is\_critical}(\|t){}$)\SHC{ while t is not critical }\6
${}\{{}$\1\6
${}\\{sp}\K\\{r32}(\|t);{}$\6
${}\\{pair23}(\|s,\39\|t);{}$\6
${}\|s\K\\{sp};{}$\6
${}\|t\K\\{other\_coface}(\|s,\39\|t);{}$\6
\4${}\}{}$\2\6
\\{unmake\_critical}(\\{tau});\6
${}\\{pair23}(\|s,\39\\{tau});{}$\6
\4${}\}{}$\2\par
\fi

\M{49}The following routine cancels a critical vertex \PB{\|v}
with a critical edge $\kappa$. It does not delete \PB{\|v} and $\kappa$
from \PB{\\{crit}[\T{0}]} and \PB{\\{crit}[\T{1}]} however.
The n is such that  the gradient path from \PB{\|v} to $\kappa$
goes through \PB{$\\{get\_vertex}(\\{kappa},\|n)$}.

\Y\B\4\X47:Subroutines canceling a single pair of critical simplices\X${}%
\mathrel+\E{}$\6
\&{void} \\{Cancel01}(\&{vertex} ${}{*}\|v,\39{}$\&{int} \|n${},\39{}$\&{edge}
${}{*}\\{kappa}){}$\1\1\2\2\6
${}\{{}$\1\6
\&{vertex} ${}{*}\|u;{}$\6
\&{edge} ${}{*}\|e,{}$ ${}{*}\\{ep};{}$\7
${}\|u\K\\{get\_vertex}(\\{kappa},\39\|n);{}$\6
${}\|e\K\\{kappa};{}$\6
\\{unmake\_critical}(\\{kappa});\6
\&{while} ${}(\R\\{is\_critical}(\|u){}$)\SHC{ while non critical }\6
${}\{{}$\1\6
${}\\{ep}\K\\{r01}(\|u);{}$\6
${}\\{pair01}(\|u,\39\|e);{}$\6
${}\|e\K\\{ep};{}$\6
${}\|u\K\\{other\_vertex\_in\_edge}(\|u,\39\|e);{}$\6
\4${}\}{}$\2\6
\\{unmake\_critical}(\|v);\6
${}\\{pair01}(\|v,\39\|e);{}$\6
\4${}\}{}$\2\par
\fi

\M{50}Cancel a critical 1 simplex $\sigma$ with a critical 2 simplex $\kappa$,
using the list of edges in the gradient path \PB{\\{grad\_path}}.
Push any 2 simplices with changed pairings to the stack \PB{\\{changed}}.
Note $\sigma$ and $\kappa$ are not deleted from \PB{\\{crit}[\T{1}]} and \PB{%
\\{crit}[\T{2}]}.

\Y\B\4\X47:Subroutines canceling a single pair of critical simplices\X${}%
\mathrel+\E{}$\6
\&{void} \\{Cancel12}(\&{edge} ${}{*}\\{sigma},\39{}$\&{triangle} ${}{*}%
\\{kappa},\39{}$\&{list} ${}{*}\\{grad\_path},\39{}$\&{list} ${}{*}%
\\{changed}){}$\1\1\2\2\6
${}\{{}$\1\6
\&{triangle} ${}{*}\|t,{}$ ${}{*}\\{nextt};{}$\6
\&{edge} ${}{*}\|e;{}$\7
\\{unmake\_critical}(\\{kappa});\6
\\{unmake\_critical}(\\{sigma});\6
${}\|t\K\\{kappa};{}$\6
\&{do}\5
${}\{{}$\1\6
${}\|e\K\\{plist\_pop}(\\{grad\_path});{}$\6
\&{if} ${}(\|e\E\\{sigma}){}$\1\5
\&{break};\2\6
${}\\{nextt}\K\\{r12}(\|e);{}$\6
${}\\{pair12}(\|e,\39\|t);{}$\6
${}\\{plist\_push}(\\{changed},\39\|t);{}$\6
${}\|t\K\\{nextt};{}$\6
\4${}\}{}$\2\5
\&{while} (\T{1});\6
${}\\{pair12}(\|e,\39\|t);{}$\6
${}\\{plist\_push}(\\{changed},\39\|t);{}$\6
\4${}\}{}$\2\par
\fi

\N{2}{51}Finding Gradient Paths. Find the end of a gradient path starting at $u%
\in K_0$.
Return the critical vertex $v$ at the end of the path,
or return \PB{$\NULL$} if $h(v)\le m$.

\Y\B\4\X51:Subroutines finding gradient paths\X${}\E{}$\6
\&{vertex} ${}{*}{}$\\{FindGrad01}(\&{vertex} ${}{*}\|u,\39{}$\&{int} \|m)\1\1%
\2\2\6
${}\{{}$\1\6
\&{vertex} ${}{*}\|v;{}$\6
\&{edge} ${}{*}\|e;{}$\7
${}\|v\K\|u;{}$\6
\&{while} ${}(\R\\{is\_critical}(\|v)\W\\{value}(\|v)>\|m){}$\5
${}\{{}$\1\6
${}\|e\K\\{r01}(\|v);{}$\6
${}\|v\K\\{other\_vertex\_in\_edge}(\|v,\39\|e);{}$\6
\4${}\}{}$\2\6
\&{if} ${}(\\{value}(\|v)\Z\|m){}$\1\5
\&{return} ${}\NULL;{}$\2\6
\&{return} \|v;\6
\4${}\}{}$\2\par
\As52, 53, 59, 60, 62\ETs72.
\U1.\fi

\M{52}Find the start of a gradient path passing through a
tetrahedron $\tau$.
Return the critical 3 simplex \PB{\|t} at the start of the path,
or return \PB{$\NULL$} if the value of \PB{\|t} is  $\ge m$ or if the path
starts
at a boundary 2 simplex.
Mark simplices deadend if we know the only gradient paths going to them
start at a boundary 2 simplex.
This is a lazy way of shortening future gradient path searches.


\Y\B\4\X51:Subroutines finding gradient paths\X${}\mathrel+\E{}$\6
\&{tetrahedron} ${}{*}{}$\\{FindGrad23}(\&{tetrahedron} ${}{*}\\{tau},\39{}$%
\&{int} \|m)\1\1\2\2\6
${}\{{}$\1\6
\&{tetrahedron} ${}{*}\|t;{}$\6
\&{triangle} ${}{*}\|s;{}$\7
\&{if} ${}(\\{tau}\E\NULL){}$\1\5
\&{return} ${}\NULL{}$;\SHC{ obsolete? }\2\6
${}\|t\K\\{tau};{}$\6
\&{while} ${}(\\{is\_in\_K}(\|t)\W\\{value}(\|t)<\|m){}$\5
${}\{{}$\1\6
\&{if} (\\{is\_critical}(\|t))\1\5
\&{return} \|t;\SHC{ reached critical t }\2\6
${}\|s\K\\{r32}(\|t);{}$\6
\&{if} (\\{is\_deadend}(\|s))\5
${}\{{}$\1\6
\\{make\_deadend}(\|t);\6
\&{return} ${}\NULL;{}$\6
\4${}\}{}$\2\6
${}\|t\K\\{other\_coface}(\|s,\39\|t);{}$\6
\&{if} (\\{is\_deadend}(\|t))\5
${}\{{}$\1\6
\\{make\_deadend}(\|s);\6
\&{return} ${}\NULL;{}$\6
\4${}\}{}$\2\6
\4${}\}{}$\2\6
\&{if} ${}(\R\\{is\_in\_K}(\|t)\W\|t\I\\{tau}){}$\1\5
\\{make\_deadend}(\|s);\2\6
\&{return} ${}\NULL;{}$\6
\4${}\}{}$\2\par
\fi

\M{53}Find all of the gradient paths starting at $\sigma$ which descend less
than $p$,
and return the best one.
If \PB{\\{grad\_path}} is not \PB{$\NULL$} return a list of the edges in the
best gradient path.
The \PB{\\{flags}} parameter, if odd, is experimental code which
changes the behavior by returning if possible a critical edge
which is connected to $\sigma$  by at least one gradient path
and could possibly generate persistent homology.

For performance reasons, the lists used are declared static
so they do not have to be initialized each time the routine is called.
I found that without doing this this routine spent
much of its time calling \PB{\\{malloc}}.
As a consequence this routine is not reentrant.
If this is ever a problem, just delete the words \PB{\&{static}} below.

Note that here and elsewhere we are essentially just searching for paths in a
graph,
in this case for nodes connected by exactly one path.
No doubt there are sophisticated and well-known algorithms for doing this
which would improve performance.
As an excercise the reader can improve on these naive implementations.

\Y\B\4\X51:Subroutines finding gradient paths\X${}\mathrel+\E{}$\6
\&{edge} ${}{*}{}$\\{FindGradPaths12}(\&{triangle} ${}{*}\\{sigma},\39{}$%
\&{int} \|p${},\39{}$\&{list} ${}{*}\\{grad\_path},\39{}$\&{int} \\{flags})\1\1%
\2\2\6
${}\{{}$\1\6
\&{static} \&{olist} ${}{*}\\{graph};{}$\6
\&{static} \&{list} ${}{*}\\{to\_do};{}$\6
\&{static} \&{list} ${}{*}\\{crits};{}$\6
\&{static} \&{int} \\{first}${}\K\T{0};{}$\6
\&{struct} \&{edge\_graph} ${}\{{}$\1\6
\&{long} \\{up};\SHC{ first uplink }\6
\&{long} \\{count};\SHC{ number of uplinks }\2\6
${}\}{}$ \|r${},{}$ ${}{*}\|q;{}$\6
\&{edge} ${}{*}\|e;{}$\6
\&{triangle} ${}{*}\|t;{}$\6
\&{long} \|m;\7
\X54:initialize lists \PB{\\{graph}}, \PB{\\{crits}}, and \PB{\\{to\_do}}\X\6
${}\|m\K{-}\T{1}{}$;\SHC{ indicate \PB{$\NULL$} uplink }\6
${}\|e\K\NULL;{}$\6
${}\|t\K\\{sigma};{}$\6
\X55:put eligible edges of \PB{\|t} on \PB{\\{graph}}, \PB{\\{crits}}, and \PB{%
\\{to\_do}}\X\6
\&{while} ${}(\R\\{list\_is\_empty}(\\{to\_do})){}$\5
${}\{{}$\1\6
${}\\{list\_pop}(\\{to\_do},\39{\AND}\|m);{}$\6
${}\|e\K{}$(\&{edge} ${}{*}){}$ \\{olist\_get\_key}${}(\\{graph},\39\|m);{}$\6
${}\|t\K\\{r12}(\|e){}$;\SHC{ get the \PB{\|t} which is paired with \PB{\|e} }\6
\X55:put eligible edges of \PB{\|t} on \PB{\\{graph}}, \PB{\\{crits}}, and \PB{%
\\{to\_do}}\X\6
\4${}\}{}$\2\6
\&{if} ${}(\\{flags}\AND\T{1}){}$\1\5
\X82:find a persistent critical edge \PB{\|e} in \PB{\\{crits}}\X\2\6
\&{else}\1\5
\X56:find the critical edge \PB{\|e} with only one grad path so \PB{\\{value}(%
\|e)} is maximized\X\2\6
\&{return} \|e;\6
\4${}\}{}$\2\par
\fi

\M{54}\B\X54:initialize lists \PB{\\{graph}}, \PB{\\{crits}}, and \PB{\\{to%
\_do}}\X${}\E{}$\6
\&{if} ${}(\\{first}\E\T{0}){}$\5
${}\{{}$\1\6
${}\\{olist\_initialize}({\AND}\\{graph},\39{}$\&{sizeof}(\&{struct} \&{edge%
\_graph}));\6
${}\\{list\_initialize}({\AND}\\{crits},\39\&{sizeof}(\&{long}));{}$\6
${}\\{list\_initialize}({\AND}\\{to\_do},\39\&{sizeof}(\&{long}));{}$\6
${}\\{first}\K\T{1};{}$\6
\4${}\}{}$\2\6
\&{else}\5
${}\{{}$\1\6
\\{olist\_clear}(\\{graph});\6
\\{list\_clear}(\\{crits});\6
\\{list\_clear}(\\{to\_do});\6
\4${}\}{}$\2\par
\U53.\fi

\M{55}\B\X55:put eligible edges of \PB{\|t} on \PB{\\{graph}}, \PB{\\{crits}},
and \PB{\\{to\_do}}\X${}\E{}$\6
${}\{{}$\1\6
\&{int} \|i;\6
\&{long} \|n;\6
\&{int} \\{flag};\6
\&{edge} ${}{*}\\{ep};{}$\6
\&{int} \\{livecount};\7
${}\\{livecount}\K\T{0};{}$\6
\&{for} ${}(\|i\K\T{0};{}$ ${}\|i<\T{3};{}$ ${}\|i\PP){}$\5
${}\{{}$\1\6
${}\\{ep}\K\\{get\_edge}(\|t,\39\|i);{}$\6
\&{if} ${}(\|e\I\\{ep}\W((\\{is\_paired\_up}(\\{ep})\W\R\\{is\_deadend}(%
\\{ep}))\V\\{is\_critical}(\\{ep}))){}$\5
${}\{{}$\1\6
${}\\{livecount}\PP;{}$\6
\&{if} ${}(\\{value}(\\{ep})\Z\\{value}(\\{sigma})-\|p){}$\1\5
\&{continue};\2\6
${}\|r.\\{up}\K\|m;{}$\6
${}\|r.\\{count}\K\T{0};{}$\6
${}\|n\K\\{olist\_find\_add}(\\{graph},\39{}$(\&{long}) \\{ep}${},\39{\AND}\|r,%
\39{\AND}\\{flag});{}$\6
${}\|q\K{}$(\&{struct} \&{edge\_graph} ${}{*}){}$ \\{olist\_entry}${}(%
\\{graph},\39\|n);{}$\6
${}\|q\MG\\{count}\PP;{}$\6
\&{if} ${}(\R\\{flag}){}$\5
${}\{{}$\1\6
\&{if} (\\{is\_critical}(\\{ep}))\1\5
${}\\{list\_push}(\\{crits},\39{\AND}\|n);{}$\2\6
\&{else}\1\5
${}\\{list\_push}(\\{to\_do},\39{\AND}\|n);{}$\2\6
\4${}\}{}$\2\6
\4${}\}{}$\2\6
\4${}\}{}$\2\6
\&{if} ${}(\\{livecount}\E\T{0}\W\|e\I\NULL){}$\1\5
\\{make\_deadend}(\|e);\2\6
\4${}\}{}$\2\par
\U53.\fi

\M{56}\B\X56:find the critical edge \PB{\|e} with only one grad path so \PB{%
\\{value}(\|e)} is maximized\X${}\E{}$\6
${}\{{}$\1\6
\&{int} \\{best\_value}${},{}$ \\{val}${},{}$ \\{bestm};\7
${}\\{bestm}\K{-}\T{1};{}$\6
\&{while} ${}(\R\\{list\_is\_empty}(\\{crits})){}$\5
${}\{{}$\1\6
${}\\{list\_pop}(\\{crits},\39{\AND}\|m);{}$\6
${}\|q\K{}$(\&{struct} \&{edge\_graph} ${}{*}){}$ \\{olist\_entry}${}(%
\\{graph},\39\|m);{}$\6
${}\\{val}\K\\{value}{}$((\&{edge} ${}{*}){}$ \\{olist\_get\_key}${}(\\{graph},%
\39\|m));{}$\6
\&{if} ${}(\|q\MG\\{count}\E\T{1}\W(\\{bestm}<\T{0}\V\\{val}>\\{best%
\_value})){}$\1\5
\X57:replace \PB{\\{bestm}} by \PB{\|m} if there's just one path to it\X\2\6
\4${}\}{}$\2\6
\&{if} ${}(\\{bestm}\G\T{0}){}$\1\5
${}\|e\K{}$(\&{edge} ${}{*}){}$ \\{olist\_get\_key}${}(\\{graph},\39%
\\{bestm});{}$\2\6
\&{else}\1\5
${}\|e\K\NULL;{}$\2\6
\&{if} ${}(\|e\I\NULL\W\\{grad\_path}\I\NULL){}$\1\5
\X58:put gradient path to \PB{\|e} on \PB{\\{grad\_path}}\X\2\6
\4${}\}{}$\2\par
\U53.\fi

\M{57}\B\X57:replace \PB{\\{bestm}} by \PB{\|m} if there's just one path to it%
\X${}\E{}$\6
${}\{{}$\1\6
\&{while} ${}(\|q\MG\\{up}\G\T{0}){}$\5
${}\{{}$\1\6
${}\|q\K{}$(\&{struct} \&{edge\_graph} ${}{*}){}$ \\{olist\_entry}${}(%
\\{graph},\39\|q\MG\\{up});{}$\6
\&{if} ${}(\|q\MG\\{count}>\T{1}){}$\1\5
\&{break};\2\6
\4${}\}{}$\2\6
\&{if} ${}(\|q\MG\\{count}\E\T{1}){}$\5
${}\{{}$\1\6
${}\\{best\_value}\K\\{val};{}$\6
${}\\{bestm}\K\|m;{}$\6
\4${}\}{}$\2\6
\4${}\}{}$\2\par
\U56.\fi

\M{58}\B\X58:put gradient path to \PB{\|e} on \PB{\\{grad\_path}}\X${}\E{}$\6
${}\{{}$\1\6
\\{list\_clear}(\\{grad\_path});\6
${}\|m\K\\{bestm};{}$\6
\&{while} ${}(\|m\G\T{0}){}$\5
${}\{{}$\1\6
${}\\{plist\_push}(\\{grad\_path},\39{}$(\&{edge} ${}{*}){}$ \\{olist\_get%
\_key}${}(\\{graph},\39\|m));{}$\6
${}\|m\K{}$((\&{struct} \&{edge\_graph} ${}{*}){}$ \\{olist\_entry}${}(%
\\{graph},\39\|m))\MG\\{up};{}$\6
\4${}\}{}$\2\6
\4${}\}{}$\2\par
\U56.\fi

\M{59}Check if \PB{\|t} is a bad tetrahedron where a gradient path could split
and rejoin.
It returns -1 if not, otherwise it returns \PB{\|i} so that \PB{$\\{get\_face}(%
\|t,\|i)$} is bad.

\Y\B\4\X51:Subroutines finding gradient paths\X${}\mathrel+\E{}$\6
\&{int} \\{splitrejoin}(\&{tetrahedron} ${}{*}\|t){}$\1\1\2\2\6
${}\{{}$\1\6
\&{int} \|i${},{}$ \|j;\6
\&{edge} ${}{*}\|e,{}$ ${}{*}\\{ep};{}$\6
\&{triangle} ${}{*}\|s;{}$\7
\&{for} ${}(\|i\K\T{0};{}$ ${}\|i<\T{4};{}$ ${}\|i\PP){}$\5
${}\{{}$\1\6
${}\|s\K\\{get\_face}(\|t,\39\|i);{}$\6
\&{if} (\\{is\_paired\_down}(\|s))\5
${}\{{}$\1\6
${}\|e\K\\{r21}(\|s);{}$\6
\&{for} ${}(\|j\K\T{0};{}$ ${}\|j<\T{3};{}$ ${}\|j\PP){}$\5
${}\{{}$\1\6
${}\\{ep}\K\\{get\_edge}(\|s,\39\|j);{}$\6
\&{if} ${}(\\{ep}\I\|e\W(\R\\{is\_paired\_up}(\\{ep})\V\\{triangle\_in%
\_tetrahedron}(\\{r12}(\\{ep}),\39\|t)<\T{0})){}$\1\5
\&{break};\2\6
\4${}\}{}$\2\6
\&{if} ${}(\|j\E\T{3}){}$\1\5
\&{return} \|i;\2\6
\4${}\}{}$\2\6
\4${}\}{}$\2\6
\&{return} ${}{-}\T{1};{}$\6
\4${}\}{}$\2\par
\fi

\M{60}Fix up a bad split rejoin tetrahedron \PB{\|t} with bad face \PB{$\\{get%
\_face}(\|t,\|n)$}.
Return the new triangle to which the bad edge is newly paired.

\Y\B\4\X51:Subroutines finding gradient paths\X${}\mathrel+\E{}$\6
\&{triangle} ${}{*}{}$\\{unsplitrejoin}(\&{tetrahedron} ${}{*}\|t,\39{}$\&{int}
\|n)\1\1\2\2\6
${}\{{}$\1\6
\&{triangle} ${}{*}\|s,{}$ ${}{*}\\{sp};{}$\6
\&{edge} ${}{*}\|e;{}$\7
${}\|s\K\\{get\_face}(\|t,\39\|n);{}$\6
${}\|e\K\\{r21}(\|s);{}$\6
${}\\{sp}\K\\{other\_face}(\|e,\39\|s,\39\|t);{}$\6
\&{if} ${}(\R\\{is\_in\_K}(\|t)){}$\1\5
\&{return} ${}\NULL{}$;\SHC{ can't fix if not in K }\2\6
\&{if} (\\{is\_critical}(\\{sp}))\1\5
\&{return} ${}\NULL{}$;\SHC{ can't fix if critical }\2\6
\&{if} (\\{is\_paired\_down}(\\{sp}))\1\5
\\{abort\_message}(\.{"tetrahedron\ surroun}\)\.{ded\ by\ 2->1\ triangle}\)%
\.{s"});\SHC{ I think this is impossible }\2\6
${}\\{pair23}(\|s,\39\|t);{}$\6
${}\\{pair12}(\|e,\39\\{sp});{}$\6
\&{return} \\{sp};\6
\4${}\}{}$\2\par
\fi

\M{61}Find all gradient paths from \PB{\\{sigma}} and return them encoded in %
\PB{\\{edges}}.
If \PB{$\\{options}\AND\T{3}\E\T{0}$}, then no pruning is done,
if \PB{$\\{options}\AND\T{3}\E\T{1}$}, then lazy pruning is done,
if \PB{$\\{options}\AND\T{3}\E\T{2}$}, then full pruning is done.
Pruning deletes edges which are not connected to a critical edge
by some gradient path.
If \PB{$\\{options}\AND\T{4}$} is set, then the count field in the edges data
structure
will be filled in.
The ordered list \PB{\\{edges}} is a list of structures \PB{\\{grad12\_struct}}
below,
one for each edge connected to \PB{\\{sigma}}, with key the list index of the
edge.
The fields \PB{\\{links}} have the following meaning for an edge \PB{\|e}:
First suppose that \PB{\|e} is paired with a triangle \PB{\|t}.
Let $i=0,1,2$ be the index of \PB{\|e} in \PB{\|t}.
Then \PB{\\{links}[\|i]} is the list index of an edge \PB{\\{ep}} so that
\PB{\|e} is contained in the triangle paired with \PB{\\{ep}}.
For \PB{$\|j\I\|i$}, \PB{\\{links}[\|j]} is the list index of another edge \PB{%
\\{epp}}
so that the \PB{\|j}-th edge of \PB{\|t} is contained in the triangle paired
with \PB{\\{epp}}.
In case \PB{\|e} is critical, then \PB{\\{links}[\T{0}]} is the list index
of an edge \PB{\\{ep}} so that \PB{\|e} is in the triangle paired with \PB{%
\\{ep}}
and \PB{\\{links}[\T{1}]} is the list index of another critical edge.
In other words we have a directed graph $G$ without cycles
so that the vertices of $G$ are edges of our complex which are paired to
triangles, or are critical.
There is a directed path in $G$ from $e'$ to $e$ if $e$ is in the
triangle paired with $e'$ and $e\ne e'$.
Then one of the links of $e$ is an $e'$ pointing to $e$,
and the other two are $e''$ pointing to an edge also pointed to by $e$.
It still sounds confusing but it works.
\PB{$\\{flags}\AND\T{3}$} is the index of the edge in its paired triangle, or 3
if critical;
If complete pruning is requested (\PB{$\\{options}\AND\T{3}\E\T{2}$}) and
\PB{$\\{flags}\AND\T{4}$} is set, then the edge is connected to a critical
edge by a gradient path, i.e., it cannot be pruned.
The return value is the list index of a critical edge,
so that all critical edges are obtained by following the \PB{\\{links}[\T{1}]}.
The \PB{\\{count}} field gives the signed number of gradient paths
going through the edge (counting orientation).
If \PB{\\{flags} $\AND$}8 is set, then the count field in the edges data
structure
is filled in.
If \PB{$\\{flags}\AND\T{16}$} is set, then the count field in the edges data
structure
cannot yet be filled in.

\Y\B\4\X61:\.{MorseExtract.h }\X${}\E{}$\6
\&{struct} \&{grad12\_struct} ${}\{{}$\1\6
\&{long} \\{links}[\T{3}];\6
\&{long} \\{count};\6
\&{int} \\{flags};\2\6
${}\}{}$;\par
\As83, 88, 92, 101, 107, 111, 116\ETs128.\fi

\M{62}\B\X51:Subroutines finding gradient paths\X${}\mathrel+\E{}$\6
\&{long} \\{find\_all\_grad12\_paths}(\&{triangle} ${}{*}\\{sigma},\39{}$%
\&{olist} ${}{*}\\{edges},\39{}$\&{int} \\{options})\1\1\2\2\6
${}\{{}$\1\6
\&{int} \\{kk}${}\K{-}\T{1};{}$\6
\&{edge} ${}{*}\\{ep};{}$\6
\&{long} \\{todo}${}\K{-}\T{2};{}$\6
\&{long} ${}\this;{}$\6
\&{long} \\{crit}${}\K{-}\T{1};{}$\6
\&{struct} \&{grad12\_struct} ${}{*}\|p;{}$\6
\&{triangle} ${}{*}\|f;{}$\7
\\{olist\_clear}(\\{edges});\6
\&{do}\5
${}\{{}$\1\6
${}\this\K\\{todo};{}$\6
\&{if} ${}(\this\G\T{0}){}$\5
${}\{{}$\1\6
${}\|p\K{}$(\&{struct} \&{grad12\_struct} ${}{*}){}$ \\{olist\_entry}${}(%
\\{edges},\39\this);{}$\6
${}\\{ep}\K\\{id2edge}(\\{olist\_get\_key}(\\{edges},\39\this));{}$\6
${}\\{kk}\K\|p\MG\\{flags}\AND\T{3};{}$\6
\&{if} (\\{kk})\5
${}\{{}$\1\6
${}\\{todo}\K\|p\MG\\{links}[\T{0}];{}$\6
${}\|p\MG\\{links}[\T{0}]\K{-}\T{1};{}$\6
\4${}\}{}$\2\6
\&{else}\5
${}\{{}$\1\6
${}\\{todo}\K\|p\MG\\{links}[\T{1}];{}$\6
${}\|p\MG\\{links}[\T{1}]\K{-}\T{1};{}$\6
\4${}\}{}$\2\6
${}\|f\K\\{r12}(\\{ep});{}$\6
\4${}\}{}$\2\6
\&{else}\1\5
${}\|f\K\\{sigma};{}$\2\6
\X63:find-add edges of \PB{\|f} to \PB{\\{edges}} if needed\X\6
\4${}\}{}$\2\5
\&{while} ${}(\\{todo}\G\T{0});{}$\6
\&{if} ${}((\\{options}\AND\T{3})\E\T{2}){}$\1\5
\X65:prune \PB{\\{edges}}\X\2\6
\&{if} ${}(\\{options}\AND\T{4}){}$\1\5
\X67:fill in count field\X\2\6
\&{return} \\{crit};\6
\4${}\}{}$\2\par
\fi

\M{63}\B\X63:find-add edges of \PB{\|f} to \PB{\\{edges}} if needed\X${}\E{}$\6
${}\{{}$\1\6
\&{int} \|k;\6
\&{edge} ${}{*}\|e;{}$\6
\&{int} \\{livecount}${}\K\T{0};{}$\7
\&{for} ${}(\|k\K\T{0};{}$ ${}\|k<\T{3};{}$ ${}\|k\PP){}$\5
${}\{{}$\1\6
\&{if} ${}(\|k\E\\{kk}){}$\1\5
\&{continue};\2\6
${}\|e\K\\{get\_edge}(\|f,\39\|k);{}$\6
\X64:find-add \PB{\|e} to \PB{\\{edges}} if needed\X\6
\4${}\}{}$\2\6
\&{if} ${}(\\{livecount}\E\T{0}\W(\\{options}\AND\T{3})\W\this\G\T{0}){}$\5
${}\{{}$\1\6
\\{make\_deadend}(\|f);\6
\\{make\_deadend}(\\{ep});\6
\4${}\}{}$\2\6
\4${}\}{}$\2\par
\U62.\fi

\M{64}\B\X64:find-add \PB{\|e} to \PB{\\{edges}} if needed\X${}\E{}$\6
${}\{{}$\1\6
\&{struct} \&{grad12\_struct} \|r${},{}$ ${}{*}\|q;{}$\6
\&{triangle} ${}{*}\|t;{}$\6
\&{int} \\{flag};\6
\&{int} \|j;\6
\&{long} \\{id};\7
\&{if} ${}(\\{is\_paired\_up}(\|e)\W(\R\\{is\_deadend}(\|e)\V(\\{options}\AND%
\T{3})\E\T{0})){}$\5
${}\{{}$\1\6
${}\\{livecount}\PP;{}$\6
${}\\{id}\K\\{olist\_find\_add}(\\{edges},\39\\{edge\_id}(\|e),\39{\AND}\|r,%
\39{\AND}\\{flag});{}$\6
${}\|q\K{}$(\&{struct} \&{grad12\_struct} ${}{*}){}$ \\{olist\_entry}${}(%
\\{edges},\39\\{id});{}$\6
\&{if} (\\{flag})\SHC{ already on list }\6
${}\{{}$\1\6
${}\|p\MG\\{links}[\|k]\K\|q\MG\\{links}[\|q\MG\\{flags}\AND\T{3}];{}$\6
${}\|q\MG\\{links}[\|q\MG\\{flags}\AND\T{3}]\K\this;{}$\6
\4${}\}{}$\2\6
\&{else}\SHC{ newly added to list }\6
${}\{{}$\1\6
${}\|q\MG\\{links}[\T{1}]\K\|q\MG\\{links}[\T{2}]\K{-}\T{1};{}$\6
${}\|t\K\\{r12}(\|e);{}$\6
${}\|q\MG\\{flags}\K\\{edge\_in\_triangle}(\|e,\39\|t);{}$\6
${}\|q\MG\\{links}[\|q\MG\\{flags}]\K\this;{}$\6
\&{if} ${}(\|q\MG\\{flags}){}$\1\5
${}\|q\MG\\{links}[\T{0}]\K\\{todo};{}$\2\6
\&{else}\1\5
${}\|q\MG\\{links}[\T{1}]\K\\{todo};{}$\2\6
${}\\{todo}\K\\{id};{}$\6
\4${}\}{}$\2\6
\4${}\}{}$\2\6
\&{else} \&{if} (\\{is\_critical}(\|e))\5
${}\{{}$\1\6
${}\\{livecount}\PP;{}$\6
${}\\{id}\K\\{olist\_find\_add}(\\{edges},\39\\{edge\_id}(\|e),\39{\AND}\|r,%
\39{\AND}\\{flag});{}$\6
${}\|q\K{}$(\&{struct} \&{grad12\_struct} ${}{*}){}$ \\{olist\_entry}${}(%
\\{edges},\39\\{id});{}$\6
\&{if} (\\{flag})\5
${}\{{}$\1\6
${}\|p\MG\\{links}[\|k]\K\|q\MG\\{links}[\T{0}];{}$\6
${}\|q\MG\\{links}[\T{0}]\K\this;{}$\6
\4${}\}{}$\2\6
\&{else}\5
${}\{{}$\1\6
${}\|q\MG\\{links}[\T{0}]\K\this;{}$\6
${}\|q\MG\\{links}[\T{1}]\K\\{crit};{}$\6
${}\|q\MG\\{flags}\K\T{3};{}$\6
${}\\{crit}\K\\{id};{}$\6
\4${}\}{}$\2\6
\4${}\}{}$\2\6
\4${}\}{}$\2\par
\U63.\fi

\M{65}\B\X65:prune \PB{\\{edges}}\X${}\E{}$\6
${}\{{}$\1\6
\&{long} \|j;\6
\&{struct} \&{grad12\_struct} ${}{*}\|p;{}$\6
\&{edge} ${}{*}\|e;{}$\6
\&{list} ${}{*}\\{todo\_list};{}$\7
${}\\{list\_initialize}({\AND}\\{todo\_list},\39\&{sizeof}(\&{long}));{}$\6
${}\\{todo}\K\\{crit};{}$\6
\&{while} ${}(\\{todo}\G\T{0}){}$\5
${}\{{}$\1\6
\X66:mark all edges on critical paths to this critical edge\X\6
${}\|p\K{}$(\&{struct} \&{grad12\_struct} ${}{*}){}$ \\{olist\_entry}${}(%
\\{edges},\39\\{todo});{}$\6
${}\\{todo}\K\|p\MG\\{links}[\T{1}];{}$\6
\4${}\}{}$\2\6
${}\\{list\_abandon}({\AND}\\{todo\_list});{}$\6
\&{for} ${}(\|j\K\T{0};{}$ ${}\|j<\\{olist\_count}(\\{edges});{}$ ${}\|j\PP){}$%
\5
${}\{{}$\1\6
${}\|p\K{}$(\&{struct} \&{grad12\_struct} ${}{*}){}$ \\{olist\_entry}${}(%
\\{edges},\39\|j);{}$\6
\&{if} ${}(\|p\MG\\{flags}\AND\T{4}){}$\1\5
\&{continue};\2\6
${}\|e\K\\{id2edge}(\\{olist\_get\_key}(\\{edges},\39\|j));{}$\6
\\{make\_deadend}(\|e);\6
\\{make\_deadend}(\\{r12}(\|e));\6
\4${}\}{}$\2\6
\4${}\}{}$\2\par
\U62.\fi

\M{66}\B\X66:mark all edges on critical paths to this critical edge\X${}\E{}$\6
${}\{{}$\1\6
\&{long} \\{next}${},{}$ \\{id};\6
\&{struct} \&{grad12\_struct} ${}{*}\|q;{}$\6
\&{int} \|i;\7
\\{list\_clear}(\\{todo\_list});\6
${}\\{list\_push}(\\{todo\_list},\39{\AND}\\{todo});{}$\6
\&{while} ${}(\R\\{list\_is\_empty}(\\{todo\_list})){}$\5
${}\{{}$\1\6
${}\\{list\_pop}(\\{todo\_list},\39{\AND}\\{next});{}$\6
${}\|p\K{}$(\&{struct} \&{grad12\_struct} ${}{*}){}$ \\{olist\_entry}${}(%
\\{edges},\39\\{next});{}$\6
\&{if} ${}(\|p\MG\\{flags}\AND\T{4}){}$\1\5
\&{continue};\2\6
${}\|p\MG\\{flags}\MRL{{\OR}{\K}}\T{4};{}$\6
${}\|i\K\|p\MG\\{flags}\AND\T{3};{}$\6
\&{if} ${}(\|i\E\T{3}){}$\1\5
${}\\{id}\K\|p\MG\\{links}[\T{0}];{}$\2\6
\&{else}\1\5
${}\\{id}\K\|p\MG\\{links}[\|i];{}$\2\6
${}\|e\K\\{id2edge}(\\{olist\_get\_key}(\\{edges},\39\\{next}));{}$\6
\&{while} ${}(\\{id}\G\T{0}){}$\5
${}\{{}$\1\6
${}\|q\K{}$(\&{struct} \&{grad12\_struct} ${}{*}){}$ \\{olist\_entry}${}(%
\\{edges},\39\\{id});{}$\6
${}\\{ep}\K\\{id2edge}(\\{olist\_get\_key}(\\{edges},\39\\{id}));{}$\6
\&{if} ${}((\|q\MG\\{flags}\AND\T{4})\E\T{0}){}$\5
${}\{{}$\1\6
${}\\{list\_push}(\\{todo\_list},\39{\AND}\\{id});{}$\6
\4${}\}{}$\2\6
${}\|i\K\\{edge\_in\_triangle}(\|e,\39\\{r12}(\\{ep}));{}$\6
\&{if} ${}(\|i<\T{0}){}$\1\5
\\{abort\_message}(\.{"error"});\2\6
${}\\{id}\K\|q\MG\\{links}[\|i];{}$\6
\4${}\}{}$\2\6
\4${}\}{}$\2\6
\4${}\}{}$\2\par
\U65.\fi

\M{67}\B\X67:fill in count field\X${}\E{}$\6
${}\{{}$\1\6
\&{list} ${}{*}\\{todo\_list};{}$\6
\&{long} \\{id}${}\K{-}\T{1},{}$ ${}{*}\\{idp};{}$\6
\&{struct} \&{grad12\_struct} ${}{*}\|q;{}$\6
\&{int} \\{error\_check};\7
${}\\{list\_initialize}({\AND}\\{todo\_list},\39\&{sizeof}(\&{long}));{}$\6
${}\\{list\_push}(\\{todo\_list},\39{\AND}\\{id});{}$\6
\&{while} ${}(\R\\{list\_is\_empty}(\\{todo\_list})){}$\5
${}\{{}$\1\6
\\{list\_read\_init}(\\{todo\_list});\6
${}\\{error\_check}\K\T{1};{}$\6
\&{while} ${}((\\{idp}\K{}$(\&{long} ${}{*}){}$ \\{list\_read}(\\{todo%
\_list}))${}\I\NULL){}$\5
${}\{{}$\1\6
\&{if} ${}({*}\\{idp}<\T{0}){}$\5
${}\{{}$\1\6
\\{list\_read\_delete}(\\{todo\_list});\6
${}\\{kk}\K{-}\T{1};{}$\6
${}\|f\K\\{sigma};{}$\6
\4${}\}{}$\2\6
\&{else}\5
${}\{{}$\1\6
${}\|p\K{}$(\&{struct} \&{grad12\_struct} ${}{*}){}$ \\{olist\_entry}${}(%
\\{edges},\39{*}\\{idp});{}$\6
\&{if} ${}(\|p\MG\\{flags}\AND\T{24}){}$\1\5
\&{continue};\2\6
\X68:see if all incoming faces are counted\X\6
\4${}\}{}$\2\6
\&{if} ${}(\|f\I\NULL){}$\5
${}\{{}$\1\6
${}\\{error\_check}\K\T{0};{}$\6
\X69:add edges of \PB{\|f} to \PB{\\{todo\_list}}\X\6
\4${}\}{}$\2\6
\4${}\}{}$\2\6
\&{if} ${}(\\{error\_check}\W\R\\{list\_is\_empty}(\\{todo\_list})){}$\1\5
\\{abort\_message}(\.{"count\ error"});\2\6
\4${}\}{}$\2\6
${}\\{list\_abandon}({\AND}\\{todo\_list});{}$\6
\4${}\}{}$\2\par
\U62.\fi

\M{68}\B\X68:see if all incoming faces are counted\X${}\E{}$\6
${}\{{}$\1\6
\&{edge} ${}{*}\|e;{}$\6
\&{int} \|i;\7
${}\\{ep}\K\\{id2edge}(\\{olist\_get\_key}(\\{edges},\39{*}\\{idp}));{}$\6
${}\\{kk}\K\|p\MG\\{flags}\AND\T{3};{}$\6
\&{if} ${}(\\{kk}\E\T{3}){}$\1\5
${}\\{id}\K\|p\MG\\{links}[\T{0}];{}$\2\6
\&{else}\1\5
${}\\{id}\K\|p\MG\\{links}[\\{kk}];{}$\2\6
\&{while} ${}(\\{id}\G\T{0}){}$\5
${}\{{}$\1\6
${}\|q\K{}$(\&{struct} \&{grad12\_struct} ${}{*}){}$ \\{olist\_entry}${}(%
\\{edges},\39\\{id});{}$\6
\&{if} ${}((\|q\MG\\{flags}\AND\T{8})\E\T{0}){}$\1\5
\&{break};\2\6
${}\|e\K\\{id2edge}(\\{olist\_get\_key}(\\{edges},\39\\{id}));{}$\6
${}\|i\K\\{edge\_in\_triangle}(\\{ep},\39\\{r12}(\|e));{}$\6
${}\\{id}\K\|q\MG\\{links}[\|i];{}$\6
\4${}\}{}$\2\6
\&{if} ${}(\\{id}<\T{0}){}$\1\5
\X71:count incoming faces to \PB{\\{ep}}\X\2\6
\&{else}\1\5
${}\|p\MG\\{flags}\MRL{{\OR}{\K}}\T{16};{}$\2\6
\&{if} ${}(\\{id}\G\T{0}\V\\{is\_critical}(\\{ep})){}$\1\5
${}\|f\K\NULL;{}$\2\6
\&{else}\1\5
${}\|f\K\\{r12}(\\{ep});{}$\2\6
\4${}\}{}$\2\par
\U67.\fi

\M{69}\B\X69:add edges of \PB{\|f} to \PB{\\{todo\_list}}\X${}\E{}$\6
${}\{{}$\1\6
\&{int} \|k;\6
\&{edge} ${}{*}\|e;{}$\7
\&{for} ${}(\|k\K\T{0};{}$ ${}\|k<\T{3};{}$ ${}\|k\PP){}$\5
${}\{{}$\1\6
\&{if} ${}(\|k\E\\{kk}){}$\1\5
\&{continue};\2\6
${}\|e\K\\{get\_edge}(\|f,\39\|k);{}$\6
\X70:add \PB{\|e} to \PB{\\{todo\_list}}\X\6
\4${}\}{}$\2\6
\4${}\}{}$\2\par
\U67.\fi

\M{70}\B\X70:add \PB{\|e} to \PB{\\{todo\_list}}\X${}\E{}$\6
${}\{{}$\1\6
\&{int} \\{flag};\6
\&{long} \\{qid};\7
\&{if} ${}(\\{is\_critical}(\|e)\V(\\{is\_paired\_up}(\|e)\W(\R\\{is\_deadend}(%
\|e)\V(\\{options}\AND\T{3})\E\T{0}))){}$\5
${}\{{}$\1\6
${}\\{qid}\K\\{olist\_find\_add}(\\{edges},\39\\{edge\_id}(\|e),\39\NULL,\39{%
\AND}\\{flag});{}$\6
\&{if} ${}(\R\\{flag}){}$\1\5
\\{abort\_message}(\.{"count\ error\ 2"});\2\6
${}\|q\K{}$(\&{struct} \&{grad12\_struct} ${}{*}){}$ \\{olist\_entry}${}(%
\\{edges},\39\\{qid});{}$\6
\&{if} ${}((\|q\MG\\{flags}\AND\T{32})\E\T{0}){}$\5
${}\{{}$\1\6
${}\\{list\_read\_insert}(\\{todo\_list},\39{\AND}\\{qid});{}$\6
${}\|q\MG\\{flags}\MRL{{\OR}{\K}}\T{32};{}$\6
\4${}\}{}$\2\6
\&{else}\1\5
${}\|q\MG\\{flags}\MRL{\AND{\K}}\T{\^ffffffef};{}$\2\6
\4${}\}{}$\2\6
\4${}\}{}$\2\par
\U69.\fi

\M{71}\B\X71:count incoming faces to \PB{\\{ep}}\X${}\E{}$\6
${}\{{}$\1\6
\&{edge} ${}{*}\|e;{}$\6
\&{int} \|i;\6
\&{long} \\{ct}${}\K\T{0};{}$\6
\&{long} \\{orient};\6
\&{triangle} ${}{*}\|t;{}$\7
${}\|p\MG\\{flags}\MRL{\AND{\K}}\T{\^ffffffef};{}$\6
${}\|p\MG\\{flags}\MRL{{\OR}{\K}}\T{8};{}$\6
\\{list\_read\_delete}(\\{todo\_list});\6
${}\\{kk}\K\|p\MG\\{flags}\AND\T{3};{}$\6
\&{if} ${}(\\{kk}\E\T{3}){}$\1\5
${}\\{id}\K\|p\MG\\{links}[\T{0}];{}$\2\6
\&{else}\1\5
${}\\{id}\K\|p\MG\\{links}[\\{kk}];{}$\2\6
\&{while} ${}(\\{id}\G\T{0}){}$\5
${}\{{}$\1\6
${}\|q\K{}$(\&{struct} \&{grad12\_struct} ${}{*}){}$ \\{olist\_entry}${}(%
\\{edges},\39\\{id});{}$\6
${}\|e\K\\{id2edge}(\\{olist\_get\_key}(\\{edges},\39\\{id}));{}$\6
${}\|t\K\\{r12}(\|e);{}$\6
${}\|i\K\\{edge\_in\_triangle}(\\{ep},\39\|t);{}$\6
${}\\{id}\K\|q\MG\\{links}[\|i];{}$\6
${}\\{ct}\MRL{+{\K}}\\{edge\_orient}(\|t,\39\|i)*\|q\MG\\{count};{}$\6
\4${}\}{}$\2\6
\&{if} ${}(\\{id}\E{-}\T{2}){}$\5
${}\{{}$\1\6
${}\\{ct}\MRL{+{\K}}\\{edge\_orient}(\\{sigma},\39\\{edge\_in\_triangle}(%
\\{ep},\39\\{sigma}));{}$\6
\4${}\}{}$\2\6
\&{if} (\\{is\_critical}(\\{ep}))\1\5
${}\|p\MG\\{count}\K\\{ct};{}$\2\6
\&{else}\1\5
${}\|p\MG\\{count}\K{-}\\{ct}*\\{edge\_orient}(\\{r12}(\\{ep}),\39\|p\MG%
\\{flags}\AND\T{3});{}$\2\6
\4${}\}{}$\2\par
\U68.\fi

\M{72}Find all gradient paths ending at tau.
Only now the key is a triangle id, rather than an edge id.
The list \PB{\\{crits}} is a list of indices of items in \PB{\\{triangles}}
which are critical triangles.
\Y\B\4\D$\\{is\_xdeadend}(\|s)$ \5
$((\|s)\MG\\{type}\AND\T{\^1000}{}$)\par
\B\4\D$\\{make\_xdeadend}(\|s)$ \5
$((\|s)\MG\\{type}\MRL{{\OR}{\K}}\T{\^1000}{}$)\par
\Y\B\4\X51:Subroutines finding gradient paths\X${}\mathrel+\E{}$\6
\&{long} \\{find\_all\_backward\_grad12\_paths}(\&{edge} ${}{*}\\{tau},\39{}$%
\&{olist} ${}{*}\\{triangles},\39{}$\&{list} ${}{*}\\{crits},\39{}$\&{int} %
\\{options})\1\1\2\2\6
${}\{{}$\1\6
\&{int} \\{kk}${}\K{-}\T{1};{}$\6
\&{triangle} ${}{*}\|f;{}$\6
\&{edge} ${}{*}\\{ep};{}$\6
\&{long} \\{todo}${}\K{-}\T{1};{}$\6
\&{long} ${}\this;{}$\6
\&{struct} \&{grad12\_struct} ${}{*}\|p;{}$\6
\&{long} \\{start}${}\K{-}\T{1};{}$\6
\&{list} ${}{*}\\{todo\_list};{}$\7
\\{olist\_clear}(\\{triangles});\6
\&{if} ${}(\\{crits}\I\NULL){}$\1\5
\\{list\_clear}(\\{crits});\2\6
\&{if} ${}((\\{options}\AND\T{3})\E\T{2}){}$\1\5
${}\\{list\_initialize}({\AND}\\{todo\_list},\39\&{sizeof}(\&{long}));{}$\2\6
\&{do}\5
${}\{{}$\1\6
${}\this\K\\{todo};{}$\6
\&{if} ${}(\this\G\T{0}){}$\5
${}\{{}$\1\6
${}\|p\K{}$(\&{struct} \&{grad12\_struct} ${}{*}){}$ \\{olist\_entry}${}(%
\\{triangles},\39\this);{}$\6
${}\|f\K\\{id2triangle}(\\{olist\_get\_key}(\\{triangles},\39\this));{}$\6
${}\\{ep}\K\\{r21}(\|f);{}$\6
${}\\{kk}\K\|p\MG\\{flags}\AND\T{3};{}$\6
${}\\{todo}\K\|p\MG\\{links}[\\{kk}];{}$\6
${}\|p\MG\\{links}[\\{kk}]\K{-}\T{1};{}$\6
\4${}\}{}$\2\6
\&{else}\1\5
${}\\{ep}\K\\{tau};{}$\2\6
\X73:find-add cofaces of \PB{\\{ep}} to \PB{\\{triangles}} if needed\X\6
\4${}\}{}$\2\5
\&{while} ${}(\\{todo}\G\T{0});{}$\6
\&{if} ${}((\\{options}\AND\T{3})\E\T{2}){}$\1\5
\X75:prune \PB{\\{triangles}}\X\2\6
\&{return} \\{start};\6
\4${}\}{}$\2\par
\fi

\M{73}\B\X73:find-add cofaces of \PB{\\{ep}} to \PB{\\{triangles}} if needed%
\X${}\E{}$\6
${}\{{}$\1\6
\&{tetrahedron} ${}{*}\|t;{}$\6
\&{int} \\{link\_count}${}\K\T{0};{}$\7
${}\|f\K\\{ep}\MG\\{links}[\T{2}];{}$\6
${}\|t\K\\{coface}(\|f,\39\T{0});{}$\6
\&{do}\5
${}\{{}$\1\6
\&{if} ${}(\\{is\_in\_K}(\|f)\W(\\{is\_critical}(\|f)\V((\R\\{is\_xdeadend}(%
\|f)\V(\\{options}\AND\T{3})\E\T{0})\W\\{is\_paired\_down}(\|f)\W\\{ep}\I%
\\{r21}(\|f)))){}$\5
${}\{{}$\1\6
${}\\{link\_count}\PP;{}$\6
\X74:find-add \PB{\|f} to \PB{\\{triangles}}\X\6
\4${}\}{}$\2\6
${}\|t\K\\{other\_coface}(\|f,\39\|t);{}$\6
${}\|f\K\\{other\_face}(\\{ep},\39\|f,\39\|t);{}$\6
\4${}\}{}$\2\5
\&{while} ${}(\|f\I\\{ep}\MG\\{links}[\T{2}]);{}$\6
\&{if} ${}(\\{link\_count}\E\T{0}\W(\\{options}\AND\T{3})\W\this\G\T{0}){}$\5
${}\{{}$\1\6
\\{make\_xdeadend}(\\{ep});\6
\\{make\_xdeadend}(\\{r12}(\\{ep}));\6
\4${}\}{}$\2\6
\4${}\}{}$\2\par
\U72.\fi

\M{74}\B\X74:find-add \PB{\|f} to \PB{\\{triangles}}\X${}\E{}$\6
${}\{{}$\1\6
\&{struct} \&{grad12\_struct} \|r${},{}$ ${}{*}\|q;{}$\6
\&{long} \\{id};\6
\&{int} \\{flag};\6
\&{int} \|k;\7
${}\\{id}\K\\{olist\_find\_add}(\\{triangles},\39\\{triangle\_id}(\|f),\39{%
\AND}\|r,\39{\AND}\\{flag});{}$\6
${}\|q\K{}$(\&{struct} \&{grad12\_struct} ${}{*}){}$ \\{olist\_entry}${}(%
\\{triangles},\39\\{id});{}$\6
${}\|k\K\\{edge\_in\_triangle}(\\{ep},\39\|f);{}$\6
\&{if} ${}(\this\G\T{0}){}$\1\5
${}\|p\K{}$(\&{struct} \&{grad12\_struct} ${}{*}){}$ \\{olist\_entry}${}(%
\\{triangles},\39\this);{}$\2\6
\&{if} (\\{flag})\SHC{ already on list }\6
${}\{{}$\1\6
\&{if} ${}(\|q\MG\\{links}[\|k]\G\T{0}){}$\1\5
\\{abort\_message}(\.{"backgrad\ error\ 1"});\2\6
\&{if} ${}(\this<\T{0}){}$\1\5
\\{abort\_message}(\.{"backgrad\ error\ 2"});\2\6
${}\|q\MG\\{links}[\|k]\K\|p\MG\\{links}[\\{kk}];{}$\6
${}\|p\MG\\{links}[\\{kk}]\K\\{id};{}$\6
\4${}\}{}$\2\6
\&{else}\SHC{ newly added to list }\6
${}\{{}$\1\6
${}\|q\MG\\{links}[\T{0}]\K\|q\MG\\{links}[\T{1}]\K\|q\MG\\{links}[\T{2}]\K{-}%
\T{2};{}$\6
\&{if} ${}(\this\G\T{0}){}$\5
${}\{{}$\1\6
${}\|q\MG\\{links}[\|k]\K\|p\MG\\{links}[\\{kk}];{}$\6
${}\|p\MG\\{links}[\\{kk}]\K\\{id};{}$\6
\4${}\}{}$\2\6
\&{else}\5
${}\{{}$\1\6
${}\|q\MG\\{links}[\|k]\K\\{start};{}$\6
${}\\{start}\K\\{id};{}$\6
\4${}\}{}$\2\6
\&{if} (\\{is\_critical}(\|f))\5
${}\{{}$\1\6
${}\|q\MG\\{flags}\K\T{3};{}$\6
\&{if} ${}(\\{crits}\I\NULL){}$\1\5
${}\\{list\_push}(\\{crits},\39{\AND}\\{id});{}$\2\6
\&{if} ${}((\\{options}\AND\T{3})\E\T{2}){}$\1\5
${}\\{list\_push}(\\{todo\_list},\39{\AND}\\{id});{}$\2\6
\4${}\}{}$\2\6
\&{else}\5
${}\{{}$\1\6
${}\|q\MG\\{flags}\K\\{edge\_in\_triangle}(\\{r21}(\|f),\39\|f);{}$\6
${}\|q\MG\\{links}[\|q\MG\\{flags}]\K\\{todo};{}$\6
${}\\{todo}\K\\{id};{}$\6
\4${}\}{}$\2\6
\4${}\}{}$\2\6
\4${}\}{}$\2\par
\U73.\fi

\M{75}\B\X75:prune \PB{\\{triangles}}\X${}\E{}$\6
${}\{{}$\1\6
\&{long} \\{id};\6
\&{int} \|k;\6
\&{edge} ${}{*}\|e;{}$\6
\&{struct} \&{grad12\_struct} \|r${},{}$ ${}{*}\|q;{}$\6
\&{triangle} ${}{*}\|f;{}$\6
\&{int} \\{flag};\7
\&{while} ${}(\R\\{list\_is\_empty}(\\{todo\_list})){}$\5
${}\{{}$\1\6
${}\\{list\_pop}(\\{todo\_list},\39{\AND}\\{id});{}$\6
${}\|p\K{}$(\&{struct} \&{grad12\_struct} ${}{*}){}$ \\{olist\_entry}${}(%
\\{triangles},\39\\{id});{}$\6
\&{if} ${}(\|p\MG\\{flags}\AND\T{4}){}$\1\5
\&{continue};\2\6
${}\|p\MG\\{flags}\MRL{{\OR}{\K}}\T{4};{}$\6
${}\\{kk}\K\|p\MG\\{flags}\AND\T{3};{}$\6
${}\|f\K\\{id2triangle}(\\{olist\_get\_key}(\\{triangles},\39\\{id}));{}$\6
\&{for} ${}(\|k\K\T{0};{}$ ${}\|k<\T{3};{}$ ${}\|k\PP){}$\5
${}\{{}$\1\6
\&{if} ${}(\|k\E\\{kk}\V\|p\MG\\{links}[\|k]<{-}\T{1}){}$\1\5
\&{continue};\2\6
${}\|e\K\\{get\_edge}(\|f,\39\|k);{}$\6
\&{if} ${}(\\{is\_paired\_up}(\|e)\W\R\\{is\_deadend}(\|e)){}$\5
${}\{{}$\1\6
\&{if} (\\{is\_xdeadend}(\|e))\1\5
\\{abort\_message}(\.{"back\ grad\ error\ 3"});\2\6
${}\\{id}\K\\{olist\_find\_add}(\\{triangles},\39\\{triangle\_id}(\\{r12}(%
\|e)),\39{\AND}\|r,\39{\AND}\\{flag});{}$\6
${}\|q\K{}$(\&{struct} \&{grad12\_struct} ${}{*}){}$ \\{olist\_entry}${}(%
\\{triangles},\39\\{id});{}$\6
\&{if} ${}(\\{flag}\E\T{0}){}$\5
${}\{{}$\1\6
${}\|q\MG\\{flags}\K\\{edge\_in\_triangle}(\|e,\39\\{r12}(\|e));{}$\6
\\{printf}(\.{"back\ grad\ puzzle\\n"});\6
\4${}\}{}$\2\6
\&{if} ${}((\|q\MG\\{flags}\AND\T{4})\E\T{0}){}$\1\5
${}\\{list\_push}(\\{todo\_list},\39{\AND}\\{id});{}$\2\6
\4${}\}{}$\2\6
\4${}\}{}$\2\6
\4${}\}{}$\2\6
${}\\{list\_abandon}({\AND}\\{todo\_list});{}$\6
\&{for} ${}(\\{id}\K\T{0};{}$ ${}\\{id}<\\{olist\_count}(\\{triangles});{}$ ${}%
\\{id}\PP){}$\5
${}\{{}$\1\6
${}\|p\K{}$(\&{struct} \&{grad12\_struct} ${}{*}){}$ \\{olist\_entry}${}(%
\\{triangles},\39\\{id});{}$\6
\&{if} ${}(\|p\MG\\{flags}\AND\T{4}){}$\1\5
\&{continue};\2\6
${}\|f\K\\{id2triangle}(\\{olist\_get\_key}(\\{triangles},\39\\{id}));{}$\6
\\{make\_deadend}(\|f);\6
\\{make\_deadend}(\\{r21}(\|f));\6
\4${}\}{}$\2\6
\4${}\}{}$\2\par
\U72.\fi

\N{1}{76}Persistent critical simplices.  This is experimental code, trying to
identify
critical simplices which might generate persistent homology.
So far in random examples all but a few critical simplices end up being
persistent.

\Y\B\4\X76:find persistent critical simplices\X${}\E{}$\6
\X77:make all critical vertices persistent\X\6
\X78:find persistent critical edges\X\6
\X81:find persistent critical triangles\X\6
\X79:find persistent critical tetrahedra\X\par
\fi

\M{77}\B\X77:make all critical vertices persistent\X${}\E{}$\6
${}\{{}$\1\6
\&{vertex} ${}{*}\|v;{}$\7
\\{list\_read\_init}(\\{crit}[\T{0}]);\6
\&{while} ${}((\|v\K{}$(\&{vertex} ${}{*}){}$ \\{plist\_read}(\\{crit}[%
\T{0}]))${}\I\NULL){}$\5
${}\{{}$\1\6
\&{if} ${}(\R\\{is\_critical}(\|v)){}$\1\5
\\{list\_read\_delete}(\\{crit}[\T{0}]);\2\6
\&{else}\1\5
\\{make\_persistent}(\|v);\2\6
\4${}\}{}$\2\6
\4${}\}{}$\2\par
\U76.\fi

\M{78}This is called after canceling is done, so if \PB{\|v} is not \PB{$%
\NULL$}
then we know that the two gradient paths from \PB{\|e} end at the same
vertex \PB{\|v} and \PB{\\{value}(\|v)} $\ge$ \PB{$\\{value}(\|e)-\|p$}.
\Y\B\4\X78:find persistent critical edges\X${}\E{}$\6
${}\{{}$\1\6
\&{edge} ${}{*}\|e;{}$\6
\&{vertex} ${}{*}\|v;{}$\7
\\{list\_read\_init}(\\{crit}[\T{1}]);\6
\&{while} ${}((\|e\K{}$(\&{edge} ${}{*}){}$ \\{plist\_read}(\\{crit}[%
\T{1}]))${}\I\NULL){}$\5
${}\{{}$\1\6
\&{if} ${}(\R\\{is\_critical}(\|e)){}$\1\5
\\{list\_read\_delete}(\\{crit}[\T{1}]);\2\6
\&{else}\5
${}\{{}$\1\6
${}\|v\K\\{FindGrad01}(\\{get\_vertex}(\|e,\39\T{0}),\39\\{value}(\|e)-\|p);{}$%
\6
\&{if} ${}(\|v\E\NULL){}$\1\5
\\{make\_persistent}(\|e);\2\6
\4${}\}{}$\2\6
\4${}\}{}$\2\6
\4${}\}{}$\2\par
\U76.\fi

\M{79}\B\X79:find persistent critical tetrahedra\X${}\E{}$\6
\X80:make all critical tetrahedra persistent\X\6
${}\{{}$\1\6
\&{triangle} ${}{*}\|t;{}$\6
\&{tetrahedron} ${}{*}\\{te};{}$\7
\\{list\_read\_init}(\\{crit}[\T{2}]);\6
\&{while} ${}((\|t\K{}$(\&{triangle} ${}{*}){}$ \\{plist\_read}(\\{crit}[%
\T{2}]))${}\I\NULL){}$\5
${}\{{}$\1\6
\&{if} (\\{is\_persistent}(\|t))\5
${}\{{}$\1\6
${}\\{te}\K\\{FindGrad23}(\\{coface}(\|t,\39\T{0}),\39\\{value}(\|t)+\|p);{}$\6
\&{if} ${}(\\{te}\I\NULL){}$\1\5
\\{unmake\_persistent}(\\{te});\2\6
\4${}\}{}$\2\6
\4${}\}{}$\2\6
\4${}\}{}$\2\par
\U76.\fi

\M{80}\B\X80:make all critical tetrahedra persistent\X${}\E{}$\6
${}\{{}$\1\6
\&{tetrahedron} ${}{*}\|t;{}$\7
\\{list\_read\_init}(\\{crit}[\T{3}]);\6
\&{while} ${}((\|t\K{}$(\&{tetrahedron} ${}{*}){}$ \\{plist\_read}(\\{crit}[%
\T{3}]))${}\I\NULL){}$\5
${}\{{}$\1\6
\&{if} ${}(\R\\{is\_critical}(\|t)){}$\1\5
\\{list\_read\_delete}(\\{crit}[\T{3}]);\2\6
\&{else}\1\5
\\{make\_persistent}(\|t);\2\6
\4${}\}{}$\2\6
\4${}\}{}$\2\par
\U79.\fi

\M{81}\B\X81:find persistent critical triangles\X${}\E{}$\6
${}\{{}$\1\6
\&{triangle} ${}{*}\|t;{}$\6
\&{void} ${}{*}\|q;{}$\7
\\{list\_read\_init}(\\{crit}[\T{2}]);\6
\&{while} ${}((\|t\K{}$(\&{triangle} ${}{*}){}$ \\{plist\_read}(\\{crit}[%
\T{2}]))${}\I\NULL){}$\5
${}\{{}$\1\6
\&{if} ${}(\R\\{is\_critical}(\|t)){}$\1\5
\\{list\_read\_delete}(\\{crit}[\T{2}]);\2\6
\&{else}\5
${}\{{}$\1\6
${}\|q\K\\{FindGradPaths12}(\|t,\39\|p,\39\NULL,\39\T{1});{}$\6
\&{if} ${}(\|q\E\NULL){}$\1\5
\\{make\_persistent}(\|t);\2\6
\4${}\}{}$\2\6
\4${}\}{}$\2\6
\4${}\}{}$\2\par
\U76.\fi

\M{82}\B\X82:find a persistent critical edge \PB{\|e} in \PB{\\{crits}}\X${}%
\E{}$\6
${}\{{}$\1\6
\&{edge} ${}{*}\\{ee};{}$\7
${}\|e\K\NULL;{}$\6
\&{while} ${}(\R\\{list\_is\_empty}(\\{crits})){}$\5
${}\{{}$\1\6
${}\\{list\_pop}(\\{crits},\39{\AND}\|m);{}$\6
${}\\{ee}\K{}$(\&{edge} ${}{*}){}$ \\{olist\_get\_key}${}(\\{graph},\39\|m);{}$%
\6
\&{if} (\\{is\_persistent}(\\{ee}))\5
${}\{{}$\1\6
${}\|e\K\\{ee};{}$\6
\&{break};\6
\4${}\}{}$\2\6
\4${}\}{}$\2\6
\4${}\}{}$\2\par
\U53.\fi

\N{1}{83}Unordered Lists.
Unordered lists work as LIFO stacks.
We can push to and pop from a \PB{\&{list}}.
We can find the $n$-th entry on a \PB{\&{list}}.
We can read the entries of a \PB{\&{list}} one by one, deleting those we no
longer want.

\Y\B\F\\{list} \5
\\{int}\par
\Y\B\4\X61:\.{MorseExtract.h }\X${}\mathrel+\E{}$\6
\&{typedef} \&{struct} ${}\{{}$\1\6
\&{long} ${}{*}\\{body};{}$\6
\&{unsigned} \&{int} \\{size};\SHC{ size of each entry, not including padding }%
\6
\&{unsigned} \&{int} \\{padded\_size};\SHC{ size of each entry, in long words }%
\6
\&{unsigned} \&{long} \\{body\_length};\SHC{ capacity of body }\6
\&{unsigned} \&{long} \\{length};\SHC{ number of entries on list }\6
\&{unsigned} \&{long} \\{read\_index};\6
\&{unsigned} \&{long} \\{read\_delete\_index};\2\6
${}\}{}$ \&{list};\6
\8\#\&{define} \\{list\_count}(\|l) \5${}((\|l)\MG\\{length}){}$\6
\8\#\&{define} \\{list\_is\_empty}(\|l) \5${}((\|l)\MG\\{length}\E\T{0}){}$\6
\8\#\&{define} \\{list\_clear}(\|l) \5${}((\|l)\MG\\{length}\K\T{0}){}$\6
\8\#\&{define} ${}\\{list\_entry}(\|l,\39\|n) \5((\|l)\MG\\{body}+(\|n)*((\|l)%
\MG\\{padded\_size})){}$\par
\fi

\M{84}Initialize a list, setting up storage
\Y\B\4\X84:List functions\X${}\E{}$\6
\&{void} \\{list\_initialize}(\&{list} ${}{*}{*}\|l,\39{}$\&{unsigned} \&{int} %
\\{sz})\1\1\2\2\6
${}\{{}$\1\6
${}{*}\|l\K{}$(\&{list} ${}{*}){}$ \\{malloc}(\&{sizeof}(\&{list}));\6
\&{if} ${}(({*}\|l)\E\NULL){}$\1\5
\\{abort\_message}(\.{"Out\ of\ memory"});\2\6
${}({*}\|l)\MG\\{size}\K\\{sz};{}$\6
${}({*}\|l)\MG\\{padded\_size}\K(\\{sz}+\&{sizeof}(\&{long})-\T{1})/\&{sizeof}(%
\&{long});{}$\6
${}({*}\|l)\MG\\{length}\K\T{0};{}$\6
${}({*}\|l)\MG\\{body}\K\NULL;{}$\6
${}({*}\|l)\MG\\{body\_length}\K\T{0};{}$\6
\4${}\}{}$\2\par
\As85, 86, 87, 89, 90, 93, 94, 95, 96, 97\ETs98.
\U1.\fi

\M{85}Abandon a list, freeing storage used.
\Y\B\4\X84:List functions\X${}\mathrel+\E{}$\6
\&{void} \\{list\_abandon}(\&{list} ${}{*}{*}\|l){}$\1\1\2\2\6
${}\{{}$\1\6
\&{if} ${}(({*}\|l)\MG\\{body\_length}>\T{0}){}$\1\5
${}\\{free}(({*}\|l)\MG\\{body});{}$\2\6
${}\\{free}({*}\|l);{}$\6
${}{*}\|l\K\NULL;{}$\6
\4${}\}{}$\2\par
\fi

\M{86}\PB{\\{list\_push}} pushes a new entry pointed to by \PB{\|q} to the top
of the list.
The variant \PB{\\{plist\_push}} pushes the pointer \PB{\|q} directly to the
list
(as opposed to the contents pointed to by \PB{\|q}).

\Y\B\4\X84:List functions\X${}\mathrel+\E{}$\6
\&{void} ${}{*}{}$\\{list\_push}(\&{list} ${}{*}\|l,\39{}$\&{void} ${}{*}%
\|q){}$\1\1\2\2\6
${}\{{}$\1\6
\&{long} ${}{*}\|p;{}$\7
\&{if} ${}(\|l\MG\\{body\_length}\Z\|l\MG\\{length}){}$\5
${}\{{}$\1\6
${}\|l\MG\\{body\_length}\K\|l\MG\\{length}+\T{1000};{}$\6
${}\|l\MG\\{body}\K{}$(\&{long} ${}{*}){}$ \\{realloc}${}(\|l\MG\\{body},\39\|l%
\MG\\{body\_length}*\|l\MG\\{padded\_size}*\&{sizeof}(\&{long}));{}$\6
\&{if} ${}(\|l\MG\\{body}\E\NULL){}$\1\5
\\{abort\_message}(\.{"out\ of\ memory"});\2\6
\4${}\}{}$\2\6
${}\|p\K\\{list\_entry}(\|l,\39\|l\MG\\{length});{}$\6
${}\\{memcpy}(\|p,\39\|q,\39\|l\MG\\{size});{}$\6
${}\|l\MG\\{length}\PP;{}$\6
\&{return} \|p;\6
\4${}\}{}$\2\7
\&{void} \\{plist\_push}(\&{list} ${}{*}\|l,\39{}$\&{void} ${}{*}\|q){}$\1\1\2%
\2\6
${}\{{}$\1\6
\&{void} ${}{*}\|p\K\|q;{}$\7
${}\\{list\_push}(\|l,\39{\AND}\|p);{}$\6
\4${}\}{}$\2\par
\fi

\M{87}\PB{\\{list\_pop}} pops the top entry into the region pointed to by \PB{%
\|q},
and deletes it from the list.
It copies the top entry to \PB{\|q}.
The variant \PB{\\{plist\_pop}} returns the entry from a pointer list directly.

\Y\B\4\X84:List functions\X${}\mathrel+\E{}$\6
\&{void} \\{list\_pop}(\&{list} ${}{*}\|l,\39{}$\&{void} ${}{*}\|q){}$\1\1\2\2\6
${}\{{}$\1\6
\&{long} ${}{*}\|p;{}$\7
\&{if} ${}(\|l\MG\\{length}\E\T{0}){}$\1\5
\\{abort\_message}(\.{"pop\ from\ empty\ list}\)\.{"});\2\6
${}\|l\MG\\{length}\MM;{}$\6
${}\|p\K\\{list\_entry}(\|l,\39\|l\MG\\{length});{}$\6
${}\\{memcpy}(\|q,\39\|p,\39\|l\MG\\{size});{}$\6
\4${}\}{}$\2\7
\&{void} ${}{*}{}$\\{plist\_pop}(\&{list} ${}{*}\|l){}$\1\1\2\2\6
${}\{{}$\1\6
\&{void} ${}{*}\|p;{}$\7
${}\\{list\_pop}(\|l,\39{\AND}\|p);{}$\6
\&{return} \|p;\6
\4${}\}{}$\2\par
\fi

\M{88}Routine to read the entries of a list one by one,
and deleting those you don't wish to retain on the list.
To use it, first call \PB{\\{list\_read\_init}}.
Then repeated calls to \PB{\\{list\_read}} will return the entries on the list,
until a \PB{$\NULL$} is returned signifying the end.
If you wish to delete the entry you last read, just call \PB{\\{list\_read%
\_delete}}.
If your list is a list of pointers, then
the companion pointer list routine \PB{\\{plist\_read}} returns the pointer,
rather than its address.
Since the end of the list is signaled by returning a \PB{$\NULL$} pointer
it will only work well if the list of pointers
contains no \PB{$\NULL$} pointers, otherwise you might stop too early.
So in this case you would need some alternate method to
recognize the end of the list.

{\bf Warnings:} if you use \PB{\\{list\_read\_delete}} then you must read
through
to the end of the list.
\Y\B\4\X61:\.{MorseExtract.h }\X${}\mathrel+\E{}$\6
\8\#\&{define} \\{list\_read\_init}(\|l) \5${}((\|l)\MG\\{read\_index}\K(\|l)%
\MG\\{read\_delete\_index}\K\T{0}){}$\6
\8\#\&{define} \\{list\_read\_delete}(\|l) \5${}((\|l)\MG\\{read\_delete%
\_index}\MM){}$\par
\fi

\M{89}\B\X84:List functions\X${}\mathrel+\E{}$\6
\&{void} ${}{*}{}$\\{list\_read}(\&{list} ${}{*}\|l){}$\1\1\2\2\6
${}\{{}$\1\6
\&{void} ${}{*}\|p,{}$ ${}{*}\\{pp};{}$\7
\&{if} ${}(\|l\MG\\{read\_index}\G\|l\MG\\{length}){}$\5
${}\{{}$\SHC{ we are at the end of the list }\1\6
${}\|l\MG\\{length}\K\|l\MG\\{read\_index}\K\|l\MG\\{read\_delete\_index};{}$\6
\&{return} ${}(\NULL);{}$\6
\4${}\}{}$\2\6
${}\\{pp}\K\\{list\_entry}(\|l,\39\|l\MG\\{read\_delete\_index});{}$\6
\&{if} ${}(\|l\MG\\{read\_index}\I\|l\MG\\{read\_delete\_index}){}$\5
${}\{{}$\1\6
${}\|p\K\\{list\_entry}(\|l,\39\|l\MG\\{read\_index});{}$\6
${}\\{memcpy}(\\{pp},\39\|p,\39\|l\MG\\{size});{}$\6
\4${}\}{}$\2\6
${}\|l\MG\\{read\_delete\_index}\PP;{}$\6
${}\|l\MG\\{read\_index}\PP;{}$\6
\&{return} \\{pp};\6
\4${}\}{}$\2\7
\&{void} ${}{*}{}$\\{plist\_read}(\&{list} ${}{*}\|l){}$\1\1\2\2\6
${}\{{}$\1\6
\&{void} ${}{*}{*}\|r;{}$\7
${}\|r\K\\{list\_read}(\|l);{}$\6
\&{if} ${}(\|r\I\NULL){}$\1\5
\&{return} ${}{*}\|r;{}$\2\6
\&{else}\1\5
\&{return} ${}\NULL;{}$\2\6
\4${}\}{}$\2\par
\fi

\M{90}The following \PB{\\{list\_read\_insert}} will insert an item in a list
you are reading, placing it just before the most recently read item
if there is room, or if not, placing it at the end.
\Y\B\4\X84:List functions\X${}\mathrel+\E{}$\6
\&{void} ${}{*}{}$\\{list\_read\_insert}(\&{list} ${}{*}\|l,\39{}$\&{void}
${}{*}\|p){}$\1\1\2\2\6
${}\{{}$\1\6
\&{if} ${}(\|l\MG\\{read\_index}\E\|l\MG\\{read\_delete\_index}){}$\1\5
${}\\{list\_push}(\|l,\39\|p);{}$\2\6
\&{else}\5
${}\{{}$\1\6
${}\\{memcpy}(\\{list\_entry}(\|l,\39\|l\MG\\{read\_delete\_index}),\39\|p,\39%
\|l\MG\\{size});{}$\6
${}\|l\MG\\{read\_delete\_index}\PP;{}$\6
\4${}\}{}$\2\6
\4${}\}{}$\2\par
\fi

\N{1}{91}Ordered Lists.
Ordered lists are implemented naively and could no doubt be made more
efficient.
Items on an \PB{\&{olist}} are ordered by an integer key.

Portability issue: these are sometimes used with a simplex pointer
as the key, so that requires \PB{\&{sizeof}(\&{long}) $\K$ \&{sizeof} ( %
\\{simplex} $*$ )}.
When this is done, of course we don't really care about the resulting order,
we are just using ordered lists to find entries quickly.
One could also implement such lists by adding auxiliary fields to
each simplex, but then memory usage is increased.
\Y\B\F\\{olist} \5
\\{int}\par
\fi

\M{92}\B\X61:\.{MorseExtract.h }\X${}\mathrel+\E{}$\6
\&{struct} \&{olist\_key} ${}\{{}$\1\6
\&{long} \\{high};\6
\&{long} \\{low};\6
\&{long} \\{eq};\6
\&{long} \|k;\SHC{ the list is ordered by this key \PB{\|k} }\2\6
${}\};{}$\6
\&{typedef} \&{struct} ${}\{{}$\1\6
\&{list} ${}{*}\\{keys};{}$\6
\&{list} ${}{*}\\{entries};{}$\6
\&{long} \\{top};\6
\&{long} \\{free};\6
\&{int} \\{sz};\2\6
${}\}{}$ \&{olist};\6
\8\#\&{define} \\{olist\_is\_empty}(\|l) \5${}((\|l)\MG\\{top}<\T{0}){}$\6
\8\#\&{define} ${}\\{olist\_entry}(\|l,\39\|n)\\{list\_entry} \5((\|l)\MG%
\\{entries},\39\|n){}$\6
\8\#\&{define} ${}\\{olist\_get\_key}(\|l,\39\|n) \5{}$(((\&{struct} \&{olist%
\_key} ${}{*}){}$ \\{list\_entry}${}((\|l)\MG\\{keys},\39\|n))\MG\|k){}$\6
\8\#\&{define} \\{olist\_count}(\|l)\\{list\_count} \5${}((\|l)\MG%
\\{entries}){}$\par
\fi

\M{93}\B\X84:List functions\X${}\mathrel+\E{}$\6
\&{void} \\{olist\_initialize}(\&{olist} ${}{*}{*}\|l,\39{}$\&{int} \\{sz})\1\1%
\2\2\6
${}\{{}$\1\6
${}{*}\|l\K{}$(\&{olist} ${}{*}){}$ \\{malloc}(\&{sizeof}(\&{olist}));\6
\&{if} ${}(({*}\|l)\E\NULL){}$\1\5
\\{abort\_message}(\.{"Out\ of\ memory"});\2\6
${}\\{list\_initialize}({\AND}(({*}\|l)\MG\\{keys}),\39{}$\&{sizeof}(\&{struct}
\&{olist\_key}));\6
${}\\{list\_initialize}({\AND}(({*}\|l)\MG\\{entries}),\39\\{sz});{}$\6
${}({*}\|l)\MG\\{top}\K{-}\T{1};{}$\6
${}({*}\|l)\MG\\{free}\K{-}\T{1};{}$\6
${}({*}\|l)\MG\\{sz}\K\\{sz};{}$\6
\4${}\}{}$\2\par
\fi

\M{94}\B\X84:List functions\X${}\mathrel+\E{}$\6
\&{void} \\{olist\_abandon}(\&{olist} ${}{*}{*}\|l){}$\1\1\2\2\6
${}\{{}$\1\6
${}\\{list\_abandon}({\AND}(({*}\|l)\MG\\{keys}));{}$\6
${}\\{list\_abandon}({\AND}(({*}\|l)\MG\\{entries}));{}$\6
${}\\{free}({*}\|l);{}$\6
${}{*}\|l\K\NULL;{}$\6
\4${}\}{}$\2\par
\fi

\M{95}\B\X84:List functions\X${}\mathrel+\E{}$\6
\&{void} \\{olist\_clear}(\&{olist} ${}{*}\|l){}$\1\1\2\2\6
${}\{{}$\1\6
${}\\{list\_clear}(\|l\MG\\{keys});{}$\6
${}\\{list\_clear}(\|l\MG\\{entries});{}$\6
${}\|l\MG\\{top}\K{-}\T{1};{}$\6
${}\|l\MG\\{free}\K{-}\T{1};{}$\6
\4${}\}{}$\2\par
\fi

\M{96}Pop the smallest entry from the list, return its key, and put the list
entry in \PB{\|p}.
\Y\B\4\X84:List functions\X${}\mathrel+\E{}$\6
\&{long} \\{olist\_min}(\&{olist} ${}{*}\|l,\39{}$\&{void} ${}{*}\|p){}$\1\1\2%
\2\6
${}\{{}$\1\6
\&{struct} \&{olist\_key} ${}{*}\|q,{}$ ${}{*}\|r;{}$\6
\&{long} \\{min\_index};\7
${}\\{min\_index}\K\|l\MG\\{top};{}$\6
\&{if} ${}(\\{min\_index}<\T{0}){}$\1\5
\\{abort\_message}(\.{"min\ of\ empty\ list"});\2\6
${}\|q\K{}$(\&{struct} \&{olist\_key} ${}{*}){}$ \\{list\_entry}${}(\|l\MG%
\\{keys},\39\\{min\_index});{}$\6
\&{if} ${}(\|q\MG\\{low}\G\T{0}){}$\5
${}\{{}$\1\6
\&{while} ${}(\|q\MG\\{low}\G\T{0}){}$\5
${}\{{}$\1\6
${}\|r\K\|q;{}$\6
${}\\{min\_index}\K\|q\MG\\{low};{}$\6
${}\|q\K{}$(\&{struct} \&{olist\_key} ${}{*}){}$ \\{list\_entry}${}(\|l\MG%
\\{keys},\39\\{min\_index});{}$\6
\4${}\}{}$\2\6
\&{if} ${}(\|q\MG\\{eq}\G\T{0}){}$\5
${}\{{}$\1\6
${}\|r\K\|q;{}$\6
${}\\{min\_index}\K\|q\MG\\{eq};{}$\6
${}\|q\K{}$(\&{struct} \&{olist\_key} ${}{*}){}$ \\{list\_entry}${}(\|l\MG%
\\{keys},\39\\{min\_index});{}$\6
${}\|r\MG\\{eq}\K\|q\MG\\{eq};{}$\6
\4${}\}{}$\2\6
\&{else}\1\5
${}\|r\MG\\{low}\K\|q\MG\\{high};{}$\2\6
\4${}\}{}$\2\6
\&{else} \&{if} ${}(\|q\MG\\{eq}\G\T{0}){}$\5
${}\{{}$\1\6
${}\|r\K\|q;{}$\6
${}\\{min\_index}\K\|q\MG\\{eq};{}$\6
${}\|q\K{}$(\&{struct} \&{olist\_key} ${}{*}){}$ \\{list\_entry}${}(\|l\MG%
\\{keys},\39\\{min\_index});{}$\6
${}\|r\MG\\{eq}\K\|q\MG\\{eq};{}$\6
\4${}\}{}$\2\6
\&{else}\1\5
${}\|l\MG\\{top}\K\|q\MG\\{high};{}$\2\6
${}\\{memcpy}(\|p,\39\\{list\_entry}(\|l\MG\\{entries},\39\\{min\_index}),\39%
\|l\MG\\{sz});{}$\6
${}\|q\MG\\{low}\K\|l\MG\\{free};{}$\6
${}\|l\MG\\{free}\K\\{min\_index};{}$\6
\&{return} \|q${}\MG\|k;{}$\6
\4${}\}{}$\2\par
\fi

\M{97}Add an entry \PB{\|p} with key \PB{\|m} to the ordered list.
Return the index of the entry.
\Y\B\4\X84:List functions\X${}\mathrel+\E{}$\6
\&{long} \\{olist\_add}(\&{olist} ${}{*}\|l,\39{}$\&{long} \|m${},\39{}$%
\&{void} ${}{*}\|p){}$\1\1\2\2\6
${}\{{}$\1\6
\&{struct} \&{olist\_key} ${}{*}\|q,{}$ ${}{*}\|r;{}$\6
\&{long} \|b${},{}$ ${}{*}\\{last};{}$\7
${}\|b\K\\{olist\_next\_free}(\|l);{}$\6
\X99:point \PB{\|r} the \PB{\|b}-th entry and copy \PB{\|p} to it\X\6
${}\\{last}\K{\AND}(\|l\MG\\{top});{}$\6
\&{while} ${}(({*}\\{last})\G\T{0}){}$\5
${}\{{}$\1\6
${}\|q\K{}$(\&{struct} \&{olist\_key} ${}{*}){}$ \\{list\_entry}${}(\|l\MG%
\\{keys},\39{*}\\{last});{}$\6
\&{if} ${}(\|m<\|q\MG\|k){}$\1\5
${}\\{last}\K{\AND}(\|q\MG\\{low});{}$\2\6
\&{else} \&{if} ${}(\|m>\|q\MG\|k){}$\1\5
${}\\{last}\K{\AND}(\|q\MG\\{high});{}$\2\6
\&{else}\5
${}\{{}$\1\6
${}\|r\MG\\{eq}\K{*}\\{last};{}$\6
${}\|r\MG\\{low}\K\|q\MG\\{low};{}$\6
${}\|r\MG\\{high}\K\|q\MG\\{high};{}$\6
${}\|q\MG\\{low}\K{-}\T{1};{}$\6
${}\|q\MG\\{high}\K{-}\T{1};{}$\6
\&{break};\6
\4${}\}{}$\2\6
\4${}\}{}$\2\6
${}{*}\\{last}\K\|b;{}$\6
\&{return} \|b;\6
\4${}\}{}$\2\par
\fi

\M{98}This searches the ordered list \PB{\|l} for an entry with key \PB{\|m}.
If it finds one, it returns its index and sets \PB{\\{flag}}.
If it doesn't find one, and \PB{\|p} is not NULL,
it creates an entry with key \PB{\|m}
and moves \PB{${*}\|p$} into that entry and resets \PB{\\{flag}}.
\Y\B\4\D$\\{olist\_next\_free}(\|l)$ \5
$((\|l)\MG\\{free}\G\T{0})\?(\|l)\MG\\{free}:\\{list\_count}((\|l)\MG%
\\{entries}{}$)\par
\Y\B\4\X84:List functions\X${}\mathrel+\E{}$\6
\&{long} \\{olist\_find\_add}(\&{olist} ${}{*}\|l,\39{}$\&{long} \|m${},\39{}$%
\&{void} ${}{*}\|p,\39{}$\&{int} ${}{*}\\{flag}){}$\1\1\2\2\6
${}\{{}$\1\6
\&{struct} \&{olist\_key} ${}{*}\|q,{}$ ${}{*}\|r;{}$\6
\&{long} \|b${},{}$ ${}{*}\\{last};{}$\7
${}\\{last}\K{\AND}(\|l\MG\\{top});{}$\6
\&{while} ${}(({*}\\{last})\G\T{0}){}$\5
${}\{{}$\1\6
${}\|q\K{}$(\&{struct} \&{olist\_key} ${}{*}){}$ \\{list\_entry}${}(\|l\MG%
\\{keys},\39{*}\\{last});{}$\6
\&{if} ${}(\|m<\|q\MG\|k){}$\1\5
${}\\{last}\K{\AND}(\|q\MG\\{low});{}$\2\6
\&{else} \&{if} ${}(\|m>\|q\MG\|k){}$\1\5
${}\\{last}\K{\AND}(\|q\MG\\{high});{}$\2\6
\&{else}\SHC{ if duplicate key, return entry }\6
${}\{{}$\1\6
\&{if} ${}(\\{flag}\I\NULL){}$\1\5
${}{*}\\{flag}\K\T{1};{}$\2\6
\&{return} ${}{*}\\{last};{}$\6
\4${}\}{}$\2\6
\4${}\}{}$\2\6
\&{if} ${}(\|p\I\NULL){}$\5
${}\{{}$\1\6
${}\|b\K{*}\\{last}\K\\{olist\_next\_free}(\|l);{}$\6
\X99:point \PB{\|r} the \PB{\|b}-th entry and copy \PB{\|p} to it\X\6
\4${}\}{}$\2\6
\&{else}\1\5
${}\|b\K{-}\T{1};{}$\2\6
\&{if} ${}(\\{flag}\I\NULL){}$\1\5
${}{*}\\{flag}\K\T{0};{}$\2\6
\&{return} \|b;\6
\4${}\}{}$\2\par
\fi

\M{99}\B\X99:point \PB{\|r} the \PB{\|b}-th entry and copy \PB{\|p} to it\X${}%
\E{}$\6
${}\{{}$\1\6
\&{struct} \&{olist\_key} \\{rr};\7
${}\\{rr}.\\{high}\K\\{rr}.\\{low}\K\\{rr}.\\{eq}\K{-}\T{1};{}$\6
${}\\{rr}.\|k\K\|m;{}$\6
\&{if} ${}(\|l\MG\\{free}\G\T{0}){}$\5
${}\{{}$\1\6
${}\\{memcpy}(\\{list\_entry}(\|l\MG\\{entries},\39\|b),\39\|p,\39\|l\MG%
\\{sz});{}$\6
${}\|r\K{}$(\&{struct} \&{olist\_key} ${}{*}){}$ \\{list\_entry}${}(\|l\MG%
\\{keys},\39\|b);{}$\6
${}\|l\MG\\{free}\K\|r\MG\\{low};{}$\6
${}\\{memcpy}(\|r,\39{\AND}\\{rr},\39{}$\&{sizeof}(\&{struct} \&{olist\_key}));%
\6
\4${}\}{}$\2\6
\&{else}\5
${}\{{}$\1\6
${}\\{list\_push}(\|l\MG\\{entries},\39\|p);{}$\6
${}\|r\K{}$(\&{struct} \&{olist\_key} ${}{*}){}$ \\{list\_push}${}(\|l\MG%
\\{keys},\39{\AND}\\{rr});{}$\6
\4${}\}{}$\2\6
\4${}\}{}$\2\par
\Us97\ET98.\fi

\N{1}{100}Navigating Simplicial Complexes.
Simplices of all dimensions have a common initial part,
there is a word with all sorts of bit flags.
Yes I know I should implement this with all these bit fields as different
entries in the struct.  Maybe later.
The meaning of the bits in the type field is:
\item{$\cdot$} Bits 0 and 1 give the dimension.
\item{$\cdot$} Bit 2 is set if the simplex is in $K$.
\item{$\cdot$} Bit 3 is set if the simplex is critical.
\item{$\cdot$} Bit 4 is set if the simplex is paired with a codimension one
face.
\item{$\cdot$} Bits 5 and 6 give the index of that face if bit 4 is set.
If bit 3 is set then bit 5 is set the simplex is persistent critical.
If bits 3 and 4 are not set and the simplex is a triangle
then bit 5 gives the index of the coface to which the simplex is paired.
\item{$\cdot$} Bit 7 is set if the \PB{\|h} field is valid.
\item{$\cdot$} Bit 8 is set in an edge if the edge  is paired up and it is
known
that all gradient paths from the edge do not lead to critical edges.
\item{$\cdot$} Bit 9 is set in an edge \PB{\|e} when that edge is processed by
\PB{$\X5:extract the lower Star of \PB{\|v}\X$} with \PB{$\|v\K\\{get\_vertex}(%
\|e,\T{0})$}.
\item{$\cdot$} Bit 10 is set in an edge \PB{\|e} when that edge is processed by
\PB{$\X5:extract the lower Star of \PB{\|v}\X$} with \PB{$\|v\K\\{get\_vertex}(%
\|e,\T{1})$}.
\item{$\cdot$} Bits 11-15 are available for other uses.  For example, if
this program were adapted to use
the CGAL representation of a complex, edges and triangles are not represented
explicitly but the unused bits could indicate, say, which face of a tetrahedron
the triangle is, or which of its two vertices an edge is.

The field \PB{\|h} is the maximum of the values of the vertices of the simplex,
if bits 2 and 7 of \PB{\\{type}} are set.  Not essential, but there was this
unused
space, so what the heck.
I expect 16 bit resolution of the function is good enough.

The remaining  field \PB{\\{links}} is a variable sized array of pointers to
other simplices
and is used to navigate around the complex.
The entries in \PB{\\{links}} have the following meaning:
\item{} For a vertex:
\itemitem{$\cdot$}{\PB{\\{links}[\T{0}]}} is an edge containing the vertex, or %
\PB{$\NULL$} if there is none.
\item{} For an edge:
\itemitem{$\cdot$}{\PB{$\\{links}[\T{0}-\T{1}]$}} are the vertices in the edge.
\itemitem{$\cdot$}{\PB{\\{links}[\T{2}]}} is a triangle containing the edge.
\item{} For a triangle:
\itemitem{$\cdot$}{\PB{$\\{links}[\T{0}-\T{2}]$}} are the edges contained in
the triangle.
\itemitem{$\cdot$}{\PB{$\\{links}[\T{3}-\T{4}]$}} are the two tetrahedra which
contain the triangle.
\item{} For a tetrahedron:
\itemitem{$\cdot$}{\PB{$\\{links}[\T{0}-\T{3}]$}} are the triangles contained
in the tetrahedron.

\Y\B\F\\{vertex} \5
\\{int}\par
\B\F\\{edge} \5
\\{int}\par
\B\F\\{triangle} \5
\\{int}\par
\B\F\\{tetrahedron} \5
\\{int}\par
\fi

\M{101}\B\X61:\.{MorseExtract.h }\X${}\mathrel+\E{}$\6
\&{typedef} \&{struct} \&{vertexstruct} ${}\{{}$\1\6
\&{short} \\{type};\6
\&{short} \|h;\6
\&{void} ${}{*}\\{links}[\T{1}];{}$\2\6
${}\}{}$ \&{vertex};\6
\&{typedef} \&{struct} \&{edgestruct} ${}\{{}$\1\6
\&{short} \\{type};\6
\&{short} \|h;\6
\&{void} ${}{*}\\{links}[\T{3}];{}$\2\6
${}\}{}$ \&{edge};\6
\&{typedef} \&{struct} \&{trianglestruct} ${}\{{}$\1\6
\&{short} \\{type};\6
\&{short} \|h;\6
\&{void} ${}{*}\\{links}[\T{5}];{}$\2\6
${}\}{}$ \&{triangle};\6
\&{typedef} \&{struct} \&{tetrahedronstruct} ${}\{{}$\1\6
\&{short} \\{type};\6
\&{short} \|h;\6
\&{void} ${}{*}\\{links}[\T{4}];{}$\2\6
${}\}{}$ \&{tetrahedron};\6
\8\#\&{define} ${}\\{get\_vertex}(\|e,\39\|i){}$(\&{vertex} ${}{*}) \5((\|e)\MG%
\\{links}[\|i]){}$\6
\8\#\&{define} ${}\\{get\_edge\_vertices}(\|e,\39\\{vl}) \5((\\{vl})[\T{0}]\K%
\\{get\_vertex}(\|e,\39\T{0}),\39(\\{vl})[\T{1}]\K\\{get\_vertex}(\|e,\39%
\T{1})){}$\6
\8\#\&{define} \\{dimension}(\|s) \5${}((\|s)\MG\\{type}\AND\T{3}){}$\6
\8\#\&{define} \\{is\_critical}(\|t) \5${}((\|t)\MG\\{type}\AND\T{8}){}$\6
\8\#\&{define} ${}\\{other\_vertex\_in\_edge}(\|u,\39\|e) \5((\\{get\_vertex}(%
\|e,\39\T{0})\E\|u)\?\\{get\_vertex}(\|e,\39\T{1}):\\{get\_vertex}(\|e,\39%
\T{0})){}$\6
\8\#\&{define} ${}\\{coface}(\|t,\39\|i){}$(\&{tetrahedron} ${}{*}) \5((\|t)\MG%
\\{links}[\T{3}+\|i]){}$\6
\8\#\&{define} ${}\\{get\_edge}(\|t,\39\|i){}$(\&{edge} ${}{*}) \5((\|t)\MG%
\\{links}[\|i]){}$\6
\8\#\&{define} ${}\\{get\_face}(\|t,\39\|i){}$(\&{triangle} ${}{*}) \5((\|t)\MG%
\\{links}[\|i]){}$\6
\8\#\&{define} \\{is\_in\_K}(\|v) \5${}((\|v)\MG\\{type}\AND\T{4}){}$\6
\8\#\&{define} \\{value}(\|t)(\&{int}) \5${}((((\|t)\MG\\{type}\AND\T{\^80})\I%
\T{0})\?(\|t)\MG\|h:\\{max\_value}(\|t,\39\\{dimension}(\|t))){}$\6
\8\#\&{define} ${}\\{other\_coface}(\|s,\39\|t){}$(\&{tetrahedron} ${}{*}) %
\5(((\|t)\E(\|s)\MG\\{links}[\T{3}])\?(\|s)\MG\\{links}[\T{4}]:(\|s)\MG%
\\{links}[\T{3}]){}$\6
\8\#\&{define} \\{is\_deadend}(\|s) \5${}((\|s)\MG\\{type}\AND\T{\^100}){}$\6
\8\#\&{define} \\{make\_deadend}(\|s) \5${}((\|s)\MG\\{type}\MRL{{\OR}{\K}}\T{%
\^100}){}$\par
\fi

\M{102}Now some functions to manipulate and navigate these simplices

\Y\B\4\D$\\{set\_value}(\|t,\|f)$ \5
$((\|t)\MG\\{type}\MRL{{\OR}{\K}}\T{\^80},\39(\|t)\MG\|h\K\|f{}$)\par
\Y\B\4\X102:Simplex functions\X${}\E{}$\6
\&{void} \\{get\_triangle\_vertices}(\&{triangle} ${}{*}\|t,\39{}$\&{vertex}
${}{*}\\{vlist}[\T{3}]{}$)\SHC{ return a list of the vertices of \PB{\|t} }\6
${}\{{}$\1\6
\&{vertex} ${}{*}\|v;{}$\6
\&{edge} ${}{*}\|e;{}$\7
${}\|e\K\\{get\_edge}(\|t,\39\T{0});{}$\6
${}\\{get\_edge\_vertices}(\|e,\39\\{vlist});{}$\6
${}\|e\K\\{get\_edge}(\|t,\39\T{1});{}$\6
${}\|v\K\\{get\_vertex}(\|e,\39\T{1});{}$\6
\&{if} ${}(\|v\I\\{vlist}[\T{0}]\W\|v\I\\{vlist}[\T{1}]){}$\1\5
${}\\{vlist}[\T{2}]\K\|v;{}$\2\6
\&{else}\1\5
${}\\{vlist}[\T{2}]\K\\{get\_vertex}(\|e,\39\T{0});{}$\2\6
\4${}\}{}$\2\7
\&{void} \\{get\_tetrahedron\_vertices}(\&{tetrahedron} ${}{*}\|t,\39{}$%
\&{vertex} ${}{*}\\{vlist}[\T{4}]{}$)\SHC{ return a list of the vertices of %
\PB{\|t} }\6
${}\{{}$\1\6
\&{vertex} ${}{*}\\{vlistp}[\T{3}];{}$\6
\&{int} \|i;\7
${}\\{get\_triangle\_vertices}(\\{get\_face}(\|t,\39\T{0}),\39\\{vlist});{}$\6
${}\\{get\_triangle\_vertices}(\\{get\_face}(\|t,\39\T{1}),\39\\{vlistp});{}$\6
\&{for} ${}(\|i\K\T{0};{}$ ${}\|i<\T{3};{}$ ${}\|i\PP){}$\5
${}\{{}$\1\6
\&{if} ${}(\\{vlistp}[\|i]\I\\{vlist}[\T{0}]\W\\{vlistp}[\|i]\I\\{vlist}[\T{1}]%
\W\\{vlistp}[\|i]\I\\{vlist}[\T{2}]){}$\5
${}\{{}$\1\6
${}\\{vlist}[\T{3}]\K\\{vlistp}[\|i];{}$\6
\&{break};\6
\4${}\}{}$\2\6
\4${}\}{}$\2\6
\4${}\}{}$\2\par
\As103, 104, 105, 106, 108, 109, 110, 112, 113\ETs114.
\U1.\fi

\M{103}Return $\pm1$ depending on the orientation of the i-th edge of \PB{\|t}.
\Y\B\4\X102:Simplex functions\X${}\mathrel+\E{}$\6
\&{int} \\{edge\_orient}(\&{triangle} ${}{*}\|t,\39{}$\&{int} \|i)\1\1\2\2\6
${}\{{}$\1\6
\&{vertex} ${}{*}\\{vl}[\T{2}],{}$ ${}{*}\\{vlp}[\T{2}];{}$\7
\&{if} ${}(\|i\E\T{0}){}$\1\5
\&{return} \T{1};\2\6
${}\\{get\_edge\_vertices}(\\{get\_edge}(\|t,\39\T{0}),\39\\{vl});{}$\6
${}\\{get\_edge\_vertices}(\\{get\_edge}(\|t,\39\|i),\39\\{vlp});{}$\6
\&{if} ${}(\\{vlp}[\T{0}]\E\\{vl}[\T{1}]\V\\{vlp}[\T{1}]\E\\{vl}[\T{0}]){}$\1\5
\&{return} \T{1};\2\6
\&{return} ${}{-}\T{1};{}$\6
\4${}\}{}$\2\par
\fi

\M{104}a test for when the value of one vertex is greater
than another. The tiebreaker is just the address of the vertex.
\Y\B\4\X102:Simplex functions\X${}\mathrel+\E{}$\6
\&{long} \\{vertex\_compare}(\&{vertex} ${}{*}\|v,\39{}$\&{vertex} ${}{*}%
\|w){}$\1\1\2\2\6
${}\{{}$\1\6
\&{if} ${}(\\{value}(\|v)<\\{value}(\|w)){}$\1\5
\&{return} ${}{-}\T{1};{}$\2\6
\&{else} \&{if} ${}(\\{value}(\|v)>\\{value}(\|w)){}$\1\5
\&{return} \T{1};\2\6
\&{else}\1\5
\&{return} (\&{long}) \|v${}-{}$(\&{long}) \|w;\2\6
\4${}\}{}$\2\par
\fi

\M{105}Find the smallest or largest valued vertex in a list of vertices of
length n
\Y\B\4\D$\\{smallest\_vertex\_in\_edge}(\|e)$ \5
$(\\{vertex\_compare}(\\{get\_vertex}(\|e,\39\T{0}),\39\\{get\_vertex}(\|e,\39%
\T{1}))<\T{0}\?\\{get\_vertex}(\|e,\39\T{0}):\\{get\_vertex}(\|e,\39\T{1}){}$)%
\par
\B\4\D$\\{largest\_vertex\_in\_edge}(\|e)$ \5
$(\\{vertex\_compare}(\\{get\_vertex}(\|e,\39\T{0}),\39\\{get\_vertex}(\|e,\39%
\T{1}))<\T{0}\?\\{get\_vertex}(\|e,\39\T{1}):\\{get\_vertex}(\|e,\39\T{0}){}$)%
\par
\Y\B\4\X102:Simplex functions\X${}\mathrel+\E{}$\6
\&{int} \\{smallest\_vertex}(\&{vertex} ${}{*}\|v[\T{2}],\39{}$\&{int} \|n)\1\1%
\2\2\6
${}\{{}$\1\6
\&{int} \|i${},{}$ \|j;\7
\&{for} ${}(\|i\K\T{0},\39\|j\K\T{1};{}$ ${}\|j<\|n;{}$ ${}\|j\PP){}$\5
${}\{{}$\1\6
\&{if} ${}(\\{vertex\_compare}(\|v[\|j],\39\|v[\|i])<\T{0}){}$\1\5
${}\|i\K\|j;{}$\2\6
\4${}\}{}$\2\6
\&{return} \|i;\6
\4${}\}{}$\2\7
\&{int} \\{largest\_vertex}(\&{vertex} ${}{*}\|v[\T{2}],\39{}$\&{int} \|n)\1\1%
\2\2\6
${}\{{}$\1\6
\&{int} \|i${},{}$ \|j;\7
\&{for} ${}(\|i\K\T{0},\39\|j\K\T{1};{}$ ${}\|j<\|n;{}$ ${}\|j\PP){}$\5
${}\{{}$\1\6
\&{if} ${}(\\{vertex\_compare}(\|v[\|j],\39\|v[\|i])>\T{0}){}$\1\5
${}\|i\K\|j;{}$\2\6
\4${}\}{}$\2\6
\&{return} \|i;\6
\4${}\}{}$\2\par
\fi

\M{106}This routine tests whether the simplex \PB{\|t} is in the lower Star of
the vertex \PB{\|v}.
It does tiebreaking if two vertices in \PB{\|t} have the same value.

\Y\B\4\X102:Simplex functions\X${}\mathrel+\E{}$\6
\&{int} \\{is\_in\_lower\_Star}(\&{tetrahedron} ${}{*}\|t,\39{}$\&{vertex}
${}{*}\|v){}$\1\1\2\2\6
${}\{{}$\1\6
\&{vertex} ${}{*}\\{vlist}[\T{4}];{}$\7
${}\\{get\_tetrahedron\_vertices}(\|t,\39\\{vlist});{}$\6
\&{return} \|v${}\E\\{vlist}[\\{largest\_vertex}(\\{vlist},\39\T{4})];{}$\6
\4${}\}{}$\2\par
\fi

\M{107}These routines test whether a given simplex is a codimension one face of
another,
and if it is, returns the index of that face.
If it is not, then -1 is returned.
\Y\B\4\X61:\.{MorseExtract.h }\X${}\mathrel+\E{}$\6
\8\#\&{define} ${}\\{vertex\_in\_edge}(\|v,\39\|e) \5(((\|v)\E\\{get\_vertex}(%
\|e,\39\T{0}))\?\T{0}:(((\|v)\E\\{get\_vertex}(\|e,\39\T{1}))\?\T{1}:{-}%
\T{1})){}$\6
\8\#\&{define} ${}\\{edge\_in\_triangle}(\|e,\39\|t) \5(((\|e)\E\\{get\_edge}(%
\|t,\39\T{0}))\?\T{0}:(((\|e)\E\\{get\_edge}(\|t,\39\T{1}))\?\T{1}:(((\|e)\E%
\\{get\_edge}(\|t,\39\T{2}))\?\T{2}:{-}\T{1}))){}$\par
\fi

\M{108}\B\X102:Simplex functions\X${}\mathrel+\E{}$\6
\&{int} \\{triangle\_in\_tetrahedron}(\&{triangle} ${}{*}\|s,\39{}$%
\&{tetrahedron} ${}{*}\|t){}$\1\1\2\2\6
${}\{{}$\1\6
\&{int} \|i;\7
\&{for} ${}(\|i\K\T{0};{}$ ${}\|i<\T{4};{}$ ${}\|i\PP){}$\5
${}\{{}$\1\6
\&{if} ${}(\|s\E\\{get\_face}(\|t,\39\|i)){}$\1\5
\&{return} \|i;\2\6
\4${}\}{}$\2\6
\&{return} ${}{-}\T{1};{}$\6
\4${}\}{}$\2\par
\fi

\M{109}These routines take a codimension one face of a simplex
and find the unique other codimension one face which also contains
the given codimension 2 face.


\Y\B\4\X102:Simplex functions\X${}\mathrel+\E{}$\6
\&{edge} ${}{*}{}$\\{other\_edge}(\&{vertex} ${}{*}\|v,\39{}$\&{edge} ${}{*}%
\|f,\39{}$\&{triangle} ${}{*}\|t{}$)\SHC{ return the edge of t which contains v
but is not f }\6
${}\{{}$\1\6
\&{int} \|i;\6
\&{edge} ${}{*}\|e;{}$\7
\&{for} ${}(\|i\K\T{0};{}$ ${}\|i<\T{3};{}$ ${}\|i\PP){}$\5
${}\{{}$\1\6
${}\|e\K\\{get\_edge}(\|t,\39\|i);{}$\6
\&{if} ${}(\|e\E\|f){}$\1\5
\&{continue};\2\6
\&{if} ${}(\\{get\_vertex}(\|e,\39\T{0})\E\|v\V\\{get\_vertex}(\|e,\39\T{1})\E%
\|v){}$\1\5
\&{return} \|e;\2\6
\4${}\}{}$\2\6
\&{return} ${}\NULL{}$;\SHC{ error, v not in t }\6
\4${}\}{}$\2\7
\&{triangle} ${}{*}{}$\\{other\_face}(\&{edge} ${}{*}\|e,\39{}$\&{triangle}
${}{*}\|f,\39{}$\&{tetrahedron} ${}{*}\|t{}$)\SHC{ Find the face of t which
contains e but is not f }\6
${}\{{}$\1\6
\&{int} \|i;\6
\&{triangle} ${}{*}\|s;{}$\7
\&{for} ${}(\|i\K\T{0};{}$ ${}\|i<\T{4};{}$ ${}\|i\PP){}$\5
${}\{{}$\1\6
${}\|s\K\\{get\_face}(\|t,\39\|i);{}$\6
\&{if} ${}(\|f\I\|s\W\\{edge\_in\_triangle}(\|e,\39\|s)\G\T{0}){}$\1\5
\&{return} \|s;\2\6
\4${}\}{}$\2\6
\&{return} ${}\NULL{}$;\SHC{ error, e not in f or f not in t }\6
\4${}\}{}$\2\par
\fi

\M{110}Here are various routines for critical simplices.
In \PB{\\{unmake\_critical}}, the
formerly critical simplex is not actually removed from
the list of critical simplices.
So when running through \PB{\\{crit}} you may need to
check if the entries are in fact critical.
The routine \PB{\\{clean\_crit}} will delete all the noncritical entries from %
\PB{\\{crit}},

\Y\B\4\D$\\{unmake\_critical}(\|s)$ \5
$(\|s)\MG\\{type}\MRL{\AND{\K}}{}$\T{\^ff87}\par
\B\4\D$\\{make\_critical}(\|s)$ \5
$((\|s)\MG\\{type}\MRL{\AND{\K}}\T{\^ff87},\39(\|s)\MG\\{type}\MRL{{\OR}{\K}}%
\T{8},\39\\{plist\_push}(\\{crit}[\\{dimension}(\|s)],\39\|s){}$)\par
\B\4\D$\\{is\_persistent}(\|t)$ \5
$((\|t)\MG\\{type}\AND\T{\^20}{}$)\par
\B\4\D$\\{make\_persistent}(\|t)$ \5
$((\|t)\MG\\{type}\MRL{{\OR}{\K}}\T{\^20}{}$)\par
\B\4\D$\\{unmake\_persistent}(\|t)$ \5
$((\|t)\MG\\{type}\MRL{\AND{\K}}\T{\^ffdf}{}$)\par
\Y\B\4\X102:Simplex functions\X${}\mathrel+\E{}$\6
\&{void} \\{clean\_crit}(\&{void})\1\1\2\2\6
${}\{{}$\1\6
\&{tetrahedron} ${}{*}\|t;{}$\6
\&{triangle} ${}{*}\|f;{}$\6
\&{edge} ${}{*}\|e;{}$\6
\&{vertex} ${}{*}\|v;{}$\6
\&{list} ${}{*}\|l;{}$\7
${}\|l\K\\{crit}[\T{0}];{}$\6
\\{list\_read\_init}(\|l);\6
\&{while} ${}((\|v\K{}$(\&{vertex} ${}{*}){}$ \\{plist\_read}(\|l))${}\I%
\NULL){}$\5
${}\{{}$\1\6
\&{if} ${}(\R\\{is\_critical}(\|v)){}$\1\5
\\{list\_read\_delete}(\|l);\2\6
\4${}\}{}$\2\6
${}\|l\K\\{crit}[\T{1}];{}$\6
\\{list\_read\_init}(\|l);\6
\&{while} ${}((\|e\K{}$(\&{edge} ${}{*}){}$ \\{plist\_read}(\|l))${}\I\NULL){}$%
\5
${}\{{}$\1\6
\&{if} ${}(\R\\{is\_critical}(\|e)){}$\1\5
\\{list\_read\_delete}(\|l);\2\6
\4${}\}{}$\2\6
${}\|l\K\\{crit}[\T{2}];{}$\6
\\{list\_read\_init}(\|l);\6
\&{while} ${}((\|f\K{}$(\&{triangle} ${}{*}){}$ \\{plist\_read}(\|l))${}\I%
\NULL){}$\5
${}\{{}$\1\6
\&{if} ${}(\R\\{is\_critical}(\|f)){}$\1\5
\\{list\_read\_delete}(\|l);\2\6
\4${}\}{}$\2\6
${}\|l\K\\{crit}[\T{3}];{}$\6
\\{list\_read\_init}(\|l);\6
\&{while} ${}((\|t\K{}$(\&{tetrahedron} ${}{*}){}$ \\{plist\_read}(\|l))${}\I%
\NULL){}$\5
${}\{{}$\1\6
\&{if} ${}(\R\\{is\_critical}(\|t)){}$\1\5
\\{list\_read\_delete}(\|l);\2\6
\4${}\}{}$\2\6
\4${}\}{}$\2\par
\fi

\M{111} Routines to pair simplices.
The routine \PB{\\{is\_paired\_up}} finds whether the simplex \PB{\|t} is
paired with a
simplex of one higher dimension.
Likewise \PB{\\{is\_paired\_down}} finds whether the simplex \PB{\|t} is paired
with a
simplex of one lower dimension.
The routines \PB{\\{rij}} return the dimension \PB{\|j} simplex paired with the
dimension \PB{\|i} simplex \PB{\|t}.
The routines \PB{\\{pairij}} pair up the i simplex \PB{\\{s0}} and the j
simplex \PB{\\{s1}}.

\Y\B\4\X61:\.{MorseExtract.h }\X${}\mathrel+\E{}$\6
\8\#\&{define} \\{is\_paired\_up}(\|t) \5${}(((\|t)\MG\\{type}\AND\T{\^1C})\E%
\T{4}){}$\6
\8\#\&{define} \\{is\_paired\_down}(\|t) \5${}(((\|t)\MG\\{type}\AND\T{\^1C})\E%
\T{\^14}){}$\6
\8\#\&{define} \\{r32}(\|t)\\{get\_face} \5${}(\|t,\39((\|t)\MG\\{type}\AND\T{%
\^60})\GG\T{5}){}$\6
\8\#\&{define} \\{r21}(\|t)\\{get\_edge} \5${}(\|t,\39((\|t)\MG\\{type}\AND\T{%
\^60})\GG\T{5}){}$\6
\8\#\&{define} \\{r10}(\|t)\\{get\_vertex} \5${}(\|t,\39((\|t)\MG\\{type}\AND%
\T{\^20})\GG\T{5}){}$\6
\8\#\&{define} \\{r23}(\|t)\\{coface} \5${}(\|t,\39((\|t)\MG\\{type}\AND\T{%
\^20})\GG\T{5}){}$\6
\8\#\&{define} \\{r12}(\|t)(\&{triangle} ${}{*}) \5((\|t)\MG\\{links}[%
\T{2}]){}$\6
\8\#\&{define} \\{r01}(\|t)(\&{edge} ${}{*}) \5((\|t)\MG\\{links}[\T{0}]){}$\par
\fi

\M{112}\B\X102:Simplex functions\X${}\mathrel+\E{}$\6
\&{void} \\{pair01}(\&{vertex} ${}{*}\\{s0},\39{}$\&{edge} ${}{*}\\{s1}){}$\1\1%
\2\2\6
${}\{{}$\1\6
\&{int} \|n;\7
${}\\{s0}\MG\\{type}\MRL{\AND{\K}}\T{\^FF87};{}$\6
${}\\{s1}\MG\\{type}\MRL{\AND{\K}}\T{\^FF87};{}$\6
${}\\{s0}\MG\\{links}[\T{0}]\K\\{s1};{}$\6
${}\|n\K\\{vertex\_in\_edge}(\\{s0},\39\\{s1});{}$\6
${}\\{s1}\MG\\{type}\MRL{{\OR}{\K}}(\T{16}+(\|n\LL\T{5}));{}$\6
\4${}\}{}$\2\7
\&{void} \\{pair12}(\&{edge} ${}{*}\\{s0},\39{}$\&{triangle} ${}{*}\\{s1}){}$\1%
\1\2\2\6
${}\{{}$\1\6
\&{int} \|n;\7
${}\\{s0}\MG\\{type}\MRL{\AND{\K}}\T{\^FF87};{}$\6
${}\\{s1}\MG\\{type}\MRL{\AND{\K}}\T{\^FF87};{}$\6
${}\\{s0}\MG\\{links}[\T{2}]\K\\{s1};{}$\6
${}\|n\K\\{edge\_in\_triangle}(\\{s0},\39\\{s1});{}$\6
${}\\{s1}\MG\\{type}\MRL{{\OR}{\K}}(\T{16}+(\|n\LL\T{5}));{}$\6
\4${}\}{}$\2\7
\&{void} \\{pair23}(\&{triangle} ${}{*}\\{s0},\39{}$\&{tetrahedron} ${}{*}%
\\{s1}){}$\1\1\2\2\6
${}\{{}$\1\6
\&{int} \|n;\7
${}\\{s0}\MG\\{type}\MRL{\AND{\K}}\T{\^FF87};{}$\6
${}\\{s1}\MG\\{type}\MRL{\AND{\K}}\T{\^FF87};{}$\6
\&{if} ${}(\\{s0}\MG\\{links}[\T{4}]\E\\{s1}){}$\1\5
${}\\{s0}\MG\\{type}\MRL{{\OR}{\K}}\T{\^20};{}$\2\6
${}\|n\K\\{triangle\_in\_tetrahedron}(\\{s0},\39\\{s1});{}$\6
${}\\{s1}\MG\\{type}\MRL{{\OR}{\K}}(\T{16}+(\|n\LL\T{5}));{}$\6
\4${}\}{}$\2\par
\fi

\M{113}find the maximum value of the vertices of the simplex \PB{\|s}
\Y\B\4\X102:Simplex functions\X${}\mathrel+\E{}$\6
\&{int} \\{max\_value}(\&{void} ${}{*}\|s,\39{}$\&{int} \|d)\1\1\2\2\6
${}\{{}$\1\6
\&{tetrahedron} ${}{*}\\{te};{}$\6
\&{triangle} ${}{*}\|t;{}$\6
\&{edge} ${}{*}\|e;{}$\6
\&{int} \\{m0}${},{}$ \\{m1};\7
\&{if} ${}(\|s\E\NULL){}$\1\5
\&{return} ${}{-}\T{\^8000}{}$;\SHC{ smallest value }\2\6
\&{switch} (\|d)\5
${}\{{}$\1\6
\4\&{case} \T{3}:\5
${}\\{te}\K{}$(\&{tetrahedron} ${}{*}){}$ \|s;\6
${}\\{m0}\K\\{value}(\\{get\_face}(\\{te},\39\T{0}));{}$\6
${}\\{m1}\K\\{value}(\\{get\_face}(\\{te},\39\T{1}));{}$\6
\&{break};\6
\4\&{case} \T{2}:\5
${}\|t\K{}$(\&{triangle} ${}{*}){}$ \|s;\6
${}\\{m0}\K\\{value}(\\{get\_edge}(\|t,\39\T{0}));{}$\6
${}\\{m1}\K\\{value}(\\{get\_edge}(\|t,\39\T{1}));{}$\6
\&{break};\6
\4\&{case} \T{1}:\5
${}\|e\K{}$(\&{edge} ${}{*}){}$ \|s;\6
${}\\{m0}\K\\{value}(\\{get\_vertex}(\|e,\39\T{0}));{}$\6
${}\\{m1}\K\\{value}(\\{get\_vertex}(\|e,\39\T{1}));{}$\6
\&{break};\6
\4\&{default}:\5
\\{abort\_message}(\.{"max\ value\ of\ simple}\)\.{x\ of\ unknown\ dimensi}\)%
\.{on"});\6
\&{break};\6
\4${}\}{}$\2\6
\&{return} \\{max}${}(\\{m0},\39\\{m1});{}$\6
\4${}\}{}$\2\par
\fi

\M{114}find the minimum value of the vertices of the simplex \PB{\|s}
\Y\B\4\X102:Simplex functions\X${}\mathrel+\E{}$\6
\&{int} \\{min\_value}(\&{void} ${}{*}\|s,\39{}$\&{int} \|d)\1\1\2\2\6
${}\{{}$\1\6
\&{tetrahedron} ${}{*}\\{te};{}$\6
\&{triangle} ${}{*}\|t;{}$\6
\&{edge} ${}{*}\|e;{}$\6
\&{int} \\{m0}${},{}$ \\{m1};\7
\&{if} ${}(\|s\E\NULL){}$\1\5
\&{return} \T{\^7fff};\SHC{ largest value }\2\6
\&{switch} (\|d)\5
${}\{{}$\1\6
\4\&{case} \T{3}:\5
${}\\{te}\K{}$(\&{tetrahedron} ${}{*}){}$ \|s;\6
${}\\{m0}\K\\{min\_value}(\\{get\_face}(\\{te},\39\T{0}),\39\T{2});{}$\6
${}\\{m1}\K\\{min\_value}(\\{get\_face}(\\{te},\39\T{1}),\39\T{2});{}$\6
\&{break};\6
\4\&{case} \T{2}:\5
${}\|t\K{}$(\&{triangle} ${}{*}){}$ \|s;\6
${}\\{m0}\K\\{min\_value}(\\{get\_edge}(\|t,\39\T{0}),\39\T{1});{}$\6
${}\\{m1}\K\\{min\_value}(\\{get\_edge}(\|t,\39\T{1}),\39\T{1});{}$\6
\&{break};\6
\4\&{case} \T{1}:\5
${}\|e\K{}$(\&{edge} ${}{*}){}$ \|s;\6
${}\\{m0}\K\\{value}(\\{get\_vertex}(\|e,\39\T{0}));{}$\6
${}\\{m1}\K\\{value}(\\{get\_vertex}(\|e,\39\T{1}));{}$\6
\&{break};\6
\4\&{default}:\5
\\{abort\_message}(\.{"min\ value\ of\ simple}\)\.{x\ of\ unknown\ dimensi}\)%
\.{on"});\6
\&{break};\6
\4${}\}{}$\2\6
\&{return} \\{min}${}(\\{m0},\39\\{m1});{}$\6
\4${}\}{}$\2\par
\fi

\N{1}{115}Debugging routines.
\Y\B\4\X115:Debugging output\X${}\E{}$\6
\&{void} \\{abort\_message}(\&{char} ${}{*}\|s){}$\1\1\2\2\6
${}\{{}$\1\6
${}\\{printf}(\.{"Error:\ \%s"},\39\|s);{}$\6
\\{exit}(\T{1});\6
\4${}\}{}$\2\par
\U1.\fi

\N{1}{116}Constructing Complexes.
The following routines allocate a new simplex.
The last parameter \PB{\\{flag}} is $>0$ if the simplex is in \PB{\|K},
is $=0$ if the simplex is not in \PB{\|K}, and is $<0$
if you want it to be in \PB{\|K} if and only if all its
faces are in \PB{\|K}.

\Y\B\4\X61:\.{MorseExtract.h }\X${}\mathrel+\E{}$\6
\8\#\&{define} \\{vertex\_id}(\|v) \5${}((\|v)-\\{vertexlist}){}$\6
\8\#\&{define} \\{edge\_id}(\|e) \5${}((\|e)-\\{elist}){}$\6
\8\#\&{define} \\{triangle\_id}(\|f) \5${}((\|f)-\\{flist}){}$\6
\8\#\&{define} \\{tetrahedron\_id}(\|t) \5${}((\|t)-\\{tlist}){}$\6
\8\#\&{define} \\{id2vertex}(\\{id}) \5${}(\\{vertexlist}+(\\{id})){}$\6
\8\#\&{define} \\{id2edge}(\\{id}) \5${}(\\{elist}+(\\{id})){}$\6
\8\#\&{define} \\{id2triangle}(\\{id}) \5${}(\\{flist}+(\\{id})){}$\6
\8\#\&{define} \\{id2tetrahedron}(\\{id}) \5${}(\\{tlist}+(\\{id})){}$\par
\fi

\M{117}\B\X117:Subroutines for constructing complexes\X${}\E{}$\6
\&{vertex} ${}{*}{}$\\{new\_vertex}(\&{long} \\{id}${},\39{}$\&{short} %
\\{val}${},\39{}$\&{short} \\{flag})\1\1\2\2\6
${}\{{}$\1\6
\&{vertex} ${}{*}\|v;{}$\7
${}\|v\K\\{id2vertex}(\\{id});{}$\6
${}\|v\MG\\{type}\K(\\{flag})\?\T{\^84}:\T{\^80}{}$;\SHC{ indicate in $K$ or
not }\6
${}\|v\MG\\{links}[\T{0}]\K\NULL;{}$\6
${}\|v\MG\|h\K\\{val};{}$\6
\&{return} \|v;\6
\4${}\}{}$\2\par
\As118, 119, 120\ETs123.
\U1.\fi

\M{118}Construct a new edge
\Y\B\4\X117:Subroutines for constructing complexes\X${}\mathrel+\E{}$\6
\&{edge} ${}{*}{}$\\{new\_edge}(\&{long} \\{id}${},\39{}$\&{long} \\{vids}[%
\T{2}]${},\39{}$\&{short} \\{flag})\1\1\2\2\6
${}\{{}$\1\6
\&{edge} ${}{*}\|e;{}$\6
\&{short} \\{flagp};\6
\&{vertex} ${}{*}\\{v0},{}$ ${}{*}\\{v1};{}$\7
${}\|e\K\\{id2edge}(\\{id});{}$\6
${}\\{v0}\K\\{id2vertex}(\\{vids}[\T{0}]);{}$\6
${}\\{v1}\K\\{id2vertex}(\\{vids}[\T{1}]);{}$\6
${}\|e\MG\\{links}[\T{0}]\K\\{v0};{}$\6
${}\|e\MG\\{links}[\T{1}]\K\\{v1};{}$\6
${}\|e\MG\\{links}[\T{2}]\K\NULL;{}$\6
${}\|e\MG\|h\K\\{max}(\\{v0}\MG\|h,\39\\{v1}\MG\|h);{}$\6
${}\\{flagp}\K(\\{flag}\W\\{is\_in\_K}(\\{v0})\W\\{is\_in\_K}(\\{v1}));{}$\6
${}\|e\MG\\{type}\K(\\{flagp})\?\T{5}:\T{1};{}$\6
\&{if} ${}(\\{flag}>\T{0}\W\\{flagp}\E\T{0}){}$\1\5
\\{abort\_message}(\.{"vertices\ of\ edge\ in}\)\.{\ K\ must\ be\ in\ K"});\2\6
\&{if} ${}(\\{v0}\MG\\{links}[\T{0}]\E\NULL){}$\1\5
${}\\{v0}\MG\\{links}[\T{0}]\K\|e;{}$\2\6
\&{if} ${}(\\{v1}\MG\\{links}[\T{0}]\E\NULL){}$\1\5
${}\\{v1}\MG\\{links}[\T{0}]\K\|e;{}$\2\6
\&{return} \|e;\6
\4${}\}{}$\2\par
\fi

\M{119}\B\X117:Subroutines for constructing complexes\X${}\mathrel+\E{}$\6
\&{triangle} ${}{*}{}$\\{new\_triangle}(\&{long} \\{id}${},\39{}$\&{long} %
\\{eids}[\T{3}]${},\39{}$\&{short} \\{flag})\1\1\2\2\6
${}\{{}$\1\6
\&{triangle} ${}{*}\|t;{}$\6
\&{vertex} ${}{*}\\{vl}[\T{3}],{}$ ${}{*}\|v[\T{2}];{}$\6
\&{edge} ${}{*}\\{e0},{}$ ${}{*}\\{e1},{}$ ${}{*}\\{e2};{}$\6
\&{short} \\{flagp};\7
${}\\{e0}\K\\{id2edge}(\\{eids}[\T{0}]);{}$\6
${}\\{e1}\K\\{id2edge}(\\{eids}[\T{1}]);{}$\6
${}\\{e2}\K\\{id2edge}(\\{eids}[\T{2}]);{}$\6
${}\\{get\_edge\_vertices}(\\{e0},\39\\{vl});{}$\6
${}\\{get\_edge\_vertices}(\\{e1},\39\|v);{}$\6
\&{if} ${}(\\{vertex\_in\_edge}(\|v[\T{0}],\39\\{e0})<\T{0}){}$\1\5
${}\\{vl}[\T{2}]\K\|v[\T{0}];{}$\2\6
\&{else} \&{if} ${}(\\{vertex\_in\_edge}(\|v[\T{1}],\39\\{e0})<\T{0}){}$\1\5
${}\\{vl}[\T{2}]\K\|v[\T{1}];{}$\2\6
\&{else}\1\5
\\{abort\_message}(\.{"new\ triangle\ has\ mo}\)\.{re\ than\ three\ vertic}\)%
\.{es"});\2\6
${}\\{get\_edge\_vertices}(\\{e2},\39\|v);{}$\6
\&{if} ${}(\|v[\T{0}]\I\\{vl}[\T{0}]\W\|v[\T{0}]\I\\{vl}[\T{1}]\W\|v[\T{0}]\I%
\\{vl}[\T{2}]){}$\1\5
\\{abort\_message}(\.{"new\ triangle\ has\ mo}\)\.{re\ than\ three\ vertic}\)%
\.{es-1"});\2\6
\&{if} ${}(\|v[\T{1}]\I\\{vl}[\T{0}]\W\|v[\T{1}]\I\\{vl}[\T{1}]\W\|v[\T{1}]\I%
\\{vl}[\T{2}]){}$\1\5
\\{abort\_message}(\.{"new\ triangle\ has\ mo}\)\.{re\ than\ three\ vertic}\)%
\.{es-2"});\2\6
${}\|t\K\\{id2triangle}(\\{id});{}$\6
${}\|t\MG\\{links}[\T{0}]\K\\{e0};{}$\6
${}\|t\MG\\{links}[\T{1}]\K\\{e1};{}$\6
${}\|t\MG\\{links}[\T{2}]\K\\{e2};{}$\6
${}\|t\MG\|h\K\\{max}(\\{e0}\MG\|h,\39\\{e1}\MG\|h);{}$\6
${}\\{flagp}\K(\\{flag}\W\\{is\_in\_K}(\\{e0})\W\\{is\_in\_K}(\\{e1})\W\\{is%
\_in\_K}(\\{e2}));{}$\6
${}\|t\MG\\{type}\K(\\{flagp})\?\T{6}:\T{2};{}$\6
${}\|t\MG\\{links}[\T{3}]\K\NULL;{}$\6
${}\|t\MG\\{links}[\T{4}]\K\NULL;{}$\6
\&{if} ${}(\\{e0}\MG\\{links}[\T{2}]\E\NULL){}$\1\5
${}\\{e0}\MG\\{links}[\T{2}]\K\|t;{}$\2\6
\&{if} ${}(\\{e1}\MG\\{links}[\T{2}]\E\NULL){}$\1\5
${}\\{e1}\MG\\{links}[\T{2}]\K\|t;{}$\2\6
\&{if} ${}(\\{e2}\MG\\{links}[\T{2}]\E\NULL){}$\1\5
${}\\{e2}\MG\\{links}[\T{2}]\K\|t;{}$\2\6
\&{if} ${}(\\{flag}>\T{0}\W\\{flagp}\E\T{0}){}$\1\5
\\{abort\_message}(\.{"edges\ of\ triangle\ i}\)\.{n\ K\ must\ be\ in\ K"});\2\6
\&{return} \|t;\6
\4${}\}{}$\2\par
\fi

\M{120}\B\X117:Subroutines for constructing complexes\X${}\mathrel+\E{}$\6
\&{tetrahedron} ${}{*}{}$\\{new\_tetrahedron}(\&{long} \\{id}${},\39{}$\&{long}
\\{fids}[\T{4}]${},\39{}$\&{short} \\{flag})\1\1\2\2\6
${}\{{}$\1\6
\&{tetrahedron} ${}{*}\|t;{}$\6
\&{vertex} ${}{*}\\{vl}[\T{4}],{}$ ${}{*}\\{vlp}[\T{3}];{}$\6
\&{int} \|i;\6
\&{short} \\{flagp};\6
\&{triangle} ${}{*}\\{f0},{}$ ${}{*}\\{f1},{}$ ${}{*}\\{f2},{}$ ${}{*}%
\\{f3};{}$\7
${}\\{f0}\K\\{id2triangle}(\\{fids}[\T{0}]);{}$\6
${}\\{f1}\K\\{id2triangle}(\\{fids}[\T{1}]);{}$\6
${}\\{f2}\K\\{id2triangle}(\\{fids}[\T{2}]);{}$\6
${}\\{f3}\K\\{id2triangle}(\\{fids}[\T{3}]);{}$\6
${}\\{get\_triangle\_vertices}(\\{f0},\39\\{vl});{}$\6
${}\\{get\_triangle\_vertices}(\\{f1},\39\\{vlp});{}$\6
\&{for} ${}(\|i\K\T{0};{}$ ${}\|i<\T{3};{}$ ${}\|i\PP){}$\5
${}\{{}$\1\6
\&{if} ${}(\\{vlp}[\|i]\I\\{vl}[\T{0}]\W\\{vlp}[\|i]\I\\{vl}[\T{1}]\W\\{vlp}[%
\|i]\I\\{vl}[\T{2}]){}$\5
${}\{{}$\1\6
${}\\{vl}[\T{3}]\K\\{vlp}[\|i];{}$\6
\&{break};\6
\4${}\}{}$\2\6
\4${}\}{}$\2\6
\X121:make sure \PB{\\{vlp}} entries are all in \PB{\\{vl}}\X\6
${}\\{get\_triangle\_vertices}(\\{f2},\39\\{vlp});{}$\6
\X121:make sure \PB{\\{vlp}} entries are all in \PB{\\{vl}}\X\6
${}\\{get\_triangle\_vertices}(\\{f3},\39\\{vlp});{}$\6
\X121:make sure \PB{\\{vlp}} entries are all in \PB{\\{vl}}\X\6
${}\|t\K\\{id2tetrahedron}(\\{id});{}$\6
${}\|t\MG\\{links}[\T{0}]\K\\{f0};{}$\6
${}\|t\MG\\{links}[\T{1}]\K\\{f1};{}$\6
${}\|t\MG\\{links}[\T{2}]\K\\{f2};{}$\6
${}\|t\MG\\{links}[\T{3}]\K\\{f3};{}$\6
${}\|t\MG\|h\K\\{max}(\\{f0}\MG\|h,\39\\{f1}\MG\|h);{}$\6
${}\\{flagp}\K(\\{flag}\W\\{is\_in\_K}(\\{f0})\W\\{is\_in\_K}(\\{f1})\W\\{is%
\_in\_K}(\\{f2})\W\\{is\_in\_K}(\\{f3}));{}$\6
${}\|t\MG\\{type}\K(\\{flagp})\?\T{7}:\T{3};{}$\6
\&{if} ${}(\\{f0}\MG\\{links}[\T{3}]\E\NULL){}$\1\5
${}\\{f0}\MG\\{links}[\T{3}]\K\|t;{}$\2\6
\&{else} \&{if} ${}(\\{f0}\MG\\{links}[\T{4}]\E\NULL){}$\1\5
${}\\{f0}\MG\\{links}[\T{4}]\K\|t;{}$\2\6
\&{else}\1\5
\\{abort\_message}(\.{"a\ triangle\ can\ be\ i}\)\.{n\ only\ two\ tetrahedr}\)%
\.{a"});\2\6
\&{if} ${}(\\{f1}\MG\\{links}[\T{3}]\E\NULL){}$\1\5
${}\\{f1}\MG\\{links}[\T{3}]\K\|t;{}$\2\6
\&{else} \&{if} ${}(\\{f1}\MG\\{links}[\T{4}]\E\NULL){}$\1\5
${}\\{f1}\MG\\{links}[\T{4}]\K\|t;{}$\2\6
\&{else}\1\5
\\{abort\_message}(\.{"a\ triangle\ can\ be\ i}\)\.{n\ only\ two\ tetrahedr}\)%
\.{a-1"});\2\6
\&{if} ${}(\\{f2}\MG\\{links}[\T{3}]\E\NULL){}$\1\5
${}\\{f2}\MG\\{links}[\T{3}]\K\|t;{}$\2\6
\&{else} \&{if} ${}(\\{f2}\MG\\{links}[\T{4}]\E\NULL){}$\1\5
${}\\{f2}\MG\\{links}[\T{4}]\K\|t;{}$\2\6
\&{else}\1\5
\\{abort\_message}(\.{"a\ triangle\ can\ be\ i}\)\.{n\ only\ two\ tetrahedr}\)%
\.{a-2"});\2\6
\&{if} ${}(\\{f3}\MG\\{links}[\T{3}]\E\NULL){}$\1\5
${}\\{f3}\MG\\{links}[\T{3}]\K\|t;{}$\2\6
\&{else} \&{if} ${}(\\{f3}\MG\\{links}[\T{4}]\E\NULL){}$\1\5
${}\\{f3}\MG\\{links}[\T{4}]\K\|t;{}$\2\6
\&{else}\1\5
\\{abort\_message}(\.{"a\ triangle\ can\ be\ i}\)\.{n\ only\ two\ tetrahedr}\)%
\.{a-3"});\2\6
\&{if} ${}(\\{flag}>\T{0}\W\\{flagp}\E\T{0}){}$\1\5
\\{abort\_message}(\.{"faces\ of\ tetrahedro}\)\.{n\ in\ K\ must\ be\ in\ K"});%
\2\6
\&{return} \|t;\6
\4${}\}{}$\2\par
\fi

\M{121}\B\X121:make sure \PB{\\{vlp}} entries are all in \PB{\\{vl}}\X${}\E{}$\6
\&{for} ${}(\|i\K\T{0};{}$ ${}\|i<\T{3};{}$ ${}\|i\PP){}$\5
${}\{{}$\1\6
\&{if} ${}(\\{vlp}[\|i]\I\\{vl}[\T{0}]\W\\{vlp}[\|i]\I\\{vl}[\T{1}]\W\\{vlp}[%
\|i]\I\\{vl}[\T{2}]\W\\{vlp}[\|i]\I\\{vl}[\T{3}]){}$\1\5
\\{abort\_message}(\.{"new\ tetrahedron\ has}\)\.{\ more\ than\ four\ vert}\)%
\.{ices"});\2\6
\4${}\}{}$\2\par
\U120.\fi

\M{122}\B\X122:output simplex pairings\X${}\E{}$\6
${}\{{}$\1\6
\&{FILE} ${}{*}\\{df};{}$\6
\&{vertex} ${}{*}\|v;{}$\6
\&{edge} ${}{*}\|e;{}$\6
\&{triangle} ${}{*}\|f;{}$\6
\&{tetrahedron} ${}{*}\|t;{}$\7
${}\\{df}\K\\{fopen}(\\{argv}[\T{2}],\39\.{"w"});{}$\6
\&{if} ${}(\\{df}\E\NULL){}$\1\5
\\{abort\_message}(\.{"Cannot\ open\ output\ }\)\.{file"});\2\6
\&{for} ${}(\|i\K\T{0};{}$ ${}\|i<\T{4};{}$ ${}\|i\PP{}$)\SHC{ output number if
i simplices and critical i simplices }\6
${}\{{}$\1\6
${}\\{fprintf}(\\{df},\39\.{"\%d\ \%d\\n"},\39\\{num\_simp}[\|i],\39\|n[%
\|i]);{}$\6
\4${}\}{}$\2\6
\&{for} ${}(\|i\K\T{0},\39\|v\K\\{vertexlist};{}$ ${}\|i<\\{num\_simp}[%
\T{0}];{}$ ${}\|i\PP,\39\|v\PP){}$\5
${}\{{}$\1\6
\&{if} ${}(\R\\{is\_in\_K}(\|v)){}$\1\5
${}\\{fprintf}(\\{df},\39\.{"x\%d\\n"},\39\|i);{}$\2\6
\4${}\}{}$\2\6
${}\\{fprintf}(\\{df},\39\.{"z\\n"});{}$\6
\&{for} ${}(\|i\K\T{0},\39\|e\K\\{elist};{}$ ${}\|i<\\{num\_simp}[\T{1}];{}$
${}\|i\PP,\39\|e\PP){}$\5
${}\{{}$\1\6
\&{if} ${}(\R\\{is\_in\_K}(\|e)){}$\1\5
${}\\{fprintf}(\\{df},\39\.{"x\\n"});{}$\2\6
\&{else} \&{if} (\\{is\_critical}(\|e))\1\5
${}\\{fprintf}(\\{df},\39\.{"c\\n"});{}$\2\6
\&{else} \&{if} (\\{is\_paired\_up}(\|e))\1\5
${}\\{fprintf}(\\{df},\39\.{"a\%d\\n"},\39\\{triangle\_id}(\\{r12}(\|e)));{}$\2%
\6
\&{else}\1\5
${}\\{fprintf}(\\{df},\39\.{"b\%d\\n"},\39\\{vertex\_id}(\\{r10}(\|e)));{}$\2\6
\4${}\}