Re: [Boost-users] BGL metric_tsp_approx time complexity?

Subject: Re: [Boost-users] BGL metric_tsp_approx time complexity?
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2011-06-07 14:27:49

On Tue, 7 Jun 2011, Anders Wallin wrote:

> On Tue, Jun 7, 2011 at 4:45 PM, Jeremiah Willcock <jewillco_at_[hidden]> wrote:
>> On Tue, 7 Jun 2011, Anders Wallin wrote:
>>
>>> Hi all,
>>>
>>> I ran metric_tsp_approx on a number of TSPLIB problems and got the
>>> following graph:
>>> http://goo.gl/iGYsH
>>>
>>> This would indicate the time-complexity is V^2
>>
>> Are you using an adjacency matrix as your representation?
>
> Yes.
>
>>  Are your graphs dense?
>
> Yes they are complete graphs, so that is as dense as it gets I guess.
>
>> I don't remember what TSPLIB contains exactly -- are you using
>> Euclidean problems that would turn into dense graphs?
>> In that case, just reading the graph's distance matrix would take O(V^2), and so the complexity
>> you are seeing is correct.
>
> Right. My point is that the documentation for metric_tsp_approx and
> for prim_minimum_spanning_tree suggests that I should see O( E log (V)
> ) time complexity, which for complete graphs is O(V^2 log (V) )  when
> in fact I am seeing V^2 which is better.
> Does the BGL documentation say something about differing time
> complexity for adjacency_matrix and dense graphs? should it?

I do not believe the code uses any special-case algorithms for dense 
graphs and uses a d-ary heap, so it probably actually is O(V^2 log_4 V); 
you might not be hitting a large enough V to see the log term.  It is odd 
that the times follow the V^2 line so closely, though.  Try changing the 4 
on line 323 of <boost/graph/dijkstra_shortest_paths.hpp> to 2 and see if 
that does anything to your times.

-- Jeremiah Willcock