tsp.hpp File Reference

Traveling Salesman Problem (TSP) approximation algorithms. More...

#include <algorithm>
#include <cassert>
#include <cstddef>
#include <limits>
#include <py2cpp/range.hpp>
#include <py2cpp/set.hpp>
#include <set>
#include <tuple>
#include <vector>
#include <xnetwork/classes/graph.hpp>

Include dependency graph for tsp.hpp:

Go to the source code of this file.

Namespaces
namespace	detail

Functions
template<typename Node , typename WeightFunc >
double	calculate_total_distance (const std::vector< Node > &path, WeightFunc &&weight)
	Compute the total length of a Hamiltonian path/cycle.
template<typename Node , typename WeightFunc >
auto	detail::prim_mst (size_t n, WeightFunc &&weight) -> std::vector< std::pair< Node, Node > >
	Prim's MST for dense (complete) graphs - O(n^2).
template<typename Node >
auto	detail::find_odd_degree_nodes (const std::vector< std::pair< Node, Node > > &mst_edges, size_t n) -> std::vector< Node >
	Collect vertices with odd degree in the MST.
template<typename Node , typename WeightFunc >
auto	detail::greedy_min_weight_matching (const std::vector< Node > &odd_nodes, WeightFunc &&weight) -> std::vector< std::pair< Node, Node > >
	Greedy minimum-weight perfect matching - O(k^2 log k).
template<typename Node >
auto	detail::build_multigraph (size_t n, const std::vector< std::pair< Node, Node > > &mst_edges, const std::vector< std::pair< Node, Node > > &matching_edges) -> std::vector< std::multiset< Node > >
	Build a multigraph adjacency list (MST + matching).
template<typename Node >
auto	detail::hierholzer (std::vector< std::multiset< Node > > adj, Node start) -> std::vector< std::pair< Node, Node > >
	Hierholzer's algorithm - find an Eulerian circuit.
template<typename Node >
auto	detail::shortcut_eulerian (const std::vector< std::pair< Node, Node > > &eulerian_circuit) -> std::vector< Node >
	Convert an Eulerian circuit to a Hamiltonian cycle by skipping repeated vertices (shortcut).
template<typename Graph , typename WeightFunc >
auto	christofides_tsp (const Graph &G, WeightFunc &&weight) -> std::vector< typename Graph::node_t >
	Solve Metric TSP using the Christofides approximation algorithm.
template<typename Graph , typename WeightFunc >
auto	two_opt (std::vector< typename Graph::node_t > path, const Graph &G, WeightFunc &&weight) -> std::vector< typename Graph::node_t >
	Refine a TSP tour using 2-opt neighbourhood search.
template<typename Graph , typename WeightFunc >
auto	solve_christofides_2opt_tsp (const Graph &G, WeightFunc &&weight) -> std::vector< typename Graph::node_t >
	Solve Metric TSP using Christofides followed by 2-Opt refinement.

Detailed Description

Traveling Salesman Problem (TSP) approximation algorithms.

Implements the Christofides algorithm (3/2-approximation for Metric TSP) and the 2-Opt local search heuristic for tour refinement.

All functions accept a callable weight(u, v) -> double for edge weights, making them agnostic to the underlying graph representation.

Algorithm summary (Christofides, 1976):

1. Compute a Minimum Spanning Tree (MST).
2. Find odd-degree vertices in the MST.
3. Compute a Minimum Weight Perfect Matching on odd vertices.
4. Superimpose MST and matching -> an Eulerian multigraph.
5. Find an Eulerian circuit (Hierholzer).
6. Shortcut repeated vertices -> Hamiltonian cycle.

Combining with 2-Opt refinement typically yields near-optimal tours for moderate-size metric instances.

Function Documentation

calculate_total_distance()

template<typename Node , typename WeightFunc >

double calculate_total_distance	(	const std::vector< Node > &	path,
		WeightFunc &&	weight
	)

Compute the total length of a Hamiltonian path/cycle.

Template Parameters

Node	node type (must be usable as an index)
WeightFunc	callable double(Node, Node)

Parameters

path	sequence of nodes (last == first for a cycle)
weight	edge-weight function

Returns

double sum of edge weights along the path

christofides_tsp()

template<typename Graph , typename WeightFunc >

auto christofides_tsp	(	const Graph &	G,
		WeightFunc &&	weight
	)		-> std::vector<typename Graph::node_t>

Solve Metric TSP using the Christofides approximation algorithm.

Template Parameters

Graph	graph type with node_t and number_of_nodes()
WeightFunc	callable double(node_t, node_t)

Parameters

G	input graph (only number_of_nodes() is used)
weight	edge-weight function (must satisfy triangle inequality)

Returns

Hamiltonian cycle [v0, v1, ..., vn, v0]

solve_christofides_2opt_tsp()

template<typename Graph , typename WeightFunc >

auto solve_christofides_2opt_tsp	(	const Graph &	G,
		WeightFunc &&	weight
	)		-> std::vector<typename Graph::node_t>

Solve Metric TSP using Christofides followed by 2-Opt refinement.

This is the recommended entry point. The 2-Opt post-processing typically improves the Christofides tour significantly, often yielding results very close to optimal for moderate-size metric instances.

Template Parameters

Graph	graph type
WeightFunc	callable double(node_t, node_t)

Parameters

G	input graph
weight	metric edge-weight function

Returns

refined Hamiltonian cycle [v0, v1, ..., vn, v0]

two_opt()

template<typename Graph , typename WeightFunc >

auto two_opt	(	std::vector< typename Graph::node_t >	path,
		const Graph &	G,
		WeightFunc &&	weight
	)		-> std::vector<typename Graph::node_t>

Refine a TSP tour using 2-opt neighbourhood search.

Replaces edge pairs (i-1,i) & (j,j+1) with (i-1,j) & (i,j+1) by reversing segment [i, j] whenever this reduces total length. Repeats until a local optimum is reached.

\[ \Delta = w(i-1,j) + w(i,j+1) - w(i-1,i) - w(j,j+1) \]

Template Parameters

Graph	graph type
WeightFunc	callable double(node_t, node_t)

Parameters

path	initial tour (last == first)
G	graph (unused except for node type deduction)
weight	edge-weight function

Returns

locally optimal tour