operations_research::HamiltonianPathSolver< CostType, CostFunction > Class Template Reference

#include <hamiltonian_path.h>

Public Types
typedef uint32_t	Integer
typedef Set< Integer >	NodeSet

Public Member Functions
	HamiltonianPathSolver (CostFunction cost)
	HamiltonianPathSolver (int num_nodes, CostFunction cost)
void	ChangeCostMatrix (CostFunction cost)
	Replaces the cost matrix while avoiding re-allocating memory.
void	ChangeCostMatrix (int num_nodes, CostFunction cost)
CostType	HamiltonianCost (int end_node)
	Returns the cost of the Hamiltonian path from 0 to end_node.
std::vector< int >	HamiltonianPath (int end_node)
	Returns the shortest Hamiltonian path from 0 to end_node.
int	BestHamiltonianPathEndNode ()
void	HamiltonianPath (std::vector< PathNodeIndex > *path)
CostType	TravelingSalesmanCost ()
	Returns the cost of the TSP tour.
std::vector< int >	TravelingSalesmanPath ()
	Returns the TSP tour in the vector pointed to by the argument.
void	TravelingSalesmanPath (std::vector< PathNodeIndex > *path)
bool	IsRobust ()
bool	VerifiesTriangleInequality ()
	Returns true if the cost matrix verifies the triangle inequality.

Detailed Description

template<typename CostType, typename CostFunction>
class operations_research::HamiltonianPathSolver< CostType, CostFunction >

Definition at line 452 of file hamiltonian_path.h.

Member Typedef Documentation

Integer

template<typename CostType , typename CostFunction >

uint32_t operations_research::HamiltonianPathSolver< CostType, CostFunction >::Integer

HamiltonianPathSolver computes a minimum Hamiltonian path starting at node 0 over a graph defined by a cost matrix. The cost function need not be symmetric. When the Hamiltonian path is closed, it's a Hamiltonian cycle, i.e. the algorithm solves the Traveling Salesman Problem. Example: std::vector<std::vector<int>> cost_mat; ... fill in cost matrix HamiltonianPathSolver<int, std::vector<std::vector<int>>> mhp(cost_mat); ///< no computation done printf("%d\n", mhp.TravelingSalesmanCost()); ///< computation done and stored In 2010, 26 was the maximum solvable with 24 Gigs of RAM, and it took several minutes. With this 2014 version of the code, one may go a little higher, but considering the complexity of the algorithm (n*2^n), and that there are very good ways to solve TSP with more than 32 cities, we limit ourselves to 32 cites. This is why we define the type NodeSet to be 32-bit wide.

Todo

(user): remove this limitation by using pruning techniques.

Definition at line 474 of file hamiltonian_path.h.

NodeSet

template<typename CostType , typename CostFunction >

Set<Integer> operations_research::HamiltonianPathSolver< CostType, CostFunction >::NodeSet

Definition at line 475 of file hamiltonian_path.h.

Constructor & Destructor Documentation

HamiltonianPathSolver() [1/2]

template<typename CostType , typename CostFunction >

operations_research::HamiltonianPathSolver< CostType, CostFunction >::HamiltonianPathSolver ( CostFunction cost )

explicit

Definition at line 605 of file hamiltonian_path.h.

HamiltonianPathSolver() [2/2]

template<typename CostType , typename CostFunction >

operations_research::HamiltonianPathSolver< CostType, CostFunction >::HamiltonianPathSolver	(	int	num_nodes,
		CostFunction	cost )

Definition at line 610 of file hamiltonian_path.h.

Member Function Documentation

BestHamiltonianPathEndNode()

template<typename CostType , typename CostFunction >

int operations_research::HamiltonianPathSolver< CostType, CostFunction >::BestHamiltonianPathEndNode

(

)

Returns the end-node that yields the shortest Hamiltonian path of all shortest Hamiltonian path from 0 to end-node (end-node != 0).

Definition at line 830 of file hamiltonian_path.h.

ChangeCostMatrix() [1/2]

template<typename CostType , typename CostFunction >

void operations_research::HamiltonianPathSolver< CostType, CostFunction >::ChangeCostMatrix

(

CostFunction

cost

)

Replaces the cost matrix while avoiding re-allocating memory.

Definition at line 626 of file hamiltonian_path.h.

ChangeCostMatrix() [2/2]

template<typename CostType , typename CostFunction >

void operations_research::HamiltonianPathSolver< CostType, CostFunction >::ChangeCostMatrix	(	int	num_nodes,
		CostFunction	cost )

Definition at line 632 of file hamiltonian_path.h.

HamiltonianCost()

template<typename CostType , typename CostFunction >

CostType operations_research::HamiltonianPathSolver< CostType, CostFunction >::HamiltonianCost

(

int

end_node

)

Returns the cost of the Hamiltonian path from 0 to end_node.

Definition at line 836 of file hamiltonian_path.h.

HamiltonianPath() [1/2]

template<typename CostType , typename CostFunction >

std::vector< int > operations_research::HamiltonianPathSolver< CostType, CostFunction >::HamiltonianPath

(

int

end_node

)

Returns the shortest Hamiltonian path from 0 to end_node.

Definition at line 843 of file hamiltonian_path.h.

HamiltonianPath() [2/2]

template<typename CostType , typename CostFunction >

void operations_research::HamiltonianPathSolver< CostType, CostFunction >::HamiltonianPath

(

std::vector< PathNodeIndex > *

path

)

Deprecated

API. Stores HamiltonianPath(BestHamiltonianPathEndNode()) into *path.

Definition at line 850 of file hamiltonian_path.h.

IsRobust()

template<typename CostType , typename CostFunction >

bool operations_research::HamiltonianPathSolver< CostType, CostFunction >::IsRobust

(

)

Returns true if there won't be precision issues. This is always true for integers, but not for floating-point types.

We compute the min and max for the cost matrix.

We determine if the range of the cost matrix is going to make the algorithm not robust because of precision issues.

Definition at line 784 of file hamiltonian_path.h.

TravelingSalesmanCost()

template<typename CostType , typename CostFunction >

CostType operations_research::HamiltonianPathSolver< CostType, CostFunction >::TravelingSalesmanCost

(

)

Returns the cost of the TSP tour.

Definition at line 857 of file hamiltonian_path.h.

TravelingSalesmanPath() [1/2]

template<typename CostType , typename CostFunction >

std::vector< int > operations_research::HamiltonianPathSolver< CostType, CostFunction >::TravelingSalesmanPath

(

)

Returns the TSP tour in the vector pointed to by the argument.

Definition at line 864 of file hamiltonian_path.h.

TravelingSalesmanPath() [2/2]

template<typename CostType , typename CostFunction >

void operations_research::HamiltonianPathSolver< CostType, CostFunction >::TravelingSalesmanPath

(

std::vector< PathNodeIndex > *

path

)

Deprecated

API.

Definition at line 870 of file hamiltonian_path.h.

VerifiesTriangleInequality()

template<typename CostType , typename CostFunction >

bool operations_research::HamiltonianPathSolver< CostType, CostFunction >::VerifiesTriangleInequality

(

)

Returns true if the cost matrix verifies the triangle inequality.

Definition at line 809 of file hamiltonian_path.h.

---

The documentation for this class was generated from the following file:

• ortools/graph/hamiltonian_path.h