[graph] Bug in metric_tsp_approx_tour?

Hello, I have an application where I need to approximately solve the traveling salesman problem. I tried metric_tsp_approx_tour_from_vertex, just following the boost test code. The function works as long as the provided start vertex is zero, but given any other vertex I get rubbish back. For example, given a graph with ten vertices, the returned tour can be of length 4. I am using the following graph type: typedef adjacency_matrix<undirectedS, no_property, property<edge_weight_t, double> > Graph; and the following call: metric_tsp_approx_tour_from_vertex(graph, start_v, back_inserter(tour)); Am I doing something wrong, or is this a bug? Regards, /Morten

On Wed, 10 Oct 2012, Morten Strandberg wrote:
Hello,
I have an application where I need to approximately solve the traveling salesman problem. I tried metric_tsp_approx_tour_from_vertex, just following the boost test code. The function works as long as the provided start vertex is zero, but given any other vertex I get rubbish back. For example, given a graph with ten vertices, the returned tour can be of length 4.
I am using the following graph type:
typedef adjacency_matrix<undirectedS, no_property, property<edge_weight_t, double> > Graph;
and the following call:
metric_tsp_approx_tour_from_vertex(graph, start_v, back_inserter(tour));
Am I doing something wrong, or is this a bug?
Could you please try the attached patch? Thank you. -- Jeremiah Willcock
participants (2)
-
Jeremiah Willcock
-
Morten Strandberg