Dear list, I read in the boost/graph/metric_tsp_approx.hpp source file that the Christofides algorithm has been considered. However the implementation of the blossom algorithm is the big problem of such a task. Is anyone working on it? Cheers, Paolo On Wed, Feb 12, 2014 at 4:15 PM, Paolo Bolzoni wrote:

Hi Aaron, I am afraid it won't work because the graph is not metric anymore. The metric_tsp_approx needs a metric graph because it shortcuts the minimum spanning tree; when it happens everything works because a -> b -> c is at most as long than a -> c. Adding the node (f) it can happen that the shortcut is from a -> b -> f to a -> f and the latter is one of this "infinity weight" edges.

Cheers, Paolo

On Wed, Feb 12, 2014 at 3:50 PM, Aaron Windsor wrote:

...

Hi Paolo,

Yes, the Christofides algorithm requires a minimum weight perfect matching, and unfortunately there's no simple reduction from the problem of finding a weighted matching to the problem of finding a maximum cardinality matching. I haven't used metric_tsp_approx before, but if you're just adding one node n to an already complete graph and connecting it to s and d, could you just add all of the other edges between n and other nodes in the graph and set those edge weights to "infinity" (something bigger than the sum of all of the edge weights in the graph) to force metric_tsp_approx to avoid those edges?

-Aaron

On Wed, Feb 12, 2014 at 6:06 AM, Paolo Bolzoni wrote:

...

Dear list,

I am using boost graph and I need to solve a variant of the classic TSP. Boost providess a function (metric_tsp_approx) to get a Halmintonian cycle over a full connected metric weighted graph. However I need something slightly different.

I need a path that visits all vertices starting and ending to two well known vertices (let be s and d). Seeking around, I found the suggestion of adding a node connected to s d and with the weight of the edge (s,d). The TSP solution of the new graph is the solution, just removing the new node.

The problem is that now the graph is not complete anymore so the metric_tsp_approx's approach does not work anymore.

Another possiblity is using a variant of Christofides algorithm, but one of the passages of that is the minimum weight perfect matching.

I am a little confused by the documentation of the functions about Maximum Cardinality Matching(1), it is possible to use them to find the a maximum cardinality matching so that the total weight of all selected edges is minimal?

Otherwise, is there an alternate approach to my problem?

Yours faithfully, Paolo

(1) http://www.boost.org/doc/libs/1_55_0/libs/graph/doc/maximum_matching.html _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users