Re: [Boost-users] Minimum perfect matching

Subject: Re: [Boost-users] Minimum perfect matching
From: Paolo Bolzoni (paolo.bolzoni.brown_at_[hidden])
Date: 2014-02-12 10:15:52

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 <aaron.windsor_at_[hidden]> 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
> <paolo.bolzoni.brown_at_[hidden]> 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_at_[hidden]
>> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>
>
>
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users