Boost logo

Boost :

From: Steve Nutt (Steve.Nutt_at_[hidden])
Date: 2007-10-23 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 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
> implemented (using the Euclidean distance between each pair of points
> edge weight). I guess this needs to be generalized for a boost
> But I would like to include his 'tsp_2_approximation' shortcut, as it
> solves the probably most common TSP problem: return the tour indices
> a given list of points...
Sure, it's always good to have shortcut algorithm for the simplest

    - Doug
Unsubscribe & other changes:

Boost list run by bdawes at, gregod at, cpdaniel at, john at