Show HN: Python 3 TSP solver based on LKH (cross platform)

by pyentropy • 7 years ago

57 12 7 years ago

enriquto3• 7 years ago

I love the "without dependencies" idea. Notice, however, that the algorithm is implemented in C, and it requires (somewhat strangely) cmake to build. I say strangely, because being a C source without dependencies itself, it could be compiled just as easily without cmake.

derefr2• 7 years ago

cmake isn't just a make tool; it also serves as a replacement for autotools in the projects that use it. I would presume that that's its purpose here—detecting system libraries and syscall availability and such.

enriquto3• 7 years ago

my point is that in this case there are no libraries to be "detected" at all. This is just vanilla ansi C without any requirement besides the standard C library. This can be compiled anywhere without need to "detect" anything.

EDIT: I put "detect" in quotes, because I find the whole concept of detecting libraries ridiculous in a context of a C program. Either a library XYZ is installed on my system, in which case the compiler finds it with the -lXYZ flag, or it isn't. If it is not installed, I expect the compilation to fail. I do not expect the build system to look in my hard disk by itself and try to find some files that look like the XYZ library; that would be extremely untoward.

pyentropy2• 7 years ago

The TSP solver is vanilla C and the Python extension that wraps it only needs "Python.h".

I use scikit-build which is a setup.py alternative and builds and bundles together the solver and the extension. The build system makes a binary version for most platforms.

rav2• 7 years ago

Looks like _elkai.c implements a CPython-API function "ElkSolve" that parses the Python lists into a C array, calls a pure-C function "InvokeSolver", and puts the result of "InvokeSolver" into a Python list.

It should be easy to implement "ElkSolve" in pure Python using ctypes to call a pure-C library that exposes the "InvokeSolver" function. That would make it possible to distribute a single Python wheel that works on both Python 2 and 3 and works across all minor versions of Python 3.

Currently, elkai works on 3.5, 3.6 and 3.7, but the build system requires a separate build artifact on each, and when Python 3.8 comes out, elkai won't be available until the author builds it for 3.8. With a pure-C library, elkai would be immediately available in new Python versions.

pyentropy2• 7 years ago

Correct, but you will have to find/build the shared library. Also, as soon as the build systems support 3.8, I will add 3.8 wheels.

I tried to support all 3.xx platforms that numpy supports: https://pypi.org/project/numpy/#files

rav2• 7 years ago

I've implemented my suggestion and sent you a pull request: https://github.com/pyEntropy/elkai/pull/3

The resulting wheel contains the shared library (using milksnake), so there's no need for the user to install that separately.

Let me know what you think. If you're unhappy about adding Python 2 support to your library, you can make 'runs' a keyword-only argument to solve_int_matrix ;-)

WoodenChair• 7 years ago

I would think "without dependencies" would mean that this was an original implementation of an algorithm. In fact, this is a wrapper around a C library that someone else did, so I think the title is misleading.

j88439h84• 7 years ago

Use cffi for calling C.

Show HN: Python 3 TSP solver based on LKH (cross platform)

Related Stories