- Boost - lists.boost.org

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

RE: [boost] Re: Policy or Trait?
by Reece Dunn 02 Apr '04

02 Apr '04

David Abrahams 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. To me a traits class provides information to a template class that gives (possibly platform or type dependant) information. For example, the decimal point character (100.00 or 100,00?) would be in a traits class (I know this is in a locale, but this is an example). Another example would be a format string to use as a separator between items in a list, depending on whether a character, string, wide character, wide string, etc are used. A policy class provides functional, i.e. behavioural, information. Examples include string comparison, pointer validation (for smart pointers) and error handling (e.g. smart pointers and how to handle InvalidPointer - nothing, throw std::exception, assert failure, etc.). Regards, Reece _________________________________________________________________ Express yourself with cool new emoticons http://www.msn.co.uk/specials/myemo

3 2

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

02 Apr '04

> Trait - A class template parameterized on a single type that > associates information with that type. A traits class, > therefore, provides an external, named grouping of > metainformation, behavior, or both for that type. A trait > class is never passed as a template parameter; it's name is > ubiquitous. A traits class never has state. By state you mean non-static data members, yes? > Policy - A class template passed to other templates for the > purpose of providing a named grouping of metainformation, > behavior, or both to those templates. Because it is a > template parameter, different policy classes can be used as > desired. In many cases, a policy class is used as a base class. Well, apparently there is somebody who think the same as I do. Thank you Rob, for your definitions. They seems sound and close to what I have in mind. > What do you think? I know that my definitions mean that > std::char_traits is a policy class, despite its name, and > they probably deviate from some other ad hoc definitions. > The question is whether these provide sound, distinct, and > defensible concepts that could be codified for future use at > Boost (and elsewhere). That's flaw in char_traits not in definitions above, IMO. Gennadiy.

2 1

BCP error for 1.31 on Windows
by Edward Diener 02 Apr '04

02 Apr '04

I built bjam for 1.31 and then I built bcp for 1.31 using MingW/GCC 3.3.1 using bjam version 1. I then opened a command prompt, went to the root directory of my Boost 1.31 distribution and tried: bcp --list shared_ptr I received this error message: **** exception(205): std::runtime_error: Error opening for output. ******** errors detected; see standard output for details ******** I then went to the boost subdirectory of my Boost 1.31 distribution and typed the same command as above and received: no errors detected but no other output was printed on standard out. I am just trying to get a list of any dependencies which shared_ptr has using bcp. What am I missing in this entire procedure ? It does not appear that bcp is working correctly but maybe I am missing something in how it should be working.

2 3

Re: [BGL] forced client complexity
by Vesa Karvonen 02 Apr '04

02 Apr '04

Provisional Dissonance: >What I was looking for, really, was dialog on existing design >strategies. It sounds like your issues with property maps mirror my >confusion with the library design, though. While I can fully appreciate >the desire to write generic code, it feels like BGL has pushed the >complexity of creating and enforcing coupling between the generic >graph/node/visitor/algorithm/etc onto the client. [...] A graph algorithm must be able to associate information on the elements of the graph. For instance, depth-first search needs to know whether it has already discovered a specific node or not (and more). In the graph utilities we implemented as part of a school project in Java, we basically relied on the hashCode() and equals() methods that every Java Object provides. The algorithm templates then internally use HashMaps for associating information on node and edge objects. This means that each time an algorithm needs to access some information (that the algorithm requires internally) on a node, a hash table lookup is performed. Assuming a good hash function, hash table lookups are O(1), but they are still slower than a direct array accesses, or accessing a member of a structure. 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. [...] >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. >What are the disadvantages of simplifying things for the client? The minimal information needed by graph algorithms, assuming best asymptotic complexity guarantees are desired, is that the client provides hashing and equality comparison functions for nodes and edges. 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. 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). >This is the type of design issue that I intended to question with my >initial post. Does this answer your question? Regards, Vesa Karvonen _________________________________________________________________ MSN 8 helps eliminate e-mail viruses. Get 2 months FREE*. http://join.msn.com/?page=features/virus

1 0

[ublas] Patch to triangular.hpp
by Giovanni Bajo 02 Apr '04

02 Apr '04

Hello, the attacched patch fixes a compilation problem of uBLAS with GCC 3.4. The fix looks legit to me, but I cannot assure this won't break other compilers due to bugs. Maybe you can monitor closely the regression fixes after having applied this. OK to commit to HEAD? -- Giovanni Bajo begin 666 triangular_gcc34.txt M26YD97@Z('1R:6%N9W5L87(N:'!P#0H]/3T]/3T]/3T]/3T]/3T]/3T]/3T] M/3T]/3T]/3T]/3T]/3T]/3T]/3T]/3T]/3T]/3T]/3T]/3T]/3T]/3T]/3T] M#0I20U,@9FEL93H@+V-V<W)O;W0O8F]O<W0O8F]O<W0O8F]O<W0O;G5M97)I M8R]U8FQA<R]T<FEA;F=U;&%R+FAP<"QV#0IR971R:65V:6YG(')E=FES:6]N M(#$N,3@-"F1I9F8@+74@+7<@+6(@+7(Q+C$X('1R:6%N9W5L87(N:'!P#0HM M+2T@=')I86YG=6QA<BYH<' ),C@@3F]V(#(P,#,@,#<Z-3@Z-3<@+3 P,# ) M,2XQ. T**RLK('1R:6%N9W5L87(N:'!P"3(@07!R(#(P,#0@,3$Z,#$Z,#(@ M+3 P,# -"D! ("TY-3@L,3 @*SDU."PQ,"! 0 T*( T*(" @("!T96UP;&%T M93QC;&%S<R!4+"!C;&%S<R!&,2P@8VQA<W,@1C(L(&-L87-S($$^#0H@(" @ M('1Y<&5N86UE('1R:6%N9W5L87)?;6%T<FEX/%0L($8Q+"!&,BP(a)03XZ.G9A M;'5E7W1Y<&4@=')I86YG=6QA<E]M871R:7@\5"P@1C$L($8R+"!!/CHZ>F5R M;U\@/0T*+2 @(" @(" @=')I86YG=6QA<E]M871R:7@\5"P@1C$L($8R+"!! M/CHZ=F%L=65?='EP92 H*3L-"BL@(" @(" @('1Y<&5N86UE('1R:6%N9W5L M87)?;6%T<FEX/%0L($8Q+"!&,BP(a)03XZ.G9A;'5E7W1Y<&4@*"D[#0H@(" @ M('1E;7!L871E/&-L87-S(%0L(&-L87-S($8Q+"!C;&%S<R!&,BP@8VQA<W,@ M03X-"B @(" @='EP96YA;64@=')I86YG=6QA<E]M871R:7@\5"P@1C$L($8R M+"!!/CHZ=F%L=65?='EP92!T<FEA;F=U;&%R7VUA=')I>#Q4+"!&,2P@1C(L M($$^.CIO;F5?(#T-"BT@(" @(" @('1R:6%N9W5L87)?;6%T<FEX/%0L($8Q M+"!&,BP(a)03XZ.G9A;'5E7W1Y<&4(a)*#$I.PT**R @(" @(" @='EP96YA;64@ M=')I86YG=6QA<E]M871R:7@\5"P@1C$L($8R+"!!/CHZ=F%L=65?='EP92 H M,2D[#0H@#0H@(" @("\O(%1R:6%N9W5L87(@;6%T<FEX(&%D87!T;W(@8VQA E<W,-"B @(" @=&5M<&QA=&4\8VQA<W,@32P@8VQA<W,@1CX-"@`` ` end

1 0

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

02 Apr '04

> On Behalf Of E. Gladyshev > Sent: Friday, 2 April 2004 1:34 PM > To: boost(a)lists.boost.org > Subject: Re: [boost] Re: Policy or Trait? > > > From: "Hurd, Matthew" <hurdm(a)sig.com> > > [...] > > It would be nice if something new like "aspect class" or some such could > > Interesting name! I second your opinion in many ways. Would be nice to stop the confusion / confounding by describing somewhat rigorously a classification / nomenclature for "aspect classes". Constant aspects (bad name?, plain? simpleton?) - static constants and types only (bad name) Static aspect - constant aspect extended to include static methods Base aspect - intended to be inherited from by a client aka common MCD policy class - policy aspect perhaps? Chain aspect - not sure how to describe this Recurring base aspect - a base aspect that requires the first parameter to be the client class, this is the CRTP. Generic "blah" aspect - "blah" parameterised by additional template parameters beyond the client e.g. generic recurring base aspect is the CRTP with additional params A generic base aspect class would describe much of the MCD style policy classes. A static aspect could be used in a base aspect like manner or without the inheritance. "Aspect" might be inappropriate as I'm not 100% on my AOP nomenclature, but it feels appropriate. A trait or policy could be classified in such terms which might avoid some confusion. Needs some work, but it might start something... > I don't think that differentiating between traits and policy > makes too much sense or really necessary. > As for now to me, they both are parts of the same concept. > The idea is that a class can define an API > specification. The user is responsible > for implementing the API and supplying the implementation > to the class as a template parameter. > > Traditionally an API is not a set of just behaviors > or just data structures. It is a combination of both > and it doesn't have to be stateless. > > So what's so unique about API's from the OOP standpoint > especially. Well, an API as such cannot be > INSTANTIATED. It just EXISTs as a set of rules, etc. > It is like namespaces in C++. > You cannot instantiate a namespace! > You can instantiate data types defined by the API though. > > So to me, both traits and policies are sort of > interchangeable namespaces. > Perhaps my view is too simplistic. > > I sometimes do something like this > > template< typename MatrixApi > > struct equation_system_solver {...}; > > struct api > { > private: //** note private here > api(); > }; > > struct my_vector_api : api {...}; > > template< typename VectrorApi > > struct my_matrix_api : api {...}; > > equation_system_solver< my_matrix_api<my_vector_api> > s; Interesting. Especially handy I'd imagine if you use the CRTP with the api to give yourself some static polymorphism. Another pattern trait / policy style pattern I've used recently is having integer offsets and types associated with names in a type that represents a packet type, these "aspect classes" are combined with a packet type in a client to handle different financial exchanges in my case. This would be a "constant aspect" in my nomenclature above. It is a trait of a concept rather being a trait of a specific type or class. Gets interesting when one of those types in the constant aspect is a static aspect that describes operations on the type to be found at the offset indicated. The packet aspect is really nothing much more than a bunch integers and associated types and it feels like a trait (it is a trait of a concept); it is used like a policy. $0.002 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.

3 2

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

02 Apr '04

> On Behalf Of David Bergman > Sent: Friday, 2 April 2004 2:37 PM > To: boost(a)lists.boost.org > Subject: RE: [boost] Re: Policy or Trait? > > I wrote: > > > So, for me it is pretty easy, traits *only* describes > > Model-invariant parts of Concept Features while policies > > furnish Models of Concepts. > > Skipping all the GP stuff: traits DESCRIBE and policies ACT. Nice and simple. Gennadiy Rozental disagrees though. He gives the example of how to print something as a trait but this acts. A type in a trait could also be a description or reference of an action to take even more indirectly. To me the description of the action and the action is not clear cut. When describing the action is a level of indirection really necessary to make it a trait? I can see both cases... Matt Hurd. 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.

1 0

[boost-users] Re: [boost] [BGL] forced client complexity
by Cromwell Enage 02 Apr '04

02 Apr '04

prs, On reflection, I've decided to cross-list my reply. > If one accepts the axiom that "a picture is worth a > thousand words," then it naturally follows that > discussion of graphs is always overly prolix. I recently had a chat with a fellow programmer and attempted to summarize, in semi-layman terms, how the core algorithms of my multi-state-mazes library work. They're pretty simple, but I couldn't do it without paper and pencil. > Sadly, the same reasoning is also applicable to > the code of graph libraries. If a "code-visualizing compiler IDE" existed that would give us "code pictures" (plus conform to the new C++ standard, not ICE, and so on), I'm pretty sure more of us would be using it for all programming projects, not just graph applications. :) But seriously, with graph theory containing several different problem domains (search, network, AI, etc.), a graph library attempting to be generic enough for use in all of them is necessarily complex. > 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. :) The library does have a rather steep learning curve, especially if you're somewhat unfamiliar with graph theory and/or template programming. > Whereas libraries like Spirit go to great lengths > to make hard things easy, BGL seems to try only to > make hard things possible. I haven't looked at the Spirit library yet, so I can't tell you how easy it may be to use it. Perhaps getting your hands on a copy of the Boost Graph Library book will help (I don't have one, so I'm not certain). > 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? BGL aims to be as generic as the STL, but whereas each STL container deals with essentially one type of element, a graph needs to contain two types: a vertex type and an edge type. 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. BGL delegates some of the responsibility of property storage to the Boost Property Map Library. I'm just glad the developers kept the complexity down to its current level. > While I understand that the BGL is deeply entrenched > in boost culture, certain academic circles, and even > publications, I nonetheless suggest that BGL lacks > the ease of use necessary for widespread adoption. 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. > 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. > 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. > 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. > 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. > 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, 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. The same goes for g.find(); is it supposed to find a vertex, an edge, or both? Also, it seems you want to be able to use non-built-in or custom types as vertex IDs. You'll have to build your own custom-type-to-vertex map and bind it to the graph; BGL won't do it for you, to retain its genericity. Incidentally, BGL favors free functions over member functions. The rationale for that can be found in the FAQ <http://www.boost.org/libs/graph/doc/faq.html>. > Should I accept that the BGL is not the magic bullet > graph library and move on, or can this kind of > simplicity be somehow found within? Yeah, no magic bullets here. It depends on the problem you are trying to solve. Cromwell Enage __________________________________ Do you Yahoo!? Yahoo! Finance Tax Center - File online. File on time. http://taxes.yahoo.com/filing.html

2 1

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

02 Apr '04

Hellow, there. > Does anyone have an implementation of least common > ancestor (LCA) for the graph library? I could hack > something together to fit my needs, but it would be > nice if someone already did the work for me. I did a Java implementation a while back, if you're patient I'll convert it to C++, Boostify it, and put it in the Yahoogroups File Vault. > Thanks, > Walter Landry You're welcome. Cromwell Enage __________________________________ Do you Yahoo!? Yahoo! Small Business $15K Web Design Giveaway http://promotions.yahoo.com/design_giveaway/

2 1