toposolve

A fast C++ implementation of the Held-Karp algorithm for solving the Traveling Salesman Problem (TSP) for ring-reduce tours, with Python bindings. We solve a specific variant of TSP where the dist(i, j) is calculated as min(max(dist(i, k), dist(k, j)) for k in range(n)).

Installation

pip install toposolve

Usage

from toposolve import TSPSolver

# Create distance matrix
distances = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0]
]

# Create solver instance
solver = TSPSolver()

# Solve TSP
min_distance, path = solver.solve_tsp(distances)

print(f"Minimum distance: {min_distance}")
print(f"Optimal path: {path}")

Requirements

Python 3.6+
C++ compiler supporting C++17
CMake 3.18+

Building from source

git clone https://github.com/Jackmin801/toposolve
cd toposolve
pip install .

Running tests

pip install pytest
pytest tests/

License

MIT License

License
- OSI Approved :: MIT License
Operating System
- OS Independent
Programming Language
- Python :: 3

Metadata

License
- OSI Approved :: MIT License
Operating System
- OS Independent
Programming Language
- Python :: 3

Release files for toposolve 0.1.17

For a detailed explanation of source distributions (sdists) and built distributions (wheels), please see the package formats documentation.

Source distribution (sdist)

Source distribution for toposolve 0.1.17
File	Size	Uploaded
toposolve-0.1.17.tar.gz	5.4 kB	Nov 30, 2024	Details

Built distributions (wheels)

Table of built distributions (wheels) for toposolve 0.1.17
File	Interpreter	ABI	Platform	Reset
toposolve-0.1.17-cp312-cp312-manylinux_2_17_x86_64.manylinux2014_x86_64.whl 95.5 kB Nov 30, 2024	CPython 3.12	CPython 3.12	Linux glibc 2.17+ x86-64	Details
toposolve-0.1.17-cp312-cp312-macosx_11_0_arm64.whl 127.5 kB Nov 30, 2024	CPython 3.12	CPython 3.12	macOS 11.0+ ARM64	Details
toposolve-0.1.17-cp312-cp312-macosx_10_13_x86_64.whl 127.4 kB Nov 30, 2024	CPython 3.12	CPython 3.12	macOS 10.13+ x86-64	Details
toposolve-0.1.17-cp311-cp311-manylinux_2_17_x86_64.manylinux2014_x86_64.whl 96.7 kB Nov 30, 2024	CPython 3.11	CPython 3.11	Linux glibc 2.17+ x86-64	Details
toposolve-0.1.17-cp311-cp311-macosx_11_0_arm64.whl 128.4 kB Nov 30, 2024	CPython 3.11	CPython 3.11	macOS 11.0+ ARM64	Details
toposolve-0.1.17-cp311-cp311-macosx_10_9_x86_64.whl 128.3 kB Nov 30, 2024	CPython 3.11	CPython 3.11	macOS 10.9+ x86-64	Details
toposolve-0.1.17-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl 95.1 kB Nov 30, 2024	CPython 3.10	CPython 3.10	Linux glibc 2.17+ x86-64	Details
toposolve-0.1.17-cp310-cp310-macosx_11_0_arm64.whl 125.5 kB Nov 30, 2024	CPython 3.10	CPython 3.10	macOS 11.0+ ARM64	Details
toposolve-0.1.17-cp310-cp310-macosx_10_9_x86_64.whl 125.5 kB Nov 30, 2024	CPython 3.10	CPython 3.10	macOS 10.9+ x86-64	Details
toposolve-0.1.17-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl 94.9 kB Nov 30, 2024	CPython 3.9	CPython 3.9	Linux glibc 2.17+ x86-64	Details
toposolve-0.1.17-cp39-cp39-macosx_11_0_arm64.whl 125.7 kB Nov 30, 2024	CPython 3.9	CPython 3.9	macOS 11.0+ ARM64	Details
toposolve-0.1.17-cp39-cp39-macosx_10_9_x86_64.whl 125.7 kB Nov 30, 2024	CPython 3.9	CPython 3.9	macOS 10.9+ x86-64	Details
toposolve-0.1.17-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl 94.9 kB Nov 30, 2024	CPython 3.8	CPython 3.8	Linux glibc 2.17+ x86-64	Details
toposolve-0.1.17-cp38-cp38-macosx_11_0_arm64.whl 125.3 kB Nov 30, 2024	CPython 3.8	CPython 3.8	macOS 11.0+ ARM64	Details
toposolve-0.1.17-cp38-cp38-macosx_10_9_x86_64.whl 125.3 kB Nov 30, 2024	CPython 3.8	CPython 3.8	macOS 10.9+ x86-64	Details

Total release size: 1.7 MB

Release files / toposolve-0.1.17.tar.gz

Download URL	toposolve-0.1.17.tar.gz
Size	5.4 kB
Tags	Source
SHA-256 checksum How to use checksums	`539a1301ed36df5e2fbd0d3e1806f2c6cd7840c3527938647a61b0a7b53689f9`
BLAKE2b-256 checksum How to use checksums	`515de24dd0bbbf9f508d9aa11120fdcc7b0e4caf1c1d401359495636470e0431`
Upload date	Nov 30, 2024
Uploaded using Trusted Publishing? What is trusted publishing?	No
Uploaded via	`twine/5.1.1 CPython/3.12.7`

Release files / toposolve-0.1.17-cp312-cp312-manylinux_2_17_x86_64.manylinux2014_x86_64.whl

Download URL	toposolve-0.1.17-cp312-cp312-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Size	95.5 kB
Tags	CPython 3.12 Linux glibc 2.17+ x86-64
SHA-256 checksum How to use checksums	`1b238dadaced7fe98638fcb595596619104724a66ba1205914d0faebb2a2081b`
BLAKE2b-256 checksum How to use checksums	`1e8e0d7b43f5c751490745bd25cf2cf1f1285627749e3ebfd2da131a9bbdac8c`
Upload date	Nov 30, 2024
Uploaded using Trusted Publishing? What is trusted publishing?	No
Uploaded via	`twine/5.1.1 CPython/3.12.7`

Release files / toposolve-0.1.17-cp312-cp312-macosx_11_0_arm64.whl

Download URL	toposolve-0.1.17-cp312-cp312-macosx_11_0_arm64.whl
Size	127.5 kB
Tags	CPython 3.12 macOS 11.0+ ARM64
SHA-256 checksum How to use checksums	`17666bdb0078cddcffc89cb9e7c0f0ce35007597b8a309f7b29c6a39a0fb6d8a`
BLAKE2b-256 checksum How to use checksums	`443ba51dd6d756076853f1a6d18cc20761126b613a28a5ff9e37a113a546477b`
Upload date	Nov 30, 2024
Uploaded using Trusted Publishing? What is trusted publishing?	No
Uploaded via	`twine/5.1.1 CPython/3.12.7`

Release files / toposolve-0.1.17-cp312-cp312-macosx_10_13_x86_64.whl

Download URL	toposolve-0.1.17-cp312-cp312-macosx_10_13_x86_64.whl
Size	127.4 kB
Tags	CPython 3.12 macOS 10.13+ x86-64
SHA-256 checksum How to use checksums	`e158c666e1492832dba077eaea9c4bcd88fbb3f45b8bfde8a8f545d5de8212e2`
BLAKE2b-256 checksum How to use checksums	`701e7028dbd313ba931c086ecb24856566fb34cd159d3bd305cf05fa6b66bb3b`
Upload date	Nov 30, 2024
Uploaded using Trusted Publishing? What is trusted publishing?	No
Uploaded via	`twine/5.1.1 CPython/3.12.7`

Release files / toposolve-0.1.17-cp311-cp311-manylinux_2_17_x86_64.manylinux2014_x86_64.whl

Download URL	toposolve-0.1.17-cp311-cp311-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Size	96.7 kB
Tags	CPython 3.11 Linux glibc 2.17+ x86-64
SHA-256 checksum How to use checksums	`ac94551501ca671d428c7ad435a50da5cd33f832c432c87e676f3ab8310bf19d`
BLAKE2b-256 checksum How to use checksums	`4f3bb6e6c863d06f8cb533068224f954b3b49722ba88cb6a0861fd62aefbc151`
Upload date	Nov 30, 2024
Uploaded using Trusted Publishing? What is trusted publishing?	No
Uploaded via	`twine/5.1.1 CPython/3.12.7`

Release files / toposolve-0.1.17-cp311-cp311-macosx_11_0_arm64.whl

Download URL	toposolve-0.1.17-cp311-cp311-macosx_11_0_arm64.whl
Size	128.4 kB
Tags	CPython 3.11 macOS 11.0+ ARM64
SHA-256 checksum How to use checksums	`baa9a76f54f295d8beb06559bd90c117c9a0c2f84aa4c9c661fb283a7529fd68`
BLAKE2b-256 checksum How to use checksums	`b9ab9e062fe4e58729594eda886ed464e4839232162e1ddbd0e36b5bcb61d664`
Upload date	Nov 30, 2024
Uploaded using Trusted Publishing? What is trusted publishing?	No
Uploaded via	`twine/5.1.1 CPython/3.12.7`

Release files / toposolve-0.1.17-cp311-cp311-macosx_10_9_x86_64.whl

Download URL	toposolve-0.1.17-cp311-cp311-macosx_10_9_x86_64.whl
Size	128.3 kB
Tags	CPython 3.11 macOS 10.9+ x86-64
SHA-256 checksum How to use checksums	`8b13cdf80823dd86dd75bda7f94418b5b093cbb4989a4a6f0956f2595b8a7be1`
BLAKE2b-256 checksum How to use checksums	`58c0854d8b5cc5cb23d99720c28908e5eff587e1ec25c797ceac219bf5f0f3a7`
Upload date	Nov 30, 2024
Uploaded using Trusted Publishing? What is trusted publishing?	No
Uploaded via	`twine/5.1.1 CPython/3.12.7`

Release files / toposolve-0.1.17-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl

Download URL	toposolve-0.1.17-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Size	95.1 kB
Tags	CPython 3.10 Linux glibc 2.17+ x86-64
SHA-256 checksum How to use checksums	`141ba41c36e49ecd2280517031f4ef8c2c131b4fb93b85f38c10fead17974b7f`
BLAKE2b-256 checksum How to use checksums	`6146062d43764ac1cf6fff3edde81295846d6191c43a103550ddf27472da49ca`
Upload date	Nov 30, 2024
Uploaded using Trusted Publishing? What is trusted publishing?	No
Uploaded via	`twine/5.1.1 CPython/3.12.7`

Release files / toposolve-0.1.17-cp310-cp310-macosx_11_0_arm64.whl

Download URL	toposolve-0.1.17-cp310-cp310-macosx_11_0_arm64.whl
Size	125.5 kB
Tags	CPython 3.10 macOS 11.0+ ARM64
SHA-256 checksum How to use checksums	`dda111813910145f97df62e34d30ad38c39df45539f129b57df0e6c51e52902b`
BLAKE2b-256 checksum How to use checksums	`ed4c90f3b00b1f381ead4394cb1a1391b8dcd2a043490b2f77ebf71609e24b91`
Upload date	Nov 30, 2024
Uploaded using Trusted Publishing? What is trusted publishing?	No
Uploaded via	`twine/5.1.1 CPython/3.12.7`

Release files / toposolve-0.1.17-cp310-cp310-macosx_10_9_x86_64.whl

Download URL	toposolve-0.1.17-cp310-cp310-macosx_10_9_x86_64.whl
Size	125.5 kB
Tags	CPython 3.10 macOS 10.9+ x86-64
SHA-256 checksum How to use checksums	`cc1a33e2438c29a29ccac4c957c6ffaf035b239b34f0e369f4665ed255b413c9`
BLAKE2b-256 checksum How to use checksums	`c40291db85f3ab2822377e90357b23783c5a1408cdb7c36f9f94a7d3db6783cc`
Upload date	Nov 30, 2024
Uploaded using Trusted Publishing? What is trusted publishing?	No
Uploaded via	`twine/5.1.1 CPython/3.12.7`

Release files / toposolve-0.1.17-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl

Download URL	toposolve-0.1.17-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Size	94.9 kB
Tags	CPython 3.9 Linux glibc 2.17+ x86-64
SHA-256 checksum How to use checksums	`c23b65a9e88740df59acbf56dea8b86b693e0bf82b42aec8b55daa0328f28c67`
BLAKE2b-256 checksum How to use checksums	`7b3da324220aeb460068b747ba982d380db4d1fe67dfa0d472ee852fe83534ac`
Upload date	Nov 30, 2024
Uploaded using Trusted Publishing? What is trusted publishing?	No
Uploaded via	`twine/5.1.1 CPython/3.12.7`

Release files / toposolve-0.1.17-cp39-cp39-macosx_11_0_arm64.whl

Download URL	toposolve-0.1.17-cp39-cp39-macosx_11_0_arm64.whl
Size	125.7 kB
Tags	CPython 3.9 macOS 11.0+ ARM64
SHA-256 checksum How to use checksums	`777fbebbbe75c3230376bc7bb3db52dedcf49e8a7cf21baa5fe35f2088d9e9af`
BLAKE2b-256 checksum How to use checksums	`23b48670f0a8923b61594008ce85f88facf8509a5d37068a49c6b6085bbfbe29`
Upload date	Nov 30, 2024
Uploaded using Trusted Publishing? What is trusted publishing?	No
Uploaded via	`twine/5.1.1 CPython/3.12.7`

Release files / toposolve-0.1.17-cp39-cp39-macosx_10_9_x86_64.whl

Download URL	toposolve-0.1.17-cp39-cp39-macosx_10_9_x86_64.whl
Size	125.7 kB
Tags	CPython 3.9 macOS 10.9+ x86-64
SHA-256 checksum How to use checksums	`17fb898c83409d07606589ca9db9039d330d7692dc27774d1bc304c7c9588a53`
BLAKE2b-256 checksum How to use checksums	`a1bd7ea8c73f890deaf6470434122f1e38285f2bf9f58c6978a0f97a852aa4db`
Upload date	Nov 30, 2024
Uploaded using Trusted Publishing? What is trusted publishing?	No
Uploaded via	`twine/5.1.1 CPython/3.12.7`

Release files / toposolve-0.1.17-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl

Download URL	toposolve-0.1.17-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Size	94.9 kB
Tags	CPython 3.8 Linux glibc 2.17+ x86-64
SHA-256 checksum How to use checksums	`035f2604dc64387961a01e7292faeeaadd14420bb165c67630c4c39470eb5cf9`
BLAKE2b-256 checksum How to use checksums	`1d676ea9c61fb092a05a215ff217258b9db0984939b6f6ca2a74d68b7b6e9baa`
Upload date	Nov 30, 2024
Uploaded using Trusted Publishing? What is trusted publishing?	No
Uploaded via	`twine/5.1.1 CPython/3.12.7`

Release files / toposolve-0.1.17-cp38-cp38-macosx_11_0_arm64.whl

Download URL	toposolve-0.1.17-cp38-cp38-macosx_11_0_arm64.whl
Size	125.3 kB
Tags	CPython 3.8 macOS 11.0+ ARM64
SHA-256 checksum How to use checksums	`3843d1ac1d900f6f93fee0d5718d83bbf580efe155678873cce55dd8768583f2`
BLAKE2b-256 checksum How to use checksums	`7e53c0911320a5e9cf707bfbbe71a5801f272127d5d3685fae1d534f01171213`
Upload date	Nov 30, 2024
Uploaded using Trusted Publishing? What is trusted publishing?	No
Uploaded via	`twine/5.1.1 CPython/3.12.7`

Release files / toposolve-0.1.17-cp38-cp38-macosx_10_9_x86_64.whl

Download URL	toposolve-0.1.17-cp38-cp38-macosx_10_9_x86_64.whl
Size	125.3 kB
Tags	CPython 3.8 macOS 10.9+ x86-64
SHA-256 checksum How to use checksums	`23c3afd06afe3fd7c8fe5c55a415335474d319f1afb02ba3414ff092ad056aea`
BLAKE2b-256 checksum How to use checksums	`574dd07f77f86315db47f1d69dcfe68b001cfa7bc094f0f2c95a7730723c3454`
Upload date	Nov 30, 2024
Uploaded using Trusted Publishing? What is trusted publishing?	No
Uploaded via	`twine/5.1.1 CPython/3.12.7`