Michale

What should be done to bring TSP closer to boost?

I wrote on a number of new algorithms/computations for Boost.Graph over the summer. One of the offshoots of that work, was a version 2 of Boost.Graph in the subversion sandbox (graph-v2). It's still basically the same thing right now, but will (should) eventually become actively developed again. I think that this would be a perfect point of integration for TSP, TSP2-approximation algorithms - hopefully Doug agrees :) There are a couple of reviews in the pipeline related to this. The Property_Map library is being re-reviewed because I added a couple of new classes and cleaned up the code a bit (it's also in the graph-v2 branch). My SoC project is also going to be reviewed, so Boost.Graph will be getting a handful of new concepts, graphs, and algorithms at the same time. Basically, once the new Property_Map library is finalized, graph-v2 should be available for new and updated algorithms. I hope... Andrew Sutton asutton@cs.kent.edu

- It would be nice if we had the 1.5x approximation rather than the 2x approximation, of course... Sure, it's always good to have shortcut algorithm for the simplest cases.

I would like to take the opportunity to say something about different algorithms for computing something (similar); actually I wanted to write already for some time to the Boost mailing lists, alarmed by a statement like The current implementation is based on descriptions of a backtracking algorithm in [46,48]. The file isomorphism-impl.pdf contains a "literate" description of the implementation. The algorithm used is simple but slow. A more efficient (and much more complex) algorithm is described in [47]. When (and if) a version of this algorithm is ported to the BGL interface it should replace the current algorithm. at http://www.boost.org/libs/graph/doc/isomorphism.html (I kind of remember having seen something similar elsewhere). Something like that, heading for the phantom of the "one and only algorithm", would be a BIG MISTAKE: 1) No algorithm dominates another algorithm (note that I speak of algorithms, not of implementations), especially not for hard problems like TSP, graph colouring or graph isomorphism: Every algorithm has its special uses and special favourable cases (for example "small graphs", or "exact solution"). 2) Algorithms are an object of study on their own! Especially the simple ones are studied extensively for many different purposes (you want to understand their behaviour, or perhaps they show an interesting pattern). So the more implementations the better! (I mean implementations of *algorithms*, which have some meanings, and are not just heuristical hacks --- but even those are interesting, if they are well-known.) I do myself research in algorithms similar to TSP and graph colouring, and I (and every colleague) is happy about every additional implementation you find (for example for teaching). Here we really have a field where we can (and should) apply political correctness: All algorithms are created equal (in some sense) ! Hope this saves some endangered algorithms (and implementations). Oliver

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