include TOPCOM as optional spkg

[vbraun]

TOPCOM is a C++ program for triangulating polyhedra. More generally, it can find a single triangulation as well as enumerate all triangulations of a "point configuration", that is, the convex hull of points in euclidean space such that all vertices of simplices of the triangulation are in the given (finite) list of points.

One problem with the upstream distribution is that it statically links many helper programs, yielding almost 200mb of binaries. Therefore, I changed the TOPCOM build system to dynamically link TOPCOM via libtools to reduce size

My libtoolized TOPCOM spkg is here:

http://www.stp.dias.ie/~vbraun/Sage/spkg/TOPCOM-0.16.2.p2.spkg

None of the patches in this ticket should be applied to the Sage library! The TOPCOM binaries are (optionally) used by the patches in #9918: triangulate point configurations.

CC: @sagetrac-mhampton @novoselt

Component: packages: optional

Author: Volker Braun

Reviewer: Marshall Hampton

Issue created by migration from https://trac.sagemath.org/ticket/8169

[sagetrac-mhampton]

comment:1

This looks great. I looked into TOPCOM briefly but because of its size and some build issues I gave up thinking about it. I don't have time to review this week, but I will try to take a look at it soon.

-Marshall

[vbraun]

comment:2

Thanks to a contribution by Josh Whitney we can now compute volumes and the secondary polytope.

Still todo: the TOPCOM spkg crashes when checking for coherency/regularity of a triangulation, investigating...

[vbraun]

updated version

[vbraun]

comment:3

Attachment: triangulation.2.py.gz

I fixed the segfaulting regularity check, it works for me now. Updated spkg is here:
http://www.stp.dias.ie/~vbraun/Sage/spkg/TOPCOM-0.16.2.p1.spkg

Also, doctests now all pass in the updated triangulation.py

[vbraun]

updated version

[vbraun]

Attachment: triangulation.3.py.gz

Attachment: triangulation.4.py.gz

Updated patch for timeout issue

[vbraun]

comment:4

The previous version would raise pexpect.TIMEOUT after 30 seconds of computation. The new version will unconditionally wait for the computation to end.

Whoever is interested in using it can now either apply trac_8169_triangulate_using_TOPCOM.patch or manually load the triangulation.py code as before.

[sagetrac-mhampton]

comment:5

I get the following error when trying to install the spkg on a mac (10.5.8):

config.status: executing libtool commands
CDPATH="${ZSH_VERSION+.}:" && cd . && /bin/sh /Users/mh/sagestuff/sage-4-x/spkg/build/TOPCOM-0.16.2.p1/src/missing --run aclocal-1.11 -I m4
/Users/mh/sagestuff/sage-4-x/spkg/build/TOPCOM-0.16.2.p1/src/missing: line 52: aclocal-1.11: command not found
WARNING: `aclocal-1.11' is missing on your system.  You should only need it if
         you modified `acinclude.m4' or `configure.ac'.  You might want
         to install the `Automake' and `Perl' packages.  Grab them from
         any GNU archive site.
 cd . && /bin/sh /Users/mh/sagestuff/sage-4-x/spkg/build/TOPCOM-0.16.2.p1/src/missing --run automake-1.11 --gnu
/Users/mh/sagestuff/sage-4-x/spkg/build/TOPCOM-0.16.2.p1/src/missing: line 52: automake-1.11: command not found
WARNING: `automake-1.11' is missing on your system.  You should only need it if
         you modified `Makefile.am', `acinclude.m4' or `configure.ac'.
         You might want to install the `Automake' and `Perl' packages.
         Grab them from any GNU archive site.
CDPATH="${ZSH_VERSION+.}:" && cd . && /bin/sh /Users/mh/sagestuff/sage-4-x/spkg/build/TOPCOM-0.16.2.p1/src/missing --run autoconf
aclocal.m4:20: warning: this file was generated for autoconf 2.63.
You have another version of autoconf.  It may work, but is not guaranteed to.
If you have problems, you may need to regenerate the build system entirely.
To do so, use the procedure documented by the package, typically `autoreconf'.
/usr/bin/gm4:aclocal.m4:953: cannot open `m4/ltoptions.m4': No such file or directory
autom4te: /usr/bin/gm4 failed with exit status: 1
make: *** [configure] Error 1
Error building TOPCOM.

[vbraun]

comment:6

The patches/autogenerated/m4 directory had symlinks to /usr instead of copies, this probably caused the build failure on OSX. I guess all previous users had automake-1.11 already... I've updated the spkg, can you try the updated spkg at http://www.stp.dias.ie/~vbraun/Sage/spkg/TOPCOM-0.16.2.p2.spkg

[sagetrac-mhampton]

comment:7

Great! That fixed it. Patch applies fine too (to sage-4.5.2).

I get the following coverage issues, which I would be happy to work on if you don't mind:

SCORE devel/sage-p1/sage/geometry//triangulation.py: 66% (14 of 21)

Missing documentation:
	 * __len__(self):
	 * _TOPCOM_points(self):
	 * liststring(container, conversion=str):


Missing doctests:
	 * __iter__(self):
	 * __getitem__(self, i):
	 * __init__(self, points, projective=False):
	 * _repr_(self):


Possibly wrong (function name doesn't occur in doctests):
	 * _render_2d(triangulation, **kwds):
	 * _render_3d(triangulation, **kwds):
	 * _repr_(self):

[vbraun]

comment:8

Feel free to make changes! I'm right now working on other tickets.

[sagetrac-mhampton]

comment:9

I'm getting lots of doctest failures; I think most of them are because points2placingtriang doesn't work:

(sage subshell) thorn:bin mh$ ./points2placingtriang
Bus error

I didn't see any errors relating to this during compilation; not sure what is going on.

[sagetrac-drkirkby]

comment:10

A few comments.

• There appears to be no code for 64-bit builds on systems which don't default to 64-bit, but want it. Take a look at spkg-install of the latest GSL library for an example how to do it.
• There's no spkg-check file. It is possible to add one? I note you delete the examples, but often those can be used in tests of the package.
• You appear to copy over configure.ac, but no configure script. Is that intentional? Whilst I agree configure.ac is the preferred usage over configure.in, I'm not sure its actually worth patching that. I think the patch will cause more confusion. If you have actually patched the file, then sure, call it configure.ac. But in that case the configure script will need to be updated too.
• Since we don't ship GMP, I think the dependencies should list MPIR rather than GMP, or at least have a note like "MPIR (used in Sage instead of GMP)"

[vbraun]

comment:11

I'll try to add the 64-bit stuff and a spkg-check. The examples are huge (the upstream distribution is 22M gzipped), but we probably should keep some for the check.

Since the intention is to eventually move the changes upstream I would prefer to move the deprecated configure.in to configure.ac. We do copy patches/autogenerated/configure over the configure script.

As for the bus error, I don't have a OSX machine to test on. But running points2placingtriangs in gdb and producing a stack trace would probably help.

[sagetrac-drkirkby]

comment:12

Replying to @vbraun:

I'll try to add the 64-bit stuff and a spkg-check. The examples are huge (the upstream distribution is 22M gzipped), but we probably should keep some for the check.

I think we should keep them all for the check myself if they can be used in a check. The problem with the doc tests is that they test so little really in most cases.

Since the intention is to eventually move the changes upstream I would prefer to move the deprecated configure.in to configure.ac. We do copy patches/autogenerated/configure over the configure script.

I must have missed that.

As for the bus error, I don't have a OSX machine to test on. But running points2placingtriangs in gdb and producing a stack trace would probably help.

William will give you access to bsd.math I expect. That runs OS X.

[novoselt]

Author: Volker Braun

[novoselt]

comment:15

I do not plan to review this ticket since it involves a package, but I'll allow myself some critical remarks anyway ;-)

1. Module level description is probably not what it was supposed to be ("all vertices of points" does not quite make sense).
2. It would be nice to explain what's the point of using projective coordinates even when the input is affine.
3. I think it is counter-intuitive that iterating over a point configuration deals with projective coordinates and over its points - affine ones. If the default input is affine, I think that default iterating also should be over affine version with points(projective=True) returning projective coordinates.
4. I personally don't like getting generators as output of methods like points and people less familiar with Python find it quite confusing. So I think it would be better to return a tuple (or a list, if it is not cached) and obtain a generator either using something like point_generator() method or by passing an optional argument like points(generator=True). I understand that generators are more efficient, but when efficiency is an issue users should be willing to work a little harder to get them, while for interactive work and new users tuples and lists are more convenient.
5. I like the interface to restricting type of triangulations, but it would be nice for each restricting function to have a precise definition of the corresponding triangulation type.

P.S. My previous attempts to install and use TOPCOM didn't succeed, but with Volker's package installation was completely painless. So I hope that it will make its way into Sage in the near future!

[vbraun]

comment:16

4. I think thats fine with points, but triangulations should default to a generator. Almost always there will be a lot of them and we should train the user to not create an unpacked list of them all :-)

Other TODO's:

6. If the point configuration is not full-dimensional TOPCOM will refuse to work. We should keep an internal auxiliary copy of the point configuration on the spanned hyperplane.

7. Implement the basic edge traversal algorithm on the secondary polytope without resorting to TOPCOM, hence making TOPCOM optional :-) This would really help in getting the triangulation code into Sage, I think.

[novoselt]

comment:17

4. Good point, let triangulations be implemented as a generator. Looking at a list of triangulations is not enlightening anyway (in their default repr-output, that is).

   7. In what sense it will make TOPCOM optional? If you already have both the point configuration and its secondary polytope?

[sagetrac-mhampton]

comment:18

I will post a patch improving the coverage sometime today (US Central time).

I am wondering what the point of the function "liststring" is in the _TOPCOM_points method. Seems like overkill to make this function given the very limited way its used.

I still haven't fixed the build on OS X; on the TOPCOM page it says "The current version compiles successfully under Darwin gcc-4.0 and gcc-4.2 if you choose the -m32 or -m64 architecture manually for all libraries." - which maybe means that we need to add such flags somewhere. I am not good with build issues though.

[sagetrac-mhampton]

comment:19

I think this is a bug in the secondary polytope code, maybe from the optional argument reduce_dimension not being set correctly in the LatticePolytope call.

c = polytopes.n_cube(3)
p = PointConfiguration(c.vertices())
p.secondary_polytope()

...this results in:

RuntimeError: Error executing "poly.x -fv" for a polytope sequence!
Output:
poly.x: Vertex.c:613: Finish_Find_Equations: Assertion `_V->nv<64' failed.
Aborted

A similar command with an octahedron instead of a cube works fine.

[sagetrac-mhampton]

comment:20

Oops, I don't think my initial guess about the above problem was correct, since the octahedron secondary polytope is also in a larger ambient dimension. Would it be OK to switch the secondary polytope to a Polyhedron instead of a lattice polytope?

[vbraun]

comment:31

The warnings are ok except for the "cannot open m4/ltoptions.m4"; This looks like you have the old version where I had not correctly packaged the m4/ directory. The current TOPCOM spkg should be 766185 bytes long. Can you double check that?

[sagetrac-mhampton]

comment:32

OK, sorry about that. I had some older versions lying around and mistakenly installed one of those. The new one seems to build fine, but after installing 9918 it doesn't seem to work. The first doctest failure looks like this:

sage -t  "devel/sage-t2/sage/geometry/triangulation/base.pyx"
**********************************************************************
File "/Users/mh/sagestuff/sage-4-x/devel/sage-t2/sage/geometry/triangulation/base.pyx", line 259:
    sage: p = PointConfiguration([[0, 1], [0, 0], [1, 0]])   # indirect doctest
Exception raised:
    Traceback (most recent call last):
      File "/Users/mh/sagestuff/sage-4-x/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/Users/mh/sagestuff/sage-4-x/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/Users/mh/sagestuff/sage-4-x/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_12[2]>", line 1, in <module>
        p = PointConfiguration([[Integer(0), Integer(1)], [Integer(0), Integer(0)], [Integer(1), Integer(0)]])   # indirect doctest###line 259:
    sage: p = PointConfiguration([[0, 1], [0, 0], [1, 0]])   # indirect doctest
      File "/Users/mh/sagestuff/sage-4-x/local/lib/python/site-packages/sage/misc/classcall_metaclass.py", line 258, in __call__
        return cls.__classcall__(cls, *args, **options)
      File "/Users/mh/sagestuff/sage-4-x/local/lib/python/site-packages/sage/geometry/triangulation/point_configuration.py", line 759, in __classcall__
        .__classcall__(cls, points, connected, fine, regular, star)
      File "/Users/mh/sagestuff/sage-4-x/local/lib/python/site-packages/sage/misc/cachefunc.py", line 115, in __call__
        w = self.f(*args, **kwds)
      File "/Users/mh/sagestuff/sage-4-x/local/lib/python/site-packages/sage/structure/unique_representation.py", line 449, in __classcall__
        instance = type.__call__(cls, *args, **options)
      File "/Users/mh/sagestuff/sage-4-x/local/lib/python/site-packages/sage/geometry/triangulation/point_configuration.py", line 793, in __init__
        self.set_engine()
      File "/Users/mh/sagestuff/sage-4-x/local/lib/python/site-packages/sage/geometry/triangulation/point_configuration.py", line 821, in set_engine
        self._use_TOPCOM = (engine=='TOPCOM') or (engine=='auto' and PointConfiguration._have_TOPCOM())
      File "/Users/mh/sagestuff/sage-4-x/local/lib/python/site-packages/sage/geometry/triangulation/point_configuration.py", line 730, in _have_TOPCOM
        except ExceptionPexpect:
    NameError: global name 'ExceptionPexpect' is not defined
**********************************************************************

[sagetrac-mhampton]

comment:33

I tried installing the patch for this ticket but it seems to conflict with the one at 9918. Are these out of sync now? Sorry for my confusion.

[sagetrac-mhampton]

comment:34

I tried directly running points2facets from $SAGE_LOCAL/bin and got this:

sage-4-x: local/bin/points2facets 
dyld: Library not loaded: /Users/mh/sagestuff/sage-4.6.alpha0/local/lib/libgmpxx.3.dylib
  Referenced from: /Users/mh/sagestuff/sage-4-x/local/bin/points2facets
  Reason: image not found
Trace/BPT trap

I had renamed my sage folder from "sage-4.6.alpha0" to "sage-4-x" after upgrading to 4.6.alpha1, and apparently that is causing some problems. So I'll try this again with a cleaner 4.6.alpha1 but that will take me a while.

[vbraun]

comment:35

Thanks for testing!

The precise version of the sage<->TOPCOM interface in #9918 should not matter. Of course you need some version, or there is no interface.

In case anyone else wants to give it a try: Since TOPCOM compiled correctly it should work.

[sagetrac-mhampton]

comment:36

To be more precise in my question: should I ignore the patch https://github.com/sagemath/sage-prod/files/10647958/trac_8169_triangulate_using_TOPCOM.patch.gz if I install the patch from #9918?

[vbraun]

comment:37

Either patch should work should work for testing the TOPCOM spkg. You can't install both of them as they definitely conflict. If you have a choice, I would recommend using the newer one at #9918.

[sagetrac-mhampton]

comment:38

I started with sage-4.6.alpha1 compiled from source on OS X 10.5. After cloning I installed the TOPCOM package and the patch from 9918. Everything seemed to compile OK with TOPCOM.

If I try to run one of the TOPCOM programs in $SAGE_ROOT/local/bin, I get a "bus error". If I do "sage -sh" and try again, it seems to work. But if I test geometry/triangulation/base.pyx or triangulation/point_configuration.py, everything fails. So I think there is some sort of linking issue here.

[vbraun]

comment:39

That sounds strange; can you post the output of otool -L points2alltriangs before running sage -sh (when you get the bus error) and gcc --version?

[sagetrac-mhampton]

comment:40

OK, here it is:

bin: otool -L points2alltriangs
points2alltriangs:
	/Users/mh/sagestuff/sage-4-x/local/lib/libcddgmp.0.dylib (compatibility version 1.0.0, current version 1.0.0)
	/Users/mh/sagestuff/sage-4-x/local/lib/libgmpxx.3.dylib (compatibility version 5.0.0, current version 5.6.0)
	/Users/mh/sagestuff/sage-4-x/local/lib/libgmp.3.dylib (compatibility version 8.0.0, current version 8.6.0)
	/Users/mh/sagestuff/sage-4-x/local/lib/libTOPCOM.0.dylib (compatibility version 1.0.0, current version 1.0.0)
	/Users/mh/sagestuff/sage-4-x/local/lib/libCHECKREG.0.dylib (compatibility version 1.0.0, current version 1.0.0)
	/usr/lib/libstdc++.6.dylib (compatibility version 7.0.0, current version 7.4.0)
	/usr/lib/libgcc_s.1.dylib (compatibility version 1.0.0, current version 1.0.0)
	/usr/lib/libSystem.B.dylib (compatibility version 1.0.0, current version 111.1.5)

bin: gcc --version
i686-apple-darwin9-gcc-4.0.1 (GCC) 4.0.1 (Apple Inc. build 5465)
Copyright (C) 2005 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

[vbraun]

comment:41

Sounds like it should work? Is this on bsd.math? Trying to debug this via trac is painfull... Maybe you can post a stack backtrace from gdb?

[sagetrac-mhampton]

comment:44

This works for me now on OS X 10.5. Works for OS X 10.6 and linux, so I think this is OK for an optional spkg.

[novoselt]

Reviewer: Marshall Hampton