shmulvad / fast-tsp

A fast TSP solver with Python bindings

👋 Hi, I'm Søren - aka shmulvad

About Me

• 🤖 Working as a Data Scientist at Singapore Pools
• 📚 Master of Computing from NUS, BSc from @diku-dk
• 🧠 My field of specialization is artificial intelligence
• 👨‍🏫 I enjoy sharing my knowledge with others
• 👨‍💻 I love to build my own stuff

Connect with me:

---

📕 Latest Blog Posts:

• Why Did I Start This Blog

🤖 Coding stats:

NOTE: Doesn't track coding at work or work done in environments such as Jupyter Notebooks.

I'm a Night 🦉

🌞 Morning                475 commits         ██░░░░░░░░░░░░░░░░░░░░░░░   08.43 % 
🌆 Daytime                1538 commits        ███████░░░░░░░░░░░░░░░░░░   27.30 % 
🌃 Evening                2200 commits        ██████████░░░░░░░░░░░░░░░   39.06 % 
🌙 Night                  1420 commits        ██████░░░░░░░░░░░░░░░░░░░   25.21 % 

📊 This Week I Spent My Time On

💬 Programming Languages: 
Python                   4 hrs 7 mins        ███████████░░░░░░░░░░░░░░   43.70 % 
Other                    2 hrs 34 mins       ███████░░░░░░░░░░░░░░░░░░   27.35 % 
YAML                     30 mins             █░░░░░░░░░░░░░░░░░░░░░░░░   05.45 % 
JavaScript               24 mins             █░░░░░░░░░░░░░░░░░░░░░░░░   04.32 % 
TypeScript               22 mins             █░░░░░░░░░░░░░░░░░░░░░░░░   04.01 % 

🔥 Editors: 
VS Code                  6 hrs 52 mins       ██████████████████░░░░░░░   72.93 % 
Zsh                      2 hrs 32 mins       ███████░░░░░░░░░░░░░░░░░░   27.05 % 
Sublime Text             0 secs              ░░░░░░░░░░░░░░░░░░░░░░░░░   00.02 % 

🐱‍💻 Projects: 
km24-core                8 hrs 33 mins       ███████████████████████░░   90.83 % 
company-scrapers         27 mins             █░░░░░░░░░░░░░░░░░░░░░░░░   04.89 % 
dmarc-analyse            12 mins             █░░░░░░░░░░░░░░░░░░░░░░░░   02.15 % 
faktanet                 11 mins             ░░░░░░░░░░░░░░░░░░░░░░░░░   01.96 % 
overvaagning-admin       0 secs              ░░░░░░░░░░░░░░░░░░░░░░░░░   00.15 % 

Last Updated on 16/07/2024 18:45:16 UTC

😇 My GitHub stats:

fast-tsp's Issues

Include MIT license for reverse_tour

As highlighted in estan/tsp#3 (comment), there is an issue with the reverse_tour code which is copied from https://github.com/estan/tsp:

fast-tsp/src/tsp.h

Lines 198 to 212 in 5f76216

	// Copied reverse method from: https://github.com/estan/tsp/blob/master/tsp.cpp
	void reverse_tour(uint_fast16_t n, Tour& tour, uint_fast16_t start, uint_fast16_t end, uint_fast16_t* position) {
	uint_fast16_t num_swaps = (((start <= end ? end - start : (end + n) - start) + 1) / 2);
	uint_fast16_t i = start;
	uint_fast16_t j = end;
	while (num_swaps--) {
	std::swap(tour[i], tour[j]);
	position[tour[i]] = i;
	position[tour[j]] = j;
	i = (i + 1) % n;
	j = ((j + n) - 1) % n;
	}
	}

estan/tsp uses a MIT license, so the copyright and permission notice needs to be included somewhere.

Code breaks for ints larger than 16-bits

I am attempting to use this module to find a tsp traverse for a set of float data. Since the module only accepts lists of lists of ints, I converted my data to this form and multiplied all my data by a larger scalar to help preserve some of the precision before casting to an int. I was getting crashes any time I multiplied by too large a number, but smaller scalars worked fine.

So I manually narrowed down the number which caused a crash and found it to be anything >= 65536. This is the smallest unsigned int number that cannot be represented by 16-bits. It also appears to crash on any negative number. Leading me to the conclusion that this module does not work for signed ints or int values larger than 16 bits, which is a very annoying restriction considering it also must use ints and cannot read numpy arrays.

Building wheel error

When trying to pip install as instructed, I get the following building wheel error:

\src\tsp.h(216): error C2131: expression did not evaluate to a constant
\src\tsp.h(216): note: failure was caused by a read of a variable outside its lifetime
\src\tsp.h(216): note: see usage of 'n'
\src\tsp.h(218): error C3863: array type 'bool [n]' is not assignable
\src\tsp.h(223): error C3863: array type 'bool [n]' is not assignable
\src\tsp.h(234): error C3863: array type 'bool [n]' is not assignable

OS: Windows 10 64bit
Python: 3.8
Visual Studio 17 2022 x64 v143
fast-tsp: 0.1.0

Full log:
fast-tsp build wheel error.txt

License is listed as MIT on PyPI

As highlighted by @JaniKallankari in estan/tsp#3, there is an inconsistency between the actual license used by the software and the license noted on PyPI.

This should be fixed in the setup.py file so it is consistently BSD.