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)

I'm sorry - I'm new to this group - does breaking this rule invalidate asking the question? Should I repost? Yours, Tony

From: Vladimir Prus <ghost@cs.msu.su> Reply-To: boost-users@lists.boost.org To: boost-users@lists.boost.org Subject: Re: [Boost-users] Could the BGL graph algorithms be improved toautomatically work with VertexList = listS graphs? Date: Wed, 14 Sep 2005 18:31:20 +0400

Tony Cook wrote:

...

Hi,

If I define a BGL graph of the type

Please don't ask questions by replying to unrelated messages.

Thanks, Volodya

_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users