Skip to main content

A fast C++ implementation of the Held-Karp algorithm for solving TSP

Project description

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

Project details


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

toposolve-0.1.1.tar.gz (5.2 kB view details)

Uploaded Source

Built Distribution

toposolve-0.1.1-cp311-cp311-macosx_13_0_arm64.whl (61.5 kB view details)

Uploaded CPython 3.11 macOS 13.0+ ARM64

File details

Details for the file toposolve-0.1.1.tar.gz.

File metadata

  • Download URL: toposolve-0.1.1.tar.gz
  • Upload date:
  • Size: 5.2 kB
  • Tags: Source
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/5.1.1 CPython/3.11.10

File hashes

Hashes for toposolve-0.1.1.tar.gz
Algorithm Hash digest
SHA256 b23287b7bdbe5704b30f4fd447a05e41a418e3f500837634c212baa8b226e9ed
MD5 2b074431f173201c422a97c11323295c
BLAKE2b-256 b4d8c57f67241f71ff14b20b2e5a7316e6a6eb16fb02010a5c6674f5dc5cb402

See more details on using hashes here.

File details

Details for the file toposolve-0.1.1-cp311-cp311-macosx_13_0_arm64.whl.

File metadata

File hashes

Hashes for toposolve-0.1.1-cp311-cp311-macosx_13_0_arm64.whl
Algorithm Hash digest
SHA256 6b4cefea1ead3bea316422790af49f63fbc91568b8a1a26305e1e9620600ff86
MD5 cf7728a25845e49363bb62f957b1680f
BLAKE2b-256 b115a8861bfc8b5d1d65b49d0078b365e45f857ee44a63b05097839dcc5384aa

See more details on using hashes here.

Supported by

AWS AWS Cloud computing and Security Sponsor Datadog Datadog Monitoring Fastly Fastly CDN Google Google Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Sentry Sentry Error logging StatusPage StatusPage Status page