Re: [Boost-users] Could the BGL graph algorithms be improved toautomatically work with VertexList = listS graphs?

From: Tony Cook (tony__cook_at_[hidden])
Date: 2005-09-16 04:21:48

>>The problem with std::map is that it does not provide constant time  
>>access to the vertex index
>>(it is logarithmic). Thus, the graph algorithm will run slower; it  
>>won't have the advertised
>>time complexity. Then we'll get bug reports from people that are  
>>surprised by how slow the
>>algorithm is.

As a postscript to this issue with graph_copy, I note that the current
implementation of the related boost::adjacency_list<> operator= uses a
std::map in the core of its implementation (boost 1.33.0 adjacency_list.hpp
line 1775). So this objection to std::map was overruled here. However the
author has noted the non constant time. (The non existent boost::hash_map
would improve matters - yes?)

      inline void copy_impl(const adj_list_impl& x_) 
      {
        ...
        // Would be better to have a constant time way to get from
        // vertices in x to the corresponding vertices in *this.
1775:   std::map<stored_vertex*,stored_vertex*> vertex_map;

        ...
        for (tie(vi, vi_end) = vertices(x); vi != vi_end; ++vi) {
          ...
          vertex_map[(stored_vertex*)*vi] = v;
        }
        ...
        for (tie(ei, ei_end) = edges(x); ei != ei_end; ++ei) {
          ...
          tie(e, inserted) = add_edge(vertex_map[(stored_vertex*)s], 
                                      vertex_map[(stored_vertex*)t], *this);
          ...
        }
      }

Tony