Re: [boost] BGL: traveling sales man

From: Douglas Gregor (dgregor_at_[hidden])
Date: 2007-10-23 22:42:52

On Oct 23, 2007, at 4:04 PM, Oliver Kullmann wrote:
> 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 completely agree, even though I may have written the paragraph you  
quoted above :)

We like having several variants of algorithms in the BGL. The way I  
see it, we should include whatever good algorithm implementations we  
can get our hands on. Then, it's our responsibility to try to  
determine which algorithms are best in which circumstances, and  
provide simple, top-level functions that perform the appropriate  
heuristics and dispatch to the best algorithm. Algorithm-savvy users  
could still invoke specific algorithms when they want to, of course.

        - Doug