[Boost-users] Could the BGL graph algorithms be improved to automatically work with VertexList = listS graphs?

From: Tony Cook (tony__cook_at_[hidden])
Date: 2005-09-14 06:00:53

Hi,

If I define a BGL graph of the type

   typedef boost::adjacency_list
      <boost::vecS, 
       boost::listS, 
       boost::undirectedS, 
       boost::no_property,
       boost::no_property,
       boost::no_property> BadGraphType ;

Then many of the standard BGL graph algorithms such as boost::graph_copy
will not compile (e.g you get "binary '+' : no operator found which takes a
left-hand operand of type <type>" with VC7.1 - this did not help me
understand what the problem really was - i.e. a missing vertex_index
property!) 

This "no-compiler" problem is only fixed if either a vertex_index property
map is made explicitly present on this graph type via VertexProperties
template argument (See #5 on the BGL FAQ page
(http://www.boost.org/libs/graphd/oc/faq.html .)) OR the particular graph
algorithm is passed an external (or internal - if not of the vertex_index_t
type) property map as a named parameter as in:

 boost::graph_copy (graph_in, graph_out, boost::vertex_index_map (i_map)) ;

In either case prior to copying (or whatever) you need to ensure this
property map is numbered contiguously from 0 to n - 1, where n is the number
of graph vertices.

My graph does not support an implicit vertex_index property, nor do I *want*
to add an explicit vertex_index compatible property *just* to make these
algorithms work. Especially as my graphs are dynamic and I would have to
remember to renumber the property values to eliminate gaps after vertices
are deleted. 

The BGL algorithms in this situation are particularly weak as first the
"no-compile" messages are remote from the real problem, and when you have
solved that then you have to prepare the graph properly prior using the
algorithm! (if not you get memory scribbles if the indices are not
contiguous and confined to 0 to n-1)

These lead me to wonder if this problem can be eliminated and be automated
as part of the algorithm itself, i.e. if no vertex_index property was
supplied by any means, then the algorithm creates a temporary vertex index
map, loads it with vertices mapped to indices 0 to n-1 and runs the algoritm
out-of-the-box. 

It should be possible for the compiler to detect that the internal property
map is missing AND the named parameter alternative is missing (in fact the
implementations of these BGL algorithms *do* set out to discover that this
is the case, but unfortunately a final vertex "descriptor-is-the-index" map
(which is only true when VertexList=vecS) is assumed and hence the
compilation failure and a lot grief and a steep learning curve is
experienced :( )

Now to the point I wanted to make :). There IS a solution that can do this.
However I'm not expert enough to merge this into the heart of each BGL graph
algorithm algorithm that requires a vertex_index property. I have however
developed crude wrappers that do this. Here is an example solution for
boost::copy_graph that handles any graph type out of the box

      /**
      copy_graph_ex. A wrapper for boost::copy_graph that sets up
      the required vertex to 0 -> n - 1 index translation map
      @param g_in the graph to copy
      @param g_out the graph copy
      */
      template <class G1, class G2>
      void copy_graph_ex (const G1& g_in, G2& g_out)
      {

         // Create a temporary external property map that maps vertex 
         // descriptors to indices that will run 0 to n-1 

         typedef std::map<typename G1::vertex_descriptor, 
                          typename G1::vertices_size_type> i_type  ;
         typedef boost::associative_property_map<i_type> i_map_type ;
   
         i_type i ;
         i_map_type i_map (i) ;
   
         // Load the external property map with values 0 to n-1
         G1::vertices_size_type n = 0 ;
         G1::vertex_iterator vi ;
         G1::vertex_iterator vi_end ;
   
         for (boost::tie (vi, vi_end) = boost::vertices (g_in) ; 
              vi != vi_end ; 
              ++vi)
         {
            boost::put (i_map, *vi, n++) ;
         }     

         // Get the BGL graph algorithm to use the constructed index map

         boost::copy_graph (g_in, g_out, boost::vertex_index_map (i_map)) ;
      }

It would be much nicer if this external setup code was made part of the
default handling of BGL graph algorithms that require it. 

What do to BGL experts/implementers say? Would it not be **saner** to get
these algorithms to work automatically no matter what graph type was chosen?

TIA

Tony Cook (who went insane with this problem for two days)