- The algorithm is implimented in main2.c view.c simplex.c list.c globals.c homology.c cancel.c globals.h Morse.h list.h simplex.h cancel.h and mytypes.h All but the first two and last of these are generated by the CWeb files simplex.w list.w homology.w and cancel.w.
- randomvertices.c generates random points in 3 dimensional space and calculates function values at those points. As is, it uses the function x^3-x+y^3-y+z^3-z, but this is easily changed to whatever the user wishes.
- enclose.c takes a vertex file and adds
four more vertices which enclose the region in a tetrahedron, this is
needed for some technical reason, to make it easy to close up the
Delaunay triangulation to a 3 sphere.

- qhprep1.c
takes the output of enclose.c, and produces a file suitable for input
to a program
qdelaunay (available from here)
which produces a triangulation with the given points as
vertices.

- gcc -O3 randomvertices.c -o randomvertices
- gcc -O3 enclose.c -o enclose
- gcc -O3 qhprep1.c -o qhprep
- gcc -O3 main2.c view.c simplex.c list.c globals.c homology.c
cancel.c -lobjc -framework OpenGL -framework GLUT -o extract

- gcc -O3 main.c view.c simplex.c list.c globals.c homology.c
cancel.c -o extract -lglut -lGLU -lGL -lXmu -lXi -lXext -lX11 -lm

./randomvertices 30000 > fv

./enclose fv

./qhprep fv | qdelaunay QJ i > ft

./extract -v fv -q ft

The first command generates 30000 random points and assigns a value to each. The second command encloses the points in a tetrahedron. The third finds a triangulation with the points as vertices. The last command computes a discrete Morse function and allows you to visualize it. You should be presented with a window with a black background, some white dots (which are the vertices) and some colored balls, some with lines coming from them (these are the critical simplices, The balls are around the barycenter of the simplex and the lines go to the barycenters of its codimension one faces. Possibly a purple ball representing a critical vertex fills the window initially.)

Navigating in the viewer:

Keyboard actions:

- space = move forward
- v = move backward
- b,c = rotate around some up-down axis
- f,g = rotate around some up-down axis through the selected simplex and also translate this simplex to the center
- q = quit

- Use left mouse button to drag and rotate scene.
- Use middle mouse button to select a critical simplex.
- Use right mouse button to select from menu-
- Display/Hide 0-1 gradient paths = display grad paths to a selected vertex or from a selected edge.
- Display/Hide 1-2 gradient paths = display grad paths to a selected edge or from a selected triangle. Only lines connecting the barycenters of the edges and triangles in the grad path are shown.
- Display/Hide 2-3 gradient paths = display grad paths to a selected triangle or from a selected tetrahedron. Only lines connecting the barycenters of the tetrahedra and triangles in the grad path are shown.
- Display/Hide descending 2 discs = display all grad paths to a selected edge or from a selected triangle. All triangles in the grad paths are displayed.
- Display/Hide link = display the link of the highest vertex of the selected simplex. The lower link is shown in red.
- Display/Hide lower link = display the lower link of the highest
vertex of the selected simplex.

- Cancel 0-1 = Do persistence canceling of vertices and edges, then double the persistence for the next canceling, so each time you click it you cancel more and more.
- Cancel 1-2 = Do persistence canceling of triangles and edges, then double the persistence for the next canceling.
- Cancel 2-3 = Do persistence canceling of triangles and tetrahedra, then double the persistence for the next canceling.
- Compute Z/pZ Betti numbers = Compute the Betti numbers for Z/pZ homology for all primes p <= 37.
- set/reset option = display actual smooth gradient paths for the
function x^3-x+y^3-y+z^3-z, they appear in red. You can use this
to compare the smooth paths to their combinatorial
approximations. Also after this is clicked on, I think I have it
set up so that when descending 2 discs are displayed, only those going
between critical simplices are displayed. Before clicking, all
grad paths are displayed, even those not ending at a critical edge.

extract has the following command line options:

-v fv
A file of vertices, must be present

-q ft A file of tetrahedra, in the format output by qdelaunay. If neither the -q or -t option is given, it is assumed the tetrahedron file is on stdin in the qdelaunay format.

-t file Use instead of -q if you have a plain tetrahedron file, without the extra stuff from qdelaunay.

-p persistence The persistence amount, default = .1.

-h maxh any two vertices with values above this will be considered to have equal value for persistence purposes, default = 1.

-l minh any two vertices with values below this will be considered to have equal value for persistence purposes. default = 0.

-x scalex scale all x values by dividing by this factor, default = 1.

-y scaley scale all x values by dividing by this factor, default = 1.

-z scalez scale all x values by dividing by this factor, default = 1.

-o val A more complicated method is used to assign values to vertices in the lower link which might give a discrete vector field which more closely approximates an underlying smooth vector field. It's not clear it makes much difference. The following argument val is ignored, but must be present.

-q ft A file of tetrahedra, in the format output by qdelaunay. If neither the -q or -t option is given, it is assumed the tetrahedron file is on stdin in the qdelaunay format.

-t file Use instead of -q if you have a plain tetrahedron file, without the extra stuff from qdelaunay.

-p persistence The persistence amount, default = .1.

-h maxh any two vertices with values above this will be considered to have equal value for persistence purposes, default = 1.

-l minh any two vertices with values below this will be considered to have equal value for persistence purposes. default = 0.

-x scalex scale all x values by dividing by this factor, default = 1.

-y scaley scale all x values by dividing by this factor, default = 1.

-z scalez scale all x values by dividing by this factor, default = 1.

-o val A more complicated method is used to assign values to vertices in the lower link which might give a discrete vector field which more closely approximates an underlying smooth vector field. It's not clear it makes much difference. The following argument val is ignored, but must be present.

Older version:

Following is an older version of this software. The main difference is that internally, in the new version of the software above, the only explicitly represented simplices are vertices and tetrahedra, a la CGAL's representation. So an edge, say, would be referred to as the edge in some specific tetrahedron thus there would be many ways of referring to the same edge since it is in many tetrahedra (a bit less than 6 on average). In the old version, all simplices are explicitly represented. The tradeoffs are:

- old version advantages: Faster computations because you can immediately check, say, that an edge or triangle is critical.
- old version disadvantages: Requires more storage and a much
larger input file. It also takes much more time to prepare the
input file since all edges and triangles must be identified, whereas
the new version only requires a list of the vertices and
tetrahedra. If the complex is large enough that virtual memory
must be used, the computations slow down considerably. This
happens sooner in the old version. Also the viewing software is
less developed and there may be more bugs in the old version.

- The algorithm is implemented in MorseExtract.c and MorseExtract.h which are generated by the Cweb file MorseExtract.w which also produces the TeX documentation MorseExtract.tex and MorseExtract.pdf. In addition there is other software which may be helpful in utilizing MorseExtract.
- randomvertices.c generates random points in 3 dimensional space and calculates function values at those points. As is, it uses the function x^3-x+y^3-y+z^3-z, but this is easily changed to whatever the user wishes.
- qhprep.c takes the output of randomvertices.c, or any file giving points and function values, and produces a file suitable for input to a program qdelaunay (available from here) which produces a triangulation with the given points as vertices. For technical reasons, it also adds four vertices of a tetrahedron which encloses the given points.
- xqhconvert.c takes the output of qdelaunay and converts it into a format suitable for input to MorseExtract. This program is generated by the Cweb file xqhconvert.w.
- main1.c can be compiled with MorseExtract.c to make an application which runs the algorithm and reports the results.
- main.c
and view.c
can be compiled with MorseExtract.c to make an application which runs
the algorithm and allows you to view the results
interactively. This is still a bit buggy. It uses OpenGL so
you need that.

./randomvertices 30000 > randv

./qhprep randv v.tmp | ./qdelaunay QJ -Fx i >qdata

./xqhconvert v.tmp < qdata >sdata

./MorseExtract 100 randv < sdata

The first command generates 30000 random points and assigns a value to each. The second command encloses the points in a tetrahedron and finds a triangulation with the points as vertices. The third command converts the triangulation to a form suitable for input to MorseExtract. The last command computes a discrete Morse function and allows you to visualize it. It does little cancelation because the persistence is set to 100 which is small compared to the 65000 range of function values.

- Space bar moves you forward
- v moves you back
- c or b rotates you.
- dragging with the left mouse button moves you around.
- clicking on a critical simplex with the middle mouse button selects the simplex. (The critical simplices are shown as a colored sphere at the barycenter with colored lines to the barycenters of codimension one faces.)
- clicking the right mouse button gives a menu which allows you to
see gradient paths to or from a selected critical simplex.

- randv has one line per point. Each line is four numbers. The first three are the x y and z coordinates and the fourth is the function value.
- v.tmp has one line per point. Each line is an integer which is the function value, scaled to the range -32500 to 32500.
- qdata is explained in qdelaunay's documentation. The first line is the number of boundary vertices which should always be 4. The next four lines are the indices of the four boundary vertices. The sixth line is the number of tetrahedra in the triangulation. Following that is one line for each tetrahedron. Each of these lines gives the four indices of the vertices of the tetrahedron.
- sdata gives all the simplices in the triangulation obtained from
qdata by coning off its boundary tetrahedron. Some of these
simplices are designated as being in a subcomplex K, which is the
complex we are interested in finding a discrete Morse function on.

- The first line is the number of vertices.

- Following that, there is one line for each vertex, an integer
which is the function value, scaled to the range -32500 to 32500.
If a vertex is not in K, this number is preceded by the letter x (and is in fact ignored).

- The next line is the number of edges.
- Following that, there is one line for each edge, two integers
giving the indices of its two boundary vertices. Again, if the
edge is not in K, these numbers are preceded by the letter x. This x is optional if one of the
boundary vertices is not in K.

- The next line is the number of triangles.
- Following that, there is one line for each triangle, three
integers
giving the indices of its three boundary edges. Again, if the
triangle is not in K, these numbers are preceded by the letter x. This x is optional if one of the
boundary edges is not in K.

- The next line is the number of tetrahedra.
- Following that, there is one line for each tetrahedron, four
integers
giving the indices of its four boundary triangles. Again, if the
tetrahedron is not in K, these numbers are preceded by the letter x. This x is optional if one of the
boundary triangles is not in K.