On Sep 14, 2005, at 7:26 PM, Jeremy Siek wrote:

Part of the problem is the language (C++), not the library. However, we may be able to fix this by going to extraordinary lengths. Though I can't say when one of the developers will have the time to do this. It's quite tedious trying to imagine all the ways an algorithm can be misused and try to trick the compiler into giving a good error message. This is one of the reasons I wrote a Ph.D. thesis about a new language.

And Jeremy neglected to mention that we're trying *very* hard to get some extensions into C++0x so that wretched error messages like these will be a thing of the past.

...

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?

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.

It's definitely slower, but I think we need to give the usability issue more weight. I only recall ever having seen two cases where someone complained about the BGL being to slow: one was with betweenness_centrality, until we learned that the person had compiled without any optimizations; the other was with bundled properties slowing things down (due to the extra level of dispatch). On the other hand, we get questions every week about how to create property maps, especially edge property maps (because there's no way to avoid managing your own edge_index_t). We should get users hooked on the BGL first, then we can worry about getting maximal performance for them later. I've been thinking of a few ways to try to help users with creating and using property maps. It's possible that "all of them" is the right answer: 1) Make edge descriptors ordered (via <), so that users can make associative property maps more easily 2) Create templates vertex_property_map and edge_property_map that create external property maps without much effort from the user; in particular, that'll use an associative property map or an iterator property map depending on whether a vertex_index property is available. 3) As Tony mentions, make the algorithms a bit more lenient about the input graphs. They could use something like the class templates in #2, so long as we can still get maximal efficiency out of them when index maps are available. 4) Create new graph types (say, directed_graph and undirected_graph) that maintain vertex and edge index maps internally (as does the Python graph type). Doug

On 9/15/05 7:05 AM, "Tony Cook" wrote:

Can I add that misuse of graph assignment and a graph copy constructor is possible - corruptible shallow copies are the result. These methods should be given private scope to prevent (mis)use or be correctly implemented

G2 = G1 ; // Compiles but NO you must use boost::graph_copy (G1, G2) instead

If this is accurate, then it should be fixed. Types with abnormal copying semantics can't be used in STL containers or similar contexts. -- Daryle Walker Mac, Internet, and Video Game Junkie darylew AT hotmail DOT com

On 9/15/05, Jeremy Siek wrote:

Hi Doug,

On Sep 14, 2005, at 9:01 PM, Douglas Gregor wrote:

<snip>

...

I've been thinking of a few ways to try to help users with creating and using property maps. It's possible that "all of them" is the right answer:

1) Make edge descriptors ordered (via <), so that users can make associative property maps more easily 2) Create templates vertex_property_map and edge_property_map that create external property maps without much effort from the user; in particular, that'll use an associative property map or an iterator property map depending on whether a vertex_index property is available.

3) As Tony mentions, make the algorithms a bit more lenient about the input graphs. They could use something like the class templates in #2, so long as we can still get maximal efficiency out of them when index maps are available.

4) Create new graph types (say, directed_graph and undirected_graph) that maintain vertex and edge index maps internally (as does the Python graph type).

All of those options sound reasonable.

All of Doug's options sound good to me, too, and I'd like to add one more idea. Most of the BGL algorithms operate on the assumption that if you don't pass in a vertex or edge index map explicitly, that index map should be accessible as an internal property, for instance, something like: template void foo(const Graph& g, VertexIndexMap vim = get(vertex_index,g)); In the above code, if g doesn't have a vertex_index property, no_property is returned from the get. What I'm thinking about is returning something other than no_property: consider another type of property map, which I'll call auto_index_property_map. It's got two data members: a shared_ptr to an associative container and an integer index called next_available_index. Its default constructor creates a new associative container, while the copy constructor and assignment operator just copy over the shared_ptr. When you call "get" on an auto_index_property_map for an element x, it checks to see if x is a key in the associative container. If it is, return the index x is associated with. If not, put the pair (x,next_available_index) in the container and return next_available_index and post-increment it. The main problem I can see with this solution is that if you call get(vertex_index,g) twice you get distinct instances of an auto_index_property_map, containing different associative containers. This could cause some pretty spectacular failures and might be a tough bug to catch within an algorithm. But from what I've seen, getting the vertex_index or edge_index property is usually done once by the algorithm, as in foo's signature above, so that all we would need to do is change the behavior of get(vertex_index,g) and get(edge_index,g) to return an auto_index_property_map. I'd be willing to code up an auto_index_property_map if anyone likes this idea, otherwise I vote for Doug's #4 above. Aaron

Thank you very much Jeremy for your prompt answer. I wasn't promoting this as a real world solution. It was just an illustration of an approach that could be taken. However I *was* promoting the principle that the BGL algorithms should work with all graph types - or at *least* document which types are not supported - currently neither is true. Do you agree with this principle?

The problem with std::map is that it does not provide constant time access to the vertex index (it is logarithmic).

1. Can anyone suggest an associative container type that I can use that performs better than std::map - some sort of hash map perhaps (does boost have one)?

... Thus, the graph algorithm will run slower; it won't have the advertised time complexity. ...

Why not change the time complexity advertisement? For example clear_vertex() advertises 4 distinct time complexities depending on sequence based vs associative-container EdgeList types and directed vs undirected graph types. Surely each of the algorithms could do likewise? I would rather have something that works and documents the consequences than something that only works under narrow conditions that are NOT documented. E.g. the documentation for copy_graph (and others) does not advertise the fact that it does not work for VertexList=listS (unless the vertex_index property is explicitly present). Maybe it should. In a nutshell the BGL is behaving like Henry Ford's model T - any graph type you like as long as it is VertexList=vecS ;) - otherwise you just have to fathom it out for yourself with little help - hummmmm.

... Then we'll get bug reports from people that are surprised by how slow the algorithm is. ...

OK so instead you get bug reports about algorithms mysteriously not compiling with certain graph types (like this one ;) - and obviously very frequently at one time as this is issue #5 on the BGL FAQ! - however I missed the FAQ connection as I didn't formulate the question in the way written). Cheers, Tony Cook PS the documentation for graph_copy has an error - its says the vertex_index_map named property should map from 0 to num_vertices(G). It should read 0 to num_vertices(G) - 1. -----Original Message----- From: boost-users-bounces@lists.boost.org [mailto:boost-users-bounces@lists.boost.org] On Behalf Of Jeremy Siek Sent: 15 September 2005 01:27 To: boost-users@lists.boost.org Subject: Re: [Boost-users] Could the BGL graph algorithms be improved toautomatically work with VertexList = listS graphs? Hi Tony, On Sep 14, 2005, at 11:08 AM, Tony Cook wrote:

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) Part of the problem is the language (C++), not the library. However, we may be able to fix this by going to extraordinary lengths. Though I can't say when one of the developers will have the time to do this. It's quite tedious trying to imagine all the ways an algorithm can be misused and try to trick the compiler into giving a good error message. This is one of the reasons I wrote a Ph.D. thesis about a new language.

At some point the BGL should be updated to use the new boost named parameter library. When that happens it would be a good idea for us to keep this issue in mind and check on the error messages.

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.

typedef std::map

typename G1::vertices_size_type> i_type ;

typedef boost::associative_property_map i_map_type ;

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? 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.

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

Thanks for all the help guys.

If a graph algorithm does not document its requirements, that's a bug, and should be fixed. However, copy_graph does document its requirement for vertex_index.

I see that now. However it is written in a difficult form which made little sense to me without that nudge. Man BGL is very steep! "Default: get(vertex_index, G)" ?? How about "Default: requires the presence of the vertex_index property map" Why else do you think FAQ #5 exists ;)

A hash map will be constant time, but is still somewhat slow. Boost does not yet have one.

:(

I don't think you understand the nature of generic algorithms.

I'm new and I'm learning. Thanks for the enlightenment :) . OK please reread this as an issue with the graph_copy algorithm. Surely all graph types should at least copy - even if *relatively* inefficiently (I can't believe that its impractical to copy!!). Worse still you can write G1 = G2 ; It compiles but doesn't work! It's shallow.

That's an exaggeration.

:) :) What I didn't tell you is that I'm *forced* by VC7.1 to use vecS,listS graphs as with my particular collection of properties, ALL other graph type combinations cause VC7.1 to issue an "Internal Compiler Error" - I should have slammed the Ford attribute onto VC7.1 - it deserves it, not BGL Anyway I'm happy this issue is being considered. I need no further assistance on this matter. Cheers, Tony

Hi Tony, On Sep 15, 2005, at 9:57 AM, Tony Cook wrote:

How about

"Default: requires the presence of the vertex_index property map"

Why else do you think FAQ #5 exists ;)

That's a fine suggestion, I've made a change along those lines to every graph algorithm.

I'm new and I'm learning. Thanks for the enlightenment :) . OK please reread this as an issue with the graph_copy algorithm. Surely all graph types should at least copy - even if *relatively* inefficiently (I can't believe that its impractical to copy!!).

Worse still you can write

G1 = G2 ;

It compiles but doesn't work! It's shallow.

Ew, that doesn't sound right. What graph type was that with? Could you send a little program that demonstrates the problem.

...

That's an exaggeration.

:) :)

What I didn't tell you is that I'm *forced* by VC7.1 to use vecS,listS graphs as with my particular collection of properties, ALL other graph type combinations cause VC7.1 to issue an "Internal Compiler Error" - I should have slammed the Ford attribute onto VC7.1 - it deserves it, not BGL

Ugh, I thought our days of ICE's from VC was over... that brings back bad memories from the days of VC 6.

Anyway I'm happy this issue is being considered. I need no further assistance on this matter.

Thanks for reporting these troubles, and thanks for encouraging the use of the BGL at work! Cheers, Jeremy

...

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 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