Re: [Boost-users] tsp 2-approximation using triangle inequality

From: Matyas W Egyhazy (megyha80_at_[hidden])
Date: 2006-08-03 21:26:44

Doug,

Thank you for the feedback.  The visualization stuff was definitely for 
the purposes of the homework assignment only - and the vertex naming 
convention was also so the vertices would have names in the neato 
graphs.  These can be removed from the implementation.  One other 
modification I was thinking of was to use a lookup map for saving the 
edge weights (lengths) after they have been calculated so they do not 
have to be calculated multiple times.

To make the interface as simple as possible I can remove the ostreams 
and the graph parameter so the algorithm requires only the position map 
for the vertices and returns the predecessor mapping for the TSP 
2-approximation tour.

Something like:

template<typename PositionMap, typename PredecessorMap>
void tsp_2_approximation(const PositionMap& pos,
                          PredecessorMap preds)

or

template<typename PositionMap, typename PredecessorMap>
PredecessorMap tsp_2_approximation(const PositionMap& pos)

If you agree with these changes I will make the updates and repost them.

Matt

Doug Gregor wrote:
> On Jul 27, 2006, at 9:04 PM, Matyas W Egyhazy wrote:
>> I recently implemented an approximation for the traveling salesperson
>> using the boost graph library.  The interface as well as the
>> implementation are not polished and they require improvement,  
>> mostly due
>> to the work being part of a school homework assignment.  If anyone is
>> interested, I would like outside comments before spending (or wasting,
>> if no one is interested) effort to fix it up.
> 
> I think this would make a good addition to the BGL. You'll probably  
> want to separate out the core algorithm from the name handling/ 
> initialization/display code a bit more, but it looks like it's in  
> good shape.
> 
> 	Doug
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>