Metadata-Version: 2.4
Name: tourforge
Version: 0.1.0
Summary: Exact brute-force traveling salesperson solvers in pure Python and Cython/C++
Author: Garvit Choudhary
License-Expression: MIT
Keywords: traveling-salesperson,tsp,cython,cpp,benchmark,combinatorial-optimization
Classifier: Development Status :: 3 - Alpha
Classifier: Intended Audience :: Developers
Classifier: Intended Audience :: Education
Classifier: Intended Audience :: Science/Research
Classifier: Operating System :: Microsoft :: Windows
Classifier: Programming Language :: C++
Classifier: Programming Language :: Cython
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: Python :: 3.11
Classifier: Topic :: Education
Classifier: Topic :: Scientific/Engineering :: Mathematics
Classifier: Typing :: Typed
Requires-Python: >=3.11
Description-Content-Type: text/markdown
License-File: LICENSE
Provides-Extra: benchmark
Requires-Dist: matplotlib>=3.7; extra == "benchmark"
Provides-Extra: dev
Requires-Dist: build>=1.2; extra == "dev"
Requires-Dist: Cython>=3.0.10; extra == "dev"
Requires-Dist: matplotlib>=3.7; extra == "dev"
Requires-Dist: mypy>=1.10; extra == "dev"
Requires-Dist: pytest>=8; extra == "dev"
Requires-Dist: ruff>=0.6; extra == "dev"
Requires-Dist: twine>=5; extra == "dev"
Dynamic: license-file

# 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](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:

```bash
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:

```bash
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

```python
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`.

```python
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:

```text
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

```mermaid
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&lt;int&gt;"]
    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

```bash
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

```bash
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:

```bash
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`.

![Median end-to-end execution time for both solvers](docs/images/benchmark-execution-time.png)

![Median speedup of the native solver](docs/images/benchmark-speedup.png)

![Run-to-run variability with individual samples and median markers](docs/images/benchmark-variability.png)

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](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](CONTRIBUTING.md). Bug reports should include the Python
version, compiler, platform, matrix, and the expected versus actual result.

## License

MIT. See [LICENSE](LICENSE).
