Skip to main content

tsp-fast-solver: High-Performance TSP Solver in Pure Python & C++ (Cython)

Python 3.8+ License: MIT

A high-performance library solving the Traveling Salesperson Problem (TSP) using brute-force search implemented in both Pure Python and Native C++ wrapped with Cython.


📌 Problem Overview & Real-World Context

The Traveling Salesperson Problem (TSP) is an NP-hard problem in combinatorial optimization:

Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?

Because the number of unique tours starting from a fixed origin scales factorially with $(N-1)!$, brute-force exploration in dynamic languages like pure Python rapidly encounters performance bottlenecks.

By offloading the inner combinatorial search loop (std::next_permutation) to compiled C++ and exposing it via a zero-overhead Cython C-extension, we achieve up to ~100x speedups.


🚀 Performance Benchmarks

Benchmarks were performed on random symmetric Euclidean/metric distance matrices using Python's timeit module.

Graph Size (Nodes) Possible Routes $(N-1)!$ Pure Python Time (s) Cython C++ Time (s) Speedup Minimum Tour Cost
N = 8 5,040 0.0034s 0.00005s 71.5x 229
N = 10 362,880 0.3384s 0.0033s 101.7x 191
N = 11 3,628,800 3.8315s 0.0418s 91.6x 268

Key Takeaways

  • N = 8: Cython execution is virtually instantaneous ($< 0.1\text{ ms}$).
  • N = 10: Over $362,000$ permutations evaluated in only $3.3\text{ ms}$ (vs. $338\text{ ms}$ in Python).
  • N = 11: Evaluates over $3.6\text{ million}$ complete candidate tours in just $41.8\text{ ms}$ (under $0.05$ seconds), delivering a massive ~92x to 102x speedup over pure Python.

📂 Project Architecture

CPython/
├── pyproject.toml              # Modern PEP 517/518 build specification
├── setup.py                    # Setuptools build configuration with Cython C++ extension
├── MANIFEST.in                 # Source distribution manifest ensuring all C++ & Cython files are packaged
├── .gitignore                  # Git ignore rules for build artifacts, compiled .pyd/.so, etc.
├── README.md                   # Complete documentation and benchmark analysis
├── WORKFLOW_STEPS.txt          # Detailed step-by-step workflow of work performed
├── benchmark.py                # Benchmarking suite comparing Pure Python vs Cython
├── test_solvers.py             # Unit tests verifying correctness and equivalence across topologies
├── src/
│   ├── python_solver/
│   │   ├── __init__.py
│   │   └── solver.py           # Pure Python implementation (tsp_python) using itertools.permutations
│   ├── cpp/
│   │   ├── tsp.h               # C++ header declaring tsp_solver(const std::vector<int>&, int)
│   │   └── tsp.cpp             # Native C++ solver using std::next_permutation
│   └── cython_wrapper/
│       ├── __init__.py
│       ├── tsp_c.pxd           # Cython declaration bridging C++ header
│       └── tsp_wrapper.pyx     # Cython implementation converting list-of-lists to std::vector<int>
└── tsp_fast_solver/            # Python package entry point
    ├── __init__.py             # Exports tsp_python and tsp_cython
    └── python_solver.py        # Packaged pure Python fallback

🛠️ Installation & Building

1. Requirements

  • Python 3.8 or higher
  • C++11 compliant compiler (GCC/MinGW-w64 on Windows, GCC/Clang on Linux/macOS, or MSVC)
  • Cython, setuptools, and build:
    pip install cython setuptools build twine pytest
    

2. In-place Compilation (Local Development)

To compile the C++ extension locally:

python setup.py build_ext --inplace

3. Build Source Distribution (sdist)

To generate the distribution tarball for PyPI:

python -m build --sdist

The resulting .tar.gz archive will be located in the dist/ directory.


💻 Usage Example

from tsp_fast_solver import tsp_python, tsp_cython

# Define an N x N distance matrix (e.g. 4 cities)
distance_matrix = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0]
]

# 1. Pure Python Solver
py_cost = tsp_python(distance_matrix)
print("Pure Python Minimum Cost:", py_cost)

# 2. Cython C++ Solver
cy_cost = tsp_cython(distance_matrix)
print("Cython C++ Minimum Cost:", cy_cost)

assert py_cost == cy_cost

🧪 Running Tests & Benchmarks

Run Unit Tests

pytest test_solvers.py -v

Run Benchmarks

python benchmark.py

📦 Publishing to GitHub and PyPI

Step 1: Initialize Git and Push to GitHub

git init
git add .
git commit -m "Initial commit: Pure Python and Cython C++ TSP solvers"
git branch -M main
git remote add origin https://github.com/<your-username>/tsp-fast-solver.git
git push -u origin main

Step 2: Published PyPI Package

The library is live globally on PyPI: 🔗 PyPI URL: https://pypi.org/project/tsp-fast-solver-raghav15048/0.1.2/

# Upload distribution archive to PyPI using Twine
python -m twine upload dist/*

Step 3: Verified Installation from PyPI

Anyone can install the package directly from PyPI via pip:

pip install tsp-fast-solver-raghav15048
python -c "import tsp_fast_solver; from tsp_fast_solver import tsp_python, tsp_cython; print('Success! Version:', tsp_fast_solver.__version__)"

📄 License

This project is licensed under the MIT License.

Metadata

Release files for fastsp 0.1.0

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

Source distribution (sdist)

Source distribution for fastsp 0.1.0
File Size Uploaded Provenance Actions
fastsp-0.1.0.tar.gz 73.6 kB Without provenance Details for fastsp-0.1.0.tar.gz

Built distribution (wheel)

Table of built distributions (wheels) for fastsp 0.1.0
File Interpreter ABI Platform Actions
fastsp-0.1.0-cp312-cp312-win_amd64.whl CPython 3.12 CPython 3.12 Windows x86-64 Details for fastsp-0.1.0-cp312-cp312-win_amd64.whl

Total release size: 170.1 kB

Release files / fastsp-0.1.0.tar.gz

Download URL fastsp-0.1.0.tar.gz
Size 73.6 kB
Tags Source
SHA-256 checksum
How to use checksums
0e792504fb9a968383537c5aea86c5524c82b4d7f196baa2f1b59dc6b25d938e
BLAKE2b-256 checksum
How to use checksums
21658363172b680c42a586e519cd9e915aa8c97cbff76383b1bc748650a44304
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
No
Uploaded via twine/7.0.0 CPython/3.12.1

Release files / fastsp-0.1.0-cp312-cp312-win_amd64.whl

Download URL fastsp-0.1.0-cp312-cp312-win_amd64.whl
Size 96.5 kB
Tags CPython 3.12 Windows x86-64
SHA-256 checksum
How to use checksums
abb49aaeff10fe43d6a7d00cd75c6d7a685665b98324f1d2dfc4e6fc2c146571
BLAKE2b-256 checksum
How to use checksums
2fc58de82c3968236c48d6f609e61f6f455560b782313df2e240102d141bae5b
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
No
Uploaded via twine/7.0.0 CPython/3.12.1

Security for fastsp 0.1.0

Provenance

Provenance describes where a file came from. On PyPI, provenance is shared via attestations, which provide a verifiable record of the build or publishing details. View details, limitations and caveats.

No provenance found

None of the files in this release were uploaded with provenance metadata.

A note on package security

PyPI is a repository for distributing packages, not a service for auditing them. While third-party security researchers and our staff do their best to detect and remove malicious packages, PyPI cannot guarantee the quality, security or suitability of any given package.

To learn more about protecting yourself from malicious actors, visit our package security documentation.

Release history Release notifications | RSS feed

This release

0.1.0 This release

2 release files No provenance

Anthropic, PBC Visionary sponsor Bloomberg Visionary sponsor Hudson River Trading Visionary sponsor Meta Visionary sponsor NVIDIA Visionary sponsor Microsoft Sustainability sponsor Depot Continuous Integration AWS Cloud computing and Security Sponsor Datadog Monitoring Fastly CDN Google Download Analytics Sentry Error logging StatusPage Status page