
Boost : 
From: Steve Nutt (Steve.Nutt_at_[hidden])
Date: 20071023 21:14:36
It would be great if this also worked with spherical geometry as well!
Original Message
From: Douglas Gregor [mailto:dgregor_at_[hidden]]
Sent: Tuesday, October 23, 2007 9:34 AM
To: boost_at_[hidden]
Subject: Re: [boost] BGL: traveling sales man
Michael Held wrote:
> Hi Doug,
>
> Yhank you very much. Your reply was *very* helpful and the code worked
> out of the box.
>
> What should be done to bring TSP closer to boost?
>
A couple things I saw:
 Needs documentation!
 Test driver needs to validate its result, not just print it
 It would be nice if we had the 1.5x approximation rather than the 2x
approximation, of course...
 The algorithm should accept a function object that computes the
distance between two vertices in the graph; of course, that function
object needs to satisfy the triangle equality, and should default to
Euclidean distance, but it's good to have that customizability
 We shouldn't be building the first graph (the complete graph) in
memory, ever. Ideally, we would create an implicitgraph type that
enumerates edges onthefly. Or, if we really need to create the graph,
why not use adjacency_matrix instead of adjacency_list?
 The Tour parameter should be an OutputIterator, not an array, to
better match the interfaces in the rest of the BGL.
 I would have expected the TSP2 approximation algorithm to accept a
graph, but it doesn't; instead, it infers the number of vertices from
the "size" of the property map. Unfortunately, there is no such notion
for property maps, so the PositionMap is essentially restricted to a
vector_property_map. I'd rather have the algorithm accept a
VertexListGraph, then compute the TSP2 approximation for that graph
based on just a distance function between two vertices.
IMO, the signature of the algorithm should be:
template<typename VertexListGraph, typename DistanceFunction,
typename OutputIterator>
OutputIterator tsp_2_approximation(VertexListGraph const& g,
DistanceFunction distance, OutputIterator out);
For the normal case of Euclidian distance, one would provide a function
template that turns a PositionMap into a distance function:
template<typename PositionMap>
??? euclidean_distance(PositionMap position);
> So far the TSP approximation of a list of 2D points is straight
forward
> implemented (using the Euclidean distance between each pair of points
as
> edge weight). I guess this needs to be generalized for a boost
integration.
> But I would like to include his 'tsp_2_approximation' shortcut, as it
> solves the probably most common TSP problem: return the tour indices
for
> a given list of points...
>
Sure, it's always good to have shortcut algorithm for the simplest
cases.
 Doug
_______________________________________________
Unsubscribe & other changes:
http://lists.boost.org/mailman/listinfo.cgi/boost
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk