[boost] BGL and hamiltonian paths

From: Fernando Cacciola (fcacciola_at_[hidden])
Date: 2002-08-16 09:02:37

Hi there,

I need to solve the following graph problem. I know how to do it by hand (I
think :-) but I was trying to figure out what would be the best approach
using BGL features. None of its algorithms seems to be of any help, but I
might be just missing it...

The problem (conceptually):

Given a set of n geometric sites and a distance map with entries for each
pair of sites; that is, given a weighted Kn;
And given starting and ending sites (s,e).
I need to find the sequence of sites from the s to e that passes through all
the sites only once with the shortest step each; that is, I need to find a
minimum weight Hamiltonian path from s to e.

I don't have any Graph book at hand, so if my memory isn't failing me, this
is essentially a matter of removing all but the lowest-weight out-edges from
s and e; and then removing all but the two lowest-weight out-edges from all
other vertices to form an euler graph, and finally doing a topological sort.

I think I know how to do it by hand using a loop, out_edges() and
remove_edge(); but I was wondering if there was any shortcut.

TIA,

Fernando Cacciola
Sierra s.r.l.
fcacciola_at_[hidden]
www.gosierra.com