- Boost - lists.boost.org

Re: Re: [BGL] forced client complexity
by Johnny Yune 03 Apr '04

03 Apr '04

Jeremy Siek" <jsiek(a)osl.iu.edu> wrote in message news: > So I think your question can be boiled down to two > questions, why does the BGL use vertex descriptors? > and why does the BGL use property maps? That probably restates my question more succinctly than I would be able to. > The BGL graph interface was designed so that many different > graph data structures could be uniformly manipulated. > It sounds like the data structure that you are most familiar > with is where each node is an object, and the connecting > structure of the graph is represented with pointers. For my na�ve endeavors, I most often use adjacency matrices. >However, > another important graph data structure is the adjacency list > representation, where there are no node objects. Instead there > is just an array of lists of integers. An integer n is associated > with each node, and the out-edge list for a node is at offset > n in the array. That seems like an intuitive way for the back-end to work. Why should I, as a client, need to concern myself with those details, though? I�m sorry if I sound critical, but I just don�t understand. To me, it feels like using some sort of balanced tree container and having to concern myself with whether a node is red or black � why do I need to know? > The vertex_descriptor abstraction provides an opaque handle > to a "vertex", whatever that may be for the data structure. > For one graph type that may be node*, for another int. > The purpose of the property map interface is to provide a > uniform way for an algorithm to access data that is associated > with a node or edge. Again, there are many ways that such > an association can be implemented, with various time, space, > and convenience tradeoffs. Here are some examples: > > 1. Associated data is a member of a struct > 2. Data is in an array, organized by vertex index offset > 3. Data is in a hash table, somehow keyed on the vertex. > > Now, the problem you're pointing out is that the extra > level of indirection of the property map makes the > syntax rather unwieldy for accessing data. For > example, instead of: > > v->color > > one must write: > > get(color_map, v) > Actually, what I really wanted clarification on was why the task of managing this mapping was left to the client instead of the underlying graph structure. The differences in syntax, above, are only indications of my confusion about the semantics. To wit, given your examples, I wouldn�t necessarily expect v->color to have anything to do with the color_map. v->color looks like a property of a vertex, while get(color_map, v) looks like a property of a graph. > (not to mention the trouble of setting up the color_map > to begin with) Well, this does make things a lot more complex. The need for such mappings is quite clear to me � the need for the client to �set them up� as opposed to the graph is unclear to me, though. If I were to ask an algorithm to generate a chromatic number over a graph, I could envision having a property map of some possible coloring returned to me. Why I would have to set one up or pass one in, though, I am unclear on. In reviewing my post, I am realizing just how astute you were to identify the property map as a major source of confusion for me � I am only beginning to be able to articulate why it �feels� unnatural for me. I guess the big question, then, is �why use property maps instead of functors?� Would not functors also allow communication between arbitrary user-defined vertex types, the graphs that store them (even if only by lookup mapping to some arbitrary internal data type), and the algorithms that operate over them? My gut tells me that it is so. It also seems like using functors would be a natural way to help preserve clarity � if an algorithm requires that every vertex have an index or a name or a color et cetera, mightn�t it be natural to pass in a functor that can extract, generate, or synthesize the required property? Such functors may also be good candidates for being defaulted, which could significantly help to simplify client code. Isn�t that, after all, the model that our beloved standard library follows with its generics? Thanks, again, for entertaining my questions. I am highly pleased to be soliciting rationale and intent instead of the rabid defensiveness or dismissal that I probably deserve. __________________________________ Do you Yahoo!? Yahoo! Small Business $15K Web Design Giveaway http://promotions.yahoo.com/design_giveaway/

2 1

Re: [BGL] forced client complexity
by Johnny Yune 03 Apr '04

03 Apr '04

"Vesa Karvonen" <vesa_karvonen(a)hotmail.com> wrote: {snipped throughout} > The design employed by BGL makes it > possible to provide faster lookups > than what is possible with hash > tables. The cost is, as you have noticed, > tougher requirements for the client. That is the conclusion that I am drawing, also. > >If, instead, it is a synthesized construct > >for communication between a > >graph and the algorithm operating > >over it, why should the client be > >responsible for its maintenance > >instead of the framework? What are the > >advantages of this approach? > > The advantage is that the client > can choose how nodes are mapped to > indices. The client can, in particular, > provide a significantly faster > mapping method. For example, the color > of a node could be stored in the > node itself, which would mean that > accessing the color property would be a > very fast O(1) operation. It could easily > be an order of magnitude faster > than a hash table lookup. We�re using the word �color� in an ill-defined context here, but I am assuming that we�re talking about an attribute used to tag a node in calculating chromatic numbers. That said, why would a coloring algorithm operating over the graph need to utilize the mapping of internal indexes to user-defined nodes? Again, this seems parallel to a red-black BST requiring that its value_type know about its color. If I had to write set<propertymap<int,color>> instead of set<int>, I�d feel the same distress. Of course, for things that are natural attributes of a node, like data from which a weight attribute can be generated, there would be no escaping the lookup cost. > It should also be possible for a > graph algorithm to internally convert a > graph to an isomorphic copy that > allows essentially optimal accesses (it > should be doable in O(V+E) time and > space in most cases). However, the > time and space required by the conversion > would probably make such a > conversion useless except for graph > algorithms whose complexity is > significantly higher than O(V+E). That sounds reasonable. I don�t see how it is applicable, though. How does maintaining a mapping between internal and external structures for a public interface hinder internal manipulation? > The disadvantage of requiring only > hashing and equality comparison from > the client is that sometimes there > are significantly more efficient ways > to associate information with nodes > and the opportunity to take advantage > of those more efficient ways is lost. Uncompromising performance at the expense of clarity or usability is a common feature of C/C++ code. It may be ample justification for the complexity of BGL use � especially since measures of clarity and usability are probably more subjective than measures of performance. > >This is the type of design issue that I intended to question with my > >initial post. > > Does this answer your question? I think that it may. Thank you for helping me to reveal some differences between possible approaches. __________________________________ Do you Yahoo!? Yahoo! Small Business $15K Web Design Giveaway http://promotions.yahoo.com/design_giveaway/

1 0

RE: [boost] Re: Policy or Trait?
by Rozental, Gennadiy 03 Apr '04

03 Apr '04

> I thought I'd try an example to see what happens. > whether this is best example I dont know....whatever > Many more variants of course possible. > operator()() could be moved into multiply_traits etc > which would give user yet more control. > Perhaps that is the difference. Move all the implementation > out of the class gives the user more flexibility. But is it > the flexibility that se wants. (Sorry boost pros uses she > above, but men users, women developers, viceversa...just a > personal thing) > > First observation from below ....Obviously the application > has a great deal to do with it.! :-) Many more experiments to > do ... but ... Interesting debate. > > regards > Andy Little > > ----------- > > #include <iostream> > template< typename A , typename B > > struct multiply_traits; > > // use traits > template< typename A , typename B > > struct multiply1{ > > typedef multiply_traits<A,B> traits; > typename traits::result_type operator () > (typename traits::first_argument_type a, > typename traits::second_argument_type b) > { > return a * b; > } > > }; > //use policy > template< typename A , typename B, typename Policy> > struct multiply2{ > > typename Policy::result_type operator () > (typename Policy::first_argument_type a, > typename Policy::second_argument_type b) > { > return a * b; > } > > // or Policy ()(a,b); etc if ---> policy > > }; And give me single example where second design is preferable to first? Actually I think the best design would look like this: namespace { struct multiply_t { template< typename A , typename B > struct sig : multiply_traits<A,B> {}; template< typename A , typename B > typename sig<A,B>::result_type operator ()( typename sig<A,B>::first_argument_type a, typename sig<A,B>::second_argument_type b ) { return a * b; } } multiply; } int main() { std::cout << multiply( 10, 1.5 ) <<'\n'; MyInt i( 10 ) std::cout << multiply( i, 10 ) <<'\n'; } Gennadiy.

3 2

RE: [boost] Re: Policy or Trait?
by Rozental, Gennadiy 03 Apr '04

03 Apr '04

> > both for that type. A trait class is never passed as a template > > parameter; it's name is ubiquitous. > > Whoops, can't agree there. The boost type traits are passed > as template parameters all the time: > > mpl::apply_if< > is_pointer<X>, remove_pointer<X>, add_reference<X> > > What he meant, I think, is "never passed as a template parameter together with primary type" > > A traits class never has state. > > > > Policy - A class template passed to other templates for the > purpose of > > providing a named grouping of metainformation, > > I think a Policy might be a non-templated class. True. > I think your definitions are mostly on target, but I think > where you go wrong is that traits/policies has less to do > with how a template is defined than how it's used. Could you please rephrase. It's a bit unclear. Gennadiy.

6 17

Re: Re: [BGL] forced client complexity
by Johnny Yune 03 Apr '04

03 Apr '04

"Cromwell Enage" <sponage(a)yahoo.com> wrote: (much snipping throughout) > > Boost.Graph seems to expose and require an > > unnecessarily large amount of complexity, > > though. > > If by "exposure" you mean lots of source code, I'll > take that complexity any day of the week and twice on > Sundays. :) Yes, I should�ve mentioned in my original post that I am unaware of another c++ graph library as powerful and flexible as BGL. It seems peerless at present. I was worried that my queries would be abrasive and am pleased to get such well-written responses. > The library does have a rather steep learning curve, > especially if you're somewhat unfamiliar with graph > theory and/or template programming. Perhaps my unrest is an extension of my naivety. We seem to be in agreement about BGL�s complexity, though. I guess the question is whether or not that complexity is absolutely necessary. > > The amount of scaffolding required > > to use BGL for even the simplest of projects > > often dwarfs the code size of a naive, > > yet functional, special-purpose implementation. > > Special-purpose implementation of a graph library? Or > the project? Special-purpose implementation of the graph related functions that would otherwise have been provided by a graph library. > Furthermore, while most STL > algorithms confine themselves to handling just those > STL container elements, most graph algorithms also > need the properties of vertices and/or edges as input. Unquestionably. > BGL delegates some of the responsibility of property > storage to the Boost Property Map Library. My confusion is as to why managing those properties are left to the client instead of the underlying container. In the case of properties that are intrinsic to the (user-defined) object being stored in the graph, I feel like they should be accessed as attributes of the object and �connected� to algorithms by generally trivial functors. What advantage is had by forcing the client to manage a property map of properties to vertices when they could instead provide a functor to reveal the same information? What about the cases where the needed properties are only relevant to the underlying graph structure and the algorithm, like indices? Wouldn�t it be more elegant to have graph container manage those properties than the client? > Having dwelt in the academic circle known as the > University of Central Florida, and thus familiar with > the theoretical uses of a graph library (plus I've > studied some game development apps on the side), I'd > like to learn more about how the Real World would want > to use BGL. I can�t speak for the �Real World� at large, but I can give you an example of the kinds of problems I would typically use a graph library for. When evaluating new programming languages (and often just for fun), I download problem sets from old top-coder and ACM programming contests. In almost every set of problems, there is at least one challenge which would benefit from a standard library graph extension. Usually, they center on things like building conversion equations from a series of ratios, walking a family tree, choosing a good path, scheduling planes, etc � the kind of stuff in an undergrad discreet math class. These problems will almost solve themselves in certain programming languages, but in C++, they require a bit more work (as you know). Doing a few of these problem sets always drives home, to me, the fact that C++ really needs standard facilities for graphs and regular expressions. > > Even knowing that ease-of-use is not a criterion > > for acceptance into boost, looking at what is > > required of the client to use the BGL always leaves > > me feeling perplexed. Is there any particular reason > > that a simplified interface is not made available? > > Again, I don't know a simple graph problem that > requires a simplified graph interface. Simplicity is rarely a requirement as such. Perhaps it is just ignorance on my part, but riddle me this: I can describe a graph in visgraph�s format in a very small number of simple statements, render it, hand it to a person and ask them to answer questions like �is there any path from A to Z?� What fundamental functionality would this kind of simplicity preclude if applied to BGL? > > Perhaps a container adapter could be packaged with > > the library allowing a compromise of functionality > > and flexibility for simplicity? > > I thought the boost::vector_as_graph class template > served that purpose. Wrap it around a > std::vector<EdgeList>, with EdgeList = > std::list<unsigned int> (or an edge list container of > your choice, so long as the value type is usable as an > index in the vector), and you should be good to go. This may be an option, although it doesn�t really seem to offer the generational leap in simplicity that I would like. Maybe I am simply needing one more layer of abstraction? Perhaps, I need something that removes the seemingly awkward distinction between the �thing you want to store in the graph� and �the attributes of the thing you want to store in the graph but are not a part of the thing and are instead part of this other thing.� Confusing, isn�t it? > > If a graphing problem is trivial, shouldn't BGL > > provide a trivial solution? Why are the simplest > > useful examples several hundred lines of code? > > The examples don't seem that big and hard to > understand. Of course, quite a few of them have > #ifdefs that I could do without since I don't use the > compilers in question, but I can live with them. For reference, this is from the Kevin Bacon example: typedef property_map < typedef adjacency_list < vecS, vecS, undirectedS, property < vertex_name_t, std::string >, property < edge_name_t, std::string > >, vertex_name_t >::type actor_name_map_t; I, personally, would find it much more natural to define an actor type with appropriate members than to manage such declerations. While my views are probably shaped by my limited understanding of the stylistic model, that is one UGLY typedef. It doesn�t really come trippingly off the tongue, does it? The amount of scaffolding required for BGL use is generally large and complex enough that I would find myself writing wrappers for the BGL so that I could use it without constant need for a reference manual. That would generally be a bad situation for me (more work), for other developers (unfamiliar framework dependency), and for end-users (greater risk of bugs via unproven code). > > I apologize for all of my vague criticisms - my > > intention is not to flame but rather to test the > > waters. > > Your criticisms seem healthy, and I hope my responses > are helpful. Thanks ever so much. I guess that all I have to worry about now is making a fool of myself. > > It is difficult for me to assess whether the > > simplicity I yearn for isn't present for stylistic > > reasons or whether it would rather necessitate a > > sacrifice of flexibility, functionality or > > implementation clarity. Nor is it clear to me to > > what extent these criteria can be compromised to > > promote clarity of client code. For what it is > > worth, the kind of ease-of-use I'm imagining might > > look like: > > #include <less_than_10_graph_headers> > ... > digraph<some_node_type,some_edge_context_type> g; > g << "vertex" << make_pair("vertex", > "implicit_vertex"); > g.add_edge("brother", "sister", "sibling"); > if(g.find(make_pair("brother", "sister"))) > related = true; > > > Could someone please elucidate on why it is > > impossible/impractical/unnecessary/whatever for a > > graph library to have such an interface? > > I believe the potential for ambiguity would hinder > this syntax the most. In this case, you'd have to > overload operator<< to input both edges and vertices, You are absolutely correct. I should�ve been more careful in presentation. Using operator<< in this case was probably a poor choice, anyway. Using add_* would�ve conveyed more information. > and what if some_node_type turned out to be std::pair? > You couldn't pass in make_pair(vertex,vertex) as an > edge then. I believe that would be ambiguous only if a vertex was somehow illegally defined to be a pair of vertices. Regardless, g.add_edge(x,x,x) is just as simple to type. > The same goes for g.find(); is it supposed > to find a vertex, an edge, or both? find would�ve been much more descriptive written as std::find(g.dfs_begin(�brother�), g.dfs_end(), �sister�) or some such. These are just ideas, of course, not proven interfaces. And my illustration wasn�t really intended so much as an example of syntax as an example of what I considered to be a �friendly� api. > Also, it seems you want to be able to use non-built-in > or custom types as vertex IDs. Actually, I would prefer to use non-built-in types as the vertex. If additional meta-data is needed for internal maintenance, then I don�t generally want to be bothered/privileged with it as a client. > You'll have to build > your own custom-type-to-vertex map and bind it to the > graph; It seems like that would be better left to the framework. > BGL won't do it for you, to retain its > genericity. It seems like adding another layer of abstraction should decrease coupling instead of adding it. I don�t really see how specifying that I want a graph of file dependencies, for example, is any less generic than saying that I want a graph of property maps where the id is a filename. Regards, prs __________________________________ Do you Yahoo!? Yahoo! Small Business $15K Web Design Giveaway http://promotions.yahoo.com/design_giveaway/

1 0

RE: [boost] problem with global mutex object on windows
by Darryl Green 02 Apr '04

02 Apr '04

> -----Original Message----- > From: boost-bounces(a)lists.boost.org > [mailto:boost-bounces@lists.boost.org] On Behalf Of Stefan Seefeld > Sent: Friday, 2 April 2004 4:59 AM > To: boost(a)lists.boost.org > Subject: [boost] problem with global mutex object on windows > > > hi there, > > we'v run into a problem with the boost_thread mutex class, > when used as a global object. > > Imagine a singleton class as > > class Singleton > { > public: > static Singleton *GetInstance(); > static void Destroy(); > private: > > struct Guard > { > ~Guard() { Singleton::Destroy();} > }; > static Singleton *instance; > static Guard guard; > static boost::mutex mutex; > }; > > where the internal access to 'instance' is serialized by means of the > mutex (inside methods GetInstance() and Destroy()). > > It is the Singleton::Guard destructor that is responsible to free > the instance (if it isn't destructed already). It, too, uses the > mutex to protect access. > > In a specific context on windows xp it happened that the mutex > variable was destructed before the guard, leading to a global 3.6.2 Objects with static storage duration .. shall be initialized in the order in which their definition appears in the translation unit. 3.6.3 ... These objects are destroyed in the reverse order of the completion of their constructor or of the completion of their dynamic initialization. So as long as the Singleton::Guard definition is before the definition of the mutex it should work. I assume that despite having the definitions in that order it doesn't work? Does that make it a compiler bug or am I missing something? In any case, I'm not convinced that this is sufficient to make your singleton useful. Do you know that GetInstance isn't called by the constructor of a static object? Do you know that no other threads (which might call GetInstance) are started prior to the mutex being constructed? I haven't tried to get a truly thread-safe singleton working - I remember several discussions about it here - but I'm not sure that any of them resulted in an efficient working solution? Sorry - perhaps not an altogether helpful response. Darryl. ########################################################################## This e-mail is for the use of the intended recipient(s) only. If you have received this e-mail in error, please notify the sender immediately and then delete it. If you are not the intended recipient, you must not use, disclose or distribute this e-mail without the author's prior permission. We have taken precautions to minimise the risk of transmitting software viruses, but we advise you to carry out your own virus checks on any attachment to this message. We cannot accept liability for any loss or damage caused by software viruses. ##########################################################################

2 1

Nightly CVS not using current BoostBook L&F
by Reece Dunn 02 Apr '04

02 Apr '04

A while back, Doug Gregor mentioned that the metacomm Nightly CVS did not use the new BoostBook L&F. This has since been updated, and the problem has persisted -- the Nightly CVS does not reflect the latest XSL:T. Regards, Reece _________________________________________________________________ Express yourself with cool new emoticons http://www.msn.co.uk/specials/myemo

4 8

Virtual member functions cause exception in get_derived_class_object
by David Rostowsky 02 Apr '04

02 Apr '04

I have a couple of really simple classes: class MyBase { public: int x; virtual int foo(int new_x) { }; // our derived classes may or may not override this function. Coders choice. }; class MyDerived: public MyBase { public: int y; MyDerived() { y = 0; }; int Get(void) { return y; }; void Set(int val) { y = val; }; }; My main goal in life is to create an instance of MyDerived class in C++: MyDerived my_derived = new MyDerived(); and then pass the pointer to a Python script where the Python script can call any of the public member functions. Yes, I am careful to keep the pointer around in the C++ code while the Python script uses it. So I expose the class (this may or may not be the source of my problems, need help): BOOST_PYTHON_MODULE(test) { using namespace boost::python; class_<MyDerived>("MyDerived") .def("Get", &MyDerived::Get) .def("Set", &MyDerived::Set) ; } /* test*/ My impasse is that the virtual function seems to really give Boost hell when Im trying to pass the pointer to the class over to the python script. Heres the code snippet for that. Its the conversion thats just KILLING me. If I comment out the virtual function, everything works perfectly! I can pass the pointer over to my script, it calls the public member functions, and Im happy. HOWEVER, if I put the virtual function back in, the following line of code just EXPLODES! // It crashes and burns in make_ptr_instance.cpp, function get_derived_class_object() boost::python::object my_arg(boost::ref(my_derived)); // pass the pointer over to the script now. int rval = callPython("myTestFunc", "Test String argument from c++", my_arg); Im completely frustrated by this. I need some psychological help! Thanks in advance! Dave

4 9

RE: [boost] Re: Policy or Trait?
by Hurd, Matthew 02 Apr '04

02 Apr '04

From: boost-bounces(a)lists.boost.org [mailto:boost-bounces@lists.boost.org] > On Behalf Of David Abrahams > > Rob Stewart <stewart(a)sig.com> writes: > > I think your definitions are mostly on target, but I think where you > go wrong is that traits/policies has less to do with how a template > is defined than how it's used. Can a method call be part of a trait class? I don't think traits should have anything to do with enacting behaviour (they may describe it). If it is not clear and I see a method I think of it as policy-like. A collection of types and static constants and I think of it as trait-like. I think it gets confusing with the overloading of the English word policy. A policy on how to do something could be passed by value as a polymorphic object or as a simple Boolean flag for that matter... which is not the common intended meaning that MCD brought into common focus. I'll try to add something... Traits are used to get information at compile time. Policies are used to modify behaviour. Traits could be used by a client to modify behaviour which makes them feel like a policy class, but they aren't in what we normally think of as a policy. If a trait is used to direct the modification of behaviour, is it a policy from the client classes point of view I guess... which points to the terminology confusion. Policies can be chained, multiply inherited from or just be ordinary template classes with static methods, maybe such different styles should have different names... a chain aspect, a base aspect (MCD-like), a static aspect... You could then say aspects and traits could be used as policies perhaps... A policy is then something that maybe used to modify behaviour. A trait carries information for use such as for behaviour modification. An aspect extends the definition of trait to also encapsulate behaviour. An aspect and a trait may be used as a policy. Does that work? It would be nice if something new like "aspect class" or some such could be defined and used commonly to avoid the mess, but I suspect it is too late. Regards, Matt Hurd _______________________ Susquehanna Pacific P/L hurdm(a)sig.com +61.2.8226.5029 _______________________ IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments. Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited. Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument. Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or that this message or any of its attachments is free of viruses.

7 18

Re: [boost] [BGL] least common ancestor
by Cromwell Enage 02 Apr '04

02 Apr '04

Walter Landry <wlandry(a)ucsd.edu> wrote: > Hmm. I don't know if I'm that patient. How about > _I_ convert it to C++, and then you can Boostify it? Okey-dokey! There's a subdirectory in the File Vault called "bgl_algo", you can upload it in there so I can find it easily. Cromwell Enage __________________________________ Do you Yahoo!? Yahoo! Small Business $15K Web Design Giveaway http://promotions.yahoo.com/design_giveaway/

2 1