TSP Solvers#

Traveling Salesman Problem solvers used internally by the cycle resolution step to find circular orderings of taxon sets around reticulation cycles.

Both functions return a CircularOrdering over the labels of the input DistanceMatrix.

TSP solvers used by the cycle resolution algorithm.

Implements:

optimal_tsp_tour — Held-Karp DP, O(n^2 * 2^n), Numba-accelerated
approximate_tsp_tour — networkx heuristics (simulated annealing / greedy / Christofides)

physquirrel.algorithms.tsp.approximate_tsp_tour(distance_matrix: DistanceMatrix, method: str = 'simulated_annealing') → CircularOrdering#

Find an approximate TSP tour using a networkx heuristic.

Parameters:

distance_matrix (DistanceMatrix)
method (str) – One of 'simulated_annealing' (default), 'greedy', or 'christofides'.

Returns:

Canonical circular ordering of all labels.

Return type:

CircularOrdering

Raises:

PhyloZooValueError – If method is not one of the supported options.

physquirrel.algorithms.tsp.optimal_tsp_tour(distance_matrix: DistanceMatrix) → CircularOrdering#

Solve TSP to optimality using the Held-Karp dynamic programming algorithm.

Time complexity O(n^2 * 2^n) — practical for n ≤ ~20.