MorseExtract

This software implements an algorithm from the paper Generating discrete Morse functions from point data by Henry King, Kevin Knudson, and Neža Mramor. This algorithm takes a function on the vertices of a 3 dimensional simplicial complex and converts it into a discrete Morse function in the sense of Forman. It also cancels pairs of critical simplices which are connected by a single gradient path and whose values differ by less than a prescribed persistence.

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.

Compiling the programs:

These programs can be compiled using the commands:

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

The last command works on a Mac running OSX but needs to be changed for other platforms so OpenGL can be accessed. Perhaps the following will work:

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

Running the programs:

Here is a sample run.

./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

Mouse actions:

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.

Command line options:

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.

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.

Running the programs:

Here is a sample run.

./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.

Navigating around the complex using view:

view could use a great deal of improvement, but this is a start.

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.

File formats:

I'll refer to the filenames given in the sample run above. All files are ascii text files.

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.