It would be great if this also worked with spherical geometry as well! -----Original Message----- From: Douglas Gregor [mailto:dgregor@osl.iu.edu] Sent: Tuesday, October 23, 2007 9:34 AM To: boost@lists.boost.org 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 implicit-graph type that enumerates edges on-the-fly. 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 TSP-2 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 TSP-2 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