TourForge

TourForge is a small, exact Traveling Salesperson Problem (TSP) library with two algorithmically identical solvers: one written in pure Python and one written in C++ and exposed through Cython. It exists to make the boundary between readable Python and native code measurable, reproducible, and easy to inspect.

The project is deliberately narrow. It does not pretend that brute force is a production routing algorithm, and it does not hide validation or conversion costs inside a benchmark that only measures a C++ loop.

Release status: not yet published to PyPI, and no public GitHub repository has been created from this workspace. Repository and package links are omitted until they can be verified. See docs/release.md for the release checklist.

What is included

• A pure-Python solver using itertools.permutations.
• A C++ solver using std::next_permutation.
• A Cython bridge that validates and flattens Python input into std::vector<int>, releases the GIL for the search, and returns a Python integer.
• A stable public API: solve, tsp_python, tsp_native, and validate_distance_matrix.
• Deterministic benchmarks for N=8, N=10, and N=11 with raw CSV data, metadata, charts, and tests that verify both solvers agree before timing.
• A source distribution and a locally built Windows wheel, both checked with Twine.
• CI and release-only trusted-publishing workflow definitions. They are statically reviewed but have not been executed from this workspace.

Installation

From a source checkout:

python -m pip install .

The package has no runtime dependencies. Building from source requires CPython 3.11 or newer and a C++17 compiler:

• Windows: Visual C++ Build Tools is the recommended toolchain. MinGW-w64 with g++ on PATH is also supported by the build script.
• Linux/macOS: GCC, Clang, or the Xcode command-line tools. These builds are not locally verified; the release workflow's CI matrix is the gate.

For development:

python -m pip install -e ".[dev]"

A binary wheel contains the compiled extension. A source distribution does not: pip install on a machine without a wheel must compile the extension locally.

Quick start

from tourforge import solve

distance_matrix = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0],
]

print(solve(distance_matrix))                  # 80, native backend
print(solve(distance_matrix, backend="python"))  # 80, pure Python

The optimal tour is 0 -> 1 -> 3 -> 2 -> 0 with cost 10 + 25 + 30 + 15 = 80.

Input and output contract

• City 0 is the fixed start and end of the tour.
• Every other city is visited exactly once.
• The matrix must be non-empty, square, and contain only integers.
• Supported distances are 0 <= d <= 2_147_483_647 (INT32_MAX). The same limit applies to both backends so their behaviour is equivalent.
• Negative distances, booleans, floats, strings, None, jagged rows, and empty matrices are rejected with TypeError or ValueError.
• A one-city matrix returns 0.
• The diagonal is ignored by the objective. A zero diagonal is conventional, but a non-zero non-negative diagonal is accepted and does not affect the result.
• Rows must be Python sequences. A NumPy array is not a collections.abc.Sequence; convert it with .tolist() first. NumPy integer scalars inside Python lists are accepted through operator.index.
• The return value is a Python int. Native tour costs accumulate in std::int64_t; a guard rejects inputs whose worst-case cost cannot fit in signed 64 bits, although this is unreachable for any matrix small enough to enumerate with distances capped at INT32_MAX.

from tourforge import tsp_native, tsp_python

matrix = ((0, 3, 4), (3, 0, 5), (4, 5, 0))
assert tsp_python(matrix) == tsp_native(matrix) == 12

Algorithm

Fixing the start city removes rotationally equivalent tours. For N cities, the remaining N - 1 cities can be arranged in (N - 1)! ways. Each candidate is a complete cycle, so the objective is:

cost(tour) = d[0][p1] + d[p1][p2] + ... + d[pN-1][0]

The Python solver enumerates itertools.permutations(range(1, N)). The C++ solver keeps a sorted std::vector<int> of the same non-starting indices and walks it with std::next_permutation. Both evaluate exactly the same set of candidate tours and return the minimum cost.

The total running time is O((N - 1)! * N), which is factorial. Native code reduces interpreter and object overhead; it does not change the complexity class. This is an implementation optimisation, not an algorithmic one.

Architecture

flowchart LR
    A["Python list of lists"] --> B["validate_distance_matrix"]
    B --> C["immutable tuple of tuples"]
    C --> D["tsp_python"]
    C --> E["Cython tsp_native"]
    E --> F["flatten to std::vector<int>"]
    F --> G["tourforge::tsp_solve<br/>nogil, std::next_permutation"]
    G --> H["std::int64_t optimum"]
    H --> I["Python int"]
    D --> I

The native call path has four distinct costs:

1. Python-level validation and normalisation.
2. Flattening the tuple rows into a contiguous std::vector<int>.
3. The C++ permutation search, which runs without the GIL.
4. Conversion of the int64_t result to a Python int.

The benchmark measures the complete public call, so all four costs are included. No isolated native-loop timing is presented alongside it, because comparing that number directly with the end-to-end Python number would overstate the benefit of the wrapper.

Files

Path	Purpose
cpp/tsp.h, cpp/tsp.cpp	Native solver declaration and implementation
src/tourforge/_python.py	Pure-Python solver
src/tourforge/_validation.py	Shared input validation and cost-bound guard
src/tourforge/_tsp.pxd	C++ declaration for Cython
src/tourforge/_native.pyx	Python/Cython/C++ bridge
src/tourforge/__init__.py	Public API
benchmark.py	Deterministic benchmark runner
scripts/plot_benchmarks.py	Charts generated from saved results
scripts/validate_benchmark_data.py	Cross-checks charts/report data against raw CSV
tests/	Validation, correctness, parity, overflow, and benchmark tests

Build from source

python -m pip install --upgrade build
python -m build

This produces an sdist and a platform wheel in dist/. The sdist contains the hand-written C++, header, Cython, and build files. The generated src/tourforge/_native.cpp is intentionally excluded from version control and from the sdist because it is rebuilt from _native.pyx during installation.

The Windows build script selects MSVC when it is available. If MSVC is absent and g++ is on PATH, it falls back to MinGW-w64 and statically links the MinGW runtime so the resulting wheel does not require libstdc++-6.dll or libwinpthread-1.dll at import time. TOURFORGE_FORCE_MINGW=1 forces the fallback.

Tests

python -m pytest -q
python -m ruff check .
python -m mypy

The suite covers one-city and two-city inputs, a manually verified four-city optimum, assorted matrices, asymmetric matrices, parity between both solvers, random instances checked against an independent brute-force reference, invalid dimensions and values, booleans and floats, the 32-bit distance limit, 64-bit accumulation, repeated calls, and deterministic benchmark fixtures.

Benchmarks

Run from a source checkout:

python -m pip install -e ".[benchmark]"
python benchmark.py
python scripts/plot_benchmarks.py
python scripts/validate_benchmark_data.py

benchmark.py uses a documented seed (20261029), builds a symmetric matrix with a zero diagonal and distances in [1, 100], and gives the identical matrix to both solvers. It verifies that the two optima agree before accepting any timing. It performs one untimed warm-up call per solver and size, then selects a repeat count targeting roughly 0.25 seconds per independent sample. Each reported per-call time is the elapsed time divided by the number of repeats. Five independent runs are used; the minimum, median, maximum, standard deviation, and relative spread are recorded.

Random generation, warm-up, printing, compilation, and plotting are outside the timed interval. The timer is time.perf_counter, and the measured scope is the public API end to end.

Measured results

Measured on 2026-10-29 on the machine listed below. These are actual results from this workspace, not values copied from the assignment sheet.

N	Candidate tours	Pure Python median	Cython/C++ median	Median speedup
8	5,040	1.953 ms	0.033 ms	58.90x
10	362,880	168.707 ms	1.889 ms	89.32x
11	3,628,800	1,832.206 ms	19.905 ms	92.05x

Environment:

• OS: Windows 11 (build 26300), AMD64.
• CPU: Intel Core 5 210H, 8 cores / 12 logical processors.
• Python: CPython 3.11.9.
• Cython: 3.3.0.
• C++ compiler: MinGW-w64 GCC 16.2.0 (-O3 -std=c++17, static MinGW runtime).
• Timer: time.perf_counter; 5 independent runs; seed 20261029.
• Raw data: benchmark-results/raw-measurements.csv.
• Metadata: benchmark-results/metadata.json.

The speedup grows with N because the native search does more work per Python call. At N=8, validation, conversion, and call overhead are a larger share of the native time. At N=11, the factorial search dominates and the native median is about 92 times lower than the Python median. The result is specific to this machine, this compiler, this input generation method, and this implementation.

See docs/benchmark.md for the full protocol and analysis.

Complexity and limitations

• Brute force remains O((N - 1)! * N). N=12 means 39,916,800 candidate tours; N=15 means over 87 billion. Exact enumeration is not a practical routing solution beyond small instances.
• The library uses an adjacency matrix and an exact search. It does not implement Held-Karp dynamic programming, branch-and-bound, 2-opt, Christofides, or any heuristic. Those are different algorithms with different trade-offs.
• Distances are limited to signed 32-bit integers at the boundary. The native accumulation uses signed 64-bit integers.
• The native path includes Python validation and flattening. For trivially small inputs, those costs can be a meaningful fraction of total latency.
• A source distribution requires a compiler. Only the local Windows/CPython 3.11 artifact has been built and tested in this workspace; the CI definition is prepared but has not been executed here.

When native code is useful

Native code is a good fit when a CPU-bound loop has a stable interface, a large amount of work per call, and a small amount of data crossing the boundary. This TSP exercise is an intentionally extreme example: the search is factorial, so the conversion cost is quickly amortised.

It is often the wrong first move. Normal Python may be fast enough; NumPy may express array-heavy work better; a better algorithm can dominate constant-factor tuning; and I/O, database access, or network latency may be the real bottleneck. Cython does not make arbitrary Python programs faster, and a native extension adds build, packaging, and platform support costs.

Platform and Python support

Evidence in this workspace:

• Built and tested: CPython 3.11.9, Windows 11 build 26300, AMD64, MinGW-w64 GCC 16.2.0, Cython 3.3.0.
• Locally built wheel: cp311-cp311-win_amd64.
• Package metadata declares Python >=3.11 and only the Windows OS classifier. The CI and release workflows target CPython 3.11-3.13 on Ubuntu, Windows, and macOS, but those jobs have not been run in this workspace. Broaden the classifiers only after the matrix has passed.

Contributing

See CONTRIBUTING.md. Bug reports should include the Python version, compiler, platform, matrix, and the expected versus actual result.

License

MIT. See LICENSE.