April 2004 - Boost - lists.boost.org

Re: [boost] Re: Formal Review: Indexed Set
by JOAQUIN LOPEZ MU?Z 04 Apr '04

04 Apr '04

----- Mensaje original ----- De: Jeremy Maitin-Shepard <jbms(a)attbi.com> Fecha: Jueves, Abril 1, 2004 8:35 pm Asunto: Re: [boost] Re: Formal Review: Indexed Set > I believe you should leave in the support for multiple tags per index. > Possible use cases include: > > - Including the key type as an index tag. > > - Using tags to flag various fields for some other algorithm -- in > this case, different fields could be flagged for use by various > different algorithms. If I'm understanding you, the case use you propose could be illegal. Do you mean something like: indexed_set< int, index_list< unique<tag<first,marked>,...>, non_unique<tag<second>,...>, non_unique<tag<third,marked>,...> > > So that "marked" can be taken advantage of by some algorithm? If so, this clashes with a request by Brian McNamara that duplicate tags be not allowed. If you mean something else, I'd appreciate if you could ellaborate. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo

2 1

[Boost-bugs] [ boost-Bugs-929094 ] patch for boost::filesystem
by SourceForge.net 04 Apr '04

04 Apr '04

Bugs item #929094, was opened at 2004-04-04 04:17 Message generated for change (Tracker Item Submitted) made by Item Submitter You can respond by visiting: https://sourceforge.net/tracker/?func=detail&atid=107586&aid=929094&group_i… Category: None Group: None Status: Open Resolution: None Priority: 5 Submitted By: Carlo Wood (libcw) Assigned to: Nobody/Anonymous (nobody) Summary: patch for boost::filesystem Initial Comment: /usr/local/include/unit++.h: In member function `virtual void unitpp::exception_test<E>::operator()()': /usr/local/include/unit++.h:163: error: there are no arguments to `fail' that depend on a template parameter, so a declaration of `fail' must be available /usr/local/include/unit++.h:163: error: (if you use `-fpermissive', G++ will accept your code, but allowing the use of an undeclared name is deprecated) Patch attached. ---------------------------------------------------------------------- You can respond by visiting: https://sourceforge.net/tracker/?func=detail&atid=107586&aid=929094&group_i… ------------------------------------------------------- This SF.Net email is sponsored by: IBM Linux Tutorials Free Linux tutorial presented by Daniel Robbins, President and CEO of GenToo technologies. Learn everything from fundamentals to system administration.http://ads.osdn.com/?ad_id=1470&alloc_id=3638&op=click _______________________________________________ Boost-bugs mailing list Boost-bugs(a)lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/boost-bugs

1 0

Proposed change to license references
by David Abrahams 03 Apr '04

03 Apr '04

Given recent advice from Diane Cabell, director of Harvard's Berkman Center for Internet and Society, I propose we change the way that boost source files refer to the bost license from: // Use, modification, and distribution is subject to the Boost Software // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy // at http://www.boost.org/LICENSE_1_0.txt) to: // Distributed under the Boost // Software License, Version 1.0. (See accompanying file // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) The earlier license reference, by referring explicitly to "use, modification, and distribution", legally excludes important issues like "display", which are covered by the license itself and are intended to apply to source files. I'm posting this now to give people a chance to come up with any other issues -- **with the license reference comment**, not the license itself -- that may need to be addressed before we make a change. If there are no new issues within a week or so, we'll make it official. -- Dave Abrahams Boost Consulting www.boost-consulting.com

8 13

Suggestion: link to the libraries page not easy to find
by Marcello Pietrobon 03 Apr '04

03 Apr '04

Hi Boost team, I don't know where to put this suggestion. Even if boost is now well known, I think in the boost's home page there should be a well visible, easy to find, link to http://www.boost.org/libs/libraries.htm because this is exactly what boost is about, I think. Best Regards, Marcello

5 12

Another mailing list description?
by Daryle Walker 03 Apr '04

03 Apr '04

Would anyone that runs the mailing list at <Boost-langbinding(a)lists.sourceforge.net> like to give a description about what that list is about so you (or me if you don't have CVS-write access) can add it to "BOOST_ROOT/more/mailing_lists.htm"? I was going to add it myself, but I can't gleam enough information for a description blurb. -- Daryle Walker Mac, Internet, and Video Game Junkie darylew AT hotmail DOT com

2 1

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