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-15 06:05:16

Hi Doug,

All excellent points and I really hope it happens in some form :) . The BGL
is great BUT yes usability should take more weight. My project manager was
all for scrapping using the BGL because of some of these issues. I thought
it was worth a couple more days graft to work out solutions because the
payback using the BGL would be more than worth it. In my limited experience
(2 months now) there are too many trip wires of the sort we are discussing.
I got there in the end with my current problem but the axe is still hovering
:(

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

>>>     3) ... so long as we can still get maximal efficiency out  
>>>of them when index maps are available.

This was exactly what I was asking in the original post, that my suggestion
(in some form) be merged into the algorithm such that it is ONLY used if
there is no vertex_index property available either by a graph vertex
property OR a named parameter input to the algorithm.

>>     4) ... that maintain vertex and edge index  
>>maps internally (as does the Python graph type).

I'm doing just this in a wrapper I have around the BGL graph types. So yes
there is a problem that I guess others are also working around.

>>     1) Make edge descriptors ordered (via <), so that users can make  
>>associative property maps more easily

Well guess what - I had to do this (but it won't work for multigraphs so
it's not complete)!

      template<typename EdgeType>
      struct EdgeCompare : public std::binary_function<EdgeType, EdgeType,
bool>
      {
         bool operator ()(const EdgeType& edge1, const EdgeType& edge2)
const
         {
            if (edge1.m_source <  edge2.m_source) return true ;
            if (edge1.m_source == edge2.m_source &&
                edge1.m_target <  edge2.m_target) return true ;
            return false ;
         }
      } ;
      
      /**
      An atom graph edge set type (i.e. a type that represents a set of
atom/atom interactions)
      Note we need to supply a custom type containing a LessThanComparable
functor to determine 
      the sort order for AtomEdgeType
      */    
      typedef std::set<AtomEdgeType, EdgeCompare<AtomEdgeType> >
AtomEdgeSetType ;  

Tony

PS I've not introduced myself. I've worked on graph algorithms applications
in computer chemical representation problems for 21 years and I am familiar
with a whole range of graph algorithms for efficient graph isomorphism
detection, subgraph isomorphism (Ullman, Sussenguth, Figeras etc), Morgan
vertex labeling, graph partitioning (symmetry detection), maximal common
subgraph, beta rings, k rings, smallest set of smallest rings (SSSR),
extended SSSR etc etc. Hopefully over the next few years I'll be able to
contribute new (to the BGL) algorithms if they prove useful. If I'm correct
in my understanding the BGL is/was developed at Indiana University, in which
case can I suggest you could lookup David Wild in the ChemoInformatics dept
as he can comment on the utility of many graph algorithms mentioned above in
the chemoinformatics domain. 

-----Original Message-----
From: boost-users-bounces_at_[hidden]
[mailto:boost-users-bounces_at_[hidden]] On Behalf Of Douglas Gregor
Sent: 15 September 2005 03:02
To: boost-users_at_[hidden]
Subject: Re: [Boost-users] Could the BGL graph algorithms be improved
toautomatically work with VertexList = listS graphs?

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<T, Graph> and  
edge_property_map<T, Graph> 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<Vertex, Edge> and  
undirected_graph<Vertex, Edge>) that maintain vertex and edge index  
maps internally (as does the Python graph type).

     Doug
_______________________________________________
Boost-users mailing list
Boost-users_at_[hidden]
http://lists.boost.org/mailman/listinfo.cgi/boost-users