- Boost - lists.preview.boost.org

[graph] non-recursive version of undirected_dfs
by Synge Todo 24 Nov '04

24 Nov '04

Dear Boosters, I'm posting a non-recursive version of undirected_dfs, which should have advantages in space and time over the current implementation based on recursion, especially for huge graphs. It's a direct counterpart of the non-recursive version of depth_first_search for digraphs. I have confirmed that libs/graph/example/undirected_dfs.cpp as well as my own programs using undirected_dfs reproduce the identical outputs as those with the original recursive version. Best regards, Synge *** boost/graph/undirected_dfs.hpp 6 Aug 2004 05:02:41 -0000 1.1.1.1 --- boost/graph/undirected_dfs.hpp 19 Aug 2004 05:11:32 -0000 1.2 *************** *** 28,38 **** --- 28,106 ---- #define BOOST_GRAPH_UNDIRECTED_DFS_HPP #include <boost/graph/depth_first_search.hpp> + #include <vector> namespace boost { namespace detail { + // Define BOOST_RECURSIVE_DFS to use older, recursive version. + // It is retained for a while in order to perform performance + // comparison. + #ifndef BOOST_RECURSIVE_DFS + + template <typename IncidenceGraph, typename DFSVisitor, + typename VertexColorMap, typename EdgeColorMap> + void undir_dfv_impl + (const IncidenceGraph& g, + typename graph_traits<IncidenceGraph>::vertex_descriptor u, + DFSVisitor& vis, + VertexColorMap vertex_color, + EdgeColorMap edge_color) + { + function_requires<IncidenceGraphConcept<IncidenceGraph> >(); + function_requires<DFSVisitorConcept<DFSVisitor, IncidenceGraph> >(); + typedef typename graph_traits<IncidenceGraph>::vertex_descriptor Vertex; + typedef typename graph_traits<IncidenceGraph>::edge_descriptor Edge; + function_requires<ReadWritePropertyMapConcept<VertexColorMap,Vertex> >(); + function_requires<ReadWritePropertyMapConcept<EdgeColorMap,Edge> >(); + typedef typename property_traits<VertexColorMap>::value_type ColorValue; + typedef typename property_traits<EdgeColorMap>::value_type EColorValue; + function_requires< ColorValueConcept<ColorValue> >(); + function_requires< ColorValueConcept<EColorValue> >(); + typedef color_traits<ColorValue> Color; + typedef color_traits<EColorValue> EColor; + typedef typename graph_traits<IncidenceGraph>::out_edge_iterator Iter; + typedef std::pair<Vertex, std::pair<Iter, Iter> > VertexInfo; + + std::vector<VertexInfo> stack; + + put(vertex_color, u, Color::gray()); + vis.discover_vertex(u, g); + stack.push_back(std::make_pair(u, out_edges(u, g))); + while (!stack.empty()) { + VertexInfo& back = stack.back(); + u = back.first; + Iter ei, ei_end; + tie(ei, ei_end) = back.second; + stack.pop_back(); + while (ei != ei_end) { + Vertex v = target(*ei, g); + vis.examine_edge(*ei, g); + ColorValue v_color = get(vertex_color, v); + EColorValue uv_color = get(edge_color, *ei); + put(edge_color, *ei, EColor::black()); + if (v_color == Color::white()) { + vis.tree_edge(*ei, g); + stack.push_back(std::make_pair(u, std::make_pair(++ei, ei_end))); + u = v; + put(vertex_color, u, Color::gray()); + vis.discover_vertex(u, g); + tie(ei, ei_end) = out_edges(u, g); + } else if (v_color == Color::gray()) { + if (uv_color == EColor::white()) vis.back_edge(*ei, g); + ++ei; + } else { // if (v_color == Color::black()) + ++ei; + } + } + put(vertex_color, u, Color::black()); + vis.finish_vertex(u, g); + } + } + + #else // BOOST_RECURSIVE_DFS + template <typename IncidenceGraph, typename DFSVisitor, typename VertexColorMap, typename EdgeColorMap> void undir_dfv_impl *************** *** 69,74 **** --- 137,145 ---- } put(vertex_color, u, Color::black()); vis.finish_vertex(u, g); } + + #endif // ! BOOST_RECURSIVE_DFS + } // namespace detail template <typename Graph, typename DFSVisitor,

2 2

[Boost-bugs] [ boost-Bugs-1072605 ] condition variables and recursive_mutex
by SourceForge.net 24 Nov '04

24 Nov '04

Bugs item #1072605, was opened at 2004-11-24 09:00 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=1072605&group_… Category: None Group: None Status: Open Resolution: None Priority: 5 Submitted By: Nobody/Anonymous (nobody) Assigned to: Nobody/Anonymous (nobody) Summary: condition variables and recursive_mutex Initial Comment: Hello - I've been working through the Boost.Threads example code, I'm new to the library, but i think i found a bug in the monitor.cpp example (boost_1_31_0/libs/thread/example/monitor.cpp) . When run using a recursive_mutex, the program hangs more often than not. It appears that the cuplrits are the calls to cond.wait(lk). For the recursive_mutex case, it appears that in some circumstances, these fall through without actually waiting for a change in the state of the lock lk. Attached is an example which is somewhat simpler that the one in monitor.cpp, but yields the same problem. Note that I'm compiling on a redhat ws3 system, with: Thread model: posix gcc version 3.2.3 20030502 (Red Hat Linux 3.2.3-42) and linking against libboost_thread-gcc-mt.so Typical output as given is: sent 100, received 100 sender waits 99, receiver waits 49944 I.e. close to 50k calls to cond.wait() in the receiver thread) When recompiling with "recursive_mutex" replaced by "mutex", the number of waits is on the order of the number of receives (i.e. in the range 0-100) Any help/insight is appreciated. Regards, Bill Moser billm(a)ll.mit.edu ---------------------------------------------------------------------- You can respond by visiting: https://sourceforge.net/tracker/?func=detail&atid=107586&aid=1072605&group_… ------------------------------------------------------- SF email is sponsored by - The IT Product Guide Read honest & candid reviews on hundreds of IT Products from real users. Discover which products truly live up to the hype. Start reading now. http://productguide.itmanagersjournal.com/ _______________________________________________ Boost-bugs mailing list Boost-bugs(a)lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/boost-bugs

1 0

Named params lib review
by Gennadiy Rozental 24 Nov '04

24 Nov '04

Hi, Recently I became quite fond of interfaces with named parameters. I developed variety of different solutions with different trade-off and set of features. At first here is couple notes from my experience: 1. In most cases multiargument interface are not in high performance critical areas. 2. In many cases it's constructors. Now lets delve in more detailed discussion on: Design =============== I. Active vs. passive I found that there are two major branched in designs for named parameters: "active" parameters collection and "passive" one. Submitted library is a variation of "passive" solution: one need to call "get" method to retrieve any parameter from collection: template<typename Params> void foo( Params const& p ) { std::string name = p[name]; std::string description = p[descr]; ... } An "active" solutions automatically place parameters in appropriate slots by single 'apply' call: class A { public: template<typename Params> A( Params const& p ) { p.apply( *this ); } }; Even though "active" solutions in some cases provide an interface look more natural. I found that "passive" solution in most cases more flexible and easier to implement. While in both cases one may employ runtime polymorphism, with "passive interfaces it's more natural. Note that parameter may not necessary is just a simple value, it maybe some kind of optional feature and 'apply' method maybe not so trivial and even invoke some functions. All in all both design seems to have heir advantages and I believe we need to provide support for both flavors. II Interfaces a) Call interface and parameters combining IMO with some very rare exclusions (1/2 optional parameter) the named parameter framework shouldn't require/expect multiple overloading of target function with different number of parameters. As well as any "impl" functions. The only acceptable interface is the one with single Params template parameters (in some cases one may provide positional interface as well, though it's rather exclusion case). This is applicable both to active and passive solutions: class A { A() : ... {} template<typename Params> A( Params const& p ) : m_name( p[name] ), m_gulp( p[gulp] ) {} }; This immediately bring a need for automatic arguments combining. There are several ways to do so, depending on requirements (BWT I liked interface presented in some other post with using ',' as combine operator). b) Optional parameter support In case of active solutions there should be an interface to check presence of specific argument. Submitted solution will cause compile time error on access to non-supplied parameter. This may not be always most convenient and may not be the case at all with different implementation (runtime based) c) Default value support I specifically dislike an interfaces provided to support default values. They are unreasonably cryptic (who would remember difference between | and ||; and why | ) but also misleading since default value is actually with access brackets: what is p["abc"]? There are several alternatives. My personal preference is : int name_ = p.is_present<name> ? p[name] : "abc"; // you will need some MP trick to make it compilable or int name_ = p.is_present( name ) ? p[value] : "abc"; // this assumes runtime based implementation Active solutions doesn't have such issue. Whatever is there gets set by apply call. d) Type safety and restrictions I do not understand why wouldn't we keep data type somewhere around keyword type and require one to supply specific type during invocation.This library instead invented special mechanism of imposing restrictions. I do not believe we need that (Also my guess is that 8 out of 10 developers unfamiliar with library will be left spellbound facing this code) e) Mix of named and positional parameters I don't believe it's actually a good idea to support such mix. IMO it just adding unnecessary confusion and possible source of users errors.. Let's say I expect 2 parameters: 1. string name 2. int value. call foo( value = 5, "my_name" ) will fail, while foo( "my_name", value = 5 ) and foo( value = 5 ) won't. Too much chances to make mistake IMO. III. Implementation IMO whatever design you prefer implementation shouldn't as complex and cumbersome. Named parameters support is pretty simple task. This submission presents 1000 lines of tight MP code (and this is without numerous includes). In majority of the cases much more simple and straightforward solution is possible (with some acceptable IMO tradeoff). Following 80 lines (I think it's possible to make it even smaller would I use mpl) should basically present solution with similar tradeoff as submitted library (without default value support, but IMO it would take another 40-60 lines, just save it into keyword struct): // Library Code template<typename NP1,typename NP2> struct named_parameter_combine; template<typename T, int unique_id> struct keyword; template<typename Derived> struct named_parameter_base { template<typename NP> named_parameter_combine<NP,Derived> operator,( NP const& np ) { return named_parameter_combine<NP,Derived>( np, *static_cast<Derived*>(this) ); } }; template<typename T, int unique_id> struct named_parameter : named_parameter_base<named_parameter<T, unique_id> > { static const int id = unique_id; named_parameter( T const& v ) : m_value( v ) {} T const& operator[]( keyword<T,unique_id> const& ) const { return m_value; } T const& m_value; }; template<bool> struct selector; template<typename NP1,typename NP2> struct named_parameter_combine : named_parameter_base<named_parameter_combine<NP1,NP2> > { named_parameter_combine( NP1 const& np1, NP2 const& np2 ) : m_np1( np1 ), m_np2( np2 ) {} template<typename KW> typename KW::data_type const& operator[]( KW const& kw ) const { return selector<KW::id==NP1::id>::_( m_np1, m_np2, kw ); } NP1 const& m_np1; NP2 const& m_np2; }; template<> struct selector<true> { template<typename NP1,typename NP2,typename KW> static typename KW::data_type const& _( NP1 const& np1, NP2 const& np2, KW const& kw ) { return np1[kw]; } }; template<> struct selector<false> { template<typename NP1,typename NP2,typename KW> static typename KW::data_type const& _( NP1 const& np1, NP2 const& np2, KW const& kw ) { return np2[kw]; } }; template<typename T, int unique_id> struct keyword { typedef T data_type; static const int id = unique_id; named_parameter<T,unique_id> operator=( T const& t ) const { return named_parameter<T,unique_id>( t ); } }; //////////////////////////////////////////////////////////////// // Example: namespace test { typedef char const* c_str; keyword<c_str,1> name; keyword <float,2> value; keyword<int,3> index; double value_default() { return 666.222; } int foo( c_str name, float v, int i ) { } template<class Params> int foo(Params const& params) { foo( params[name], params[value], params[index] ); } } int main() { using test::foo; using test::name; using test::value; using test::index; foo(( index = 20, name = "foo", value = 2.5 )); return 0; } Strict type checking on top of it. This code works under gcc 3.4.2. Should work everywhere. As you may guess by now my vote is NO to accept this library. I personally wouldn't be using it in current form and IMO as it stands now it's just another collection of neat MP tricks. I do not have to much comments on docs and tests, other then they seems incomplete. Regards, Gennadiy P.S. Why is the RC branch of mpl is different from HEAD? Doesn't we supposed to fix HEAD and only then propagate to branch?

9 45

RE: [boost] Re: Boost Sandbox layout?
by Stefan Seefeld 24 Nov '04

24 Nov '04

> From: Vladimir Prus [mailto:ghost@cs.msu.su] > I really wish there were a version control system with symlinks in > repository. Apparently subversion 1.1 support that: http://svnbook.red-bean.com/en/1.1/svn-book.html Regards, Stefan

1 0

how does one remove vertices from a graph
by Eyal Farago 24 Nov '04

24 Nov '04

adjacency_list documentations refers to 'stability' problems of vertex descriptors and iterators. it also provides two wrong and one correct ways to remove all vertices from a graph, trying to use the 'correct' way produced an exception from within vector::erase. after looking into the state of the iterators I understand that the 'correct' example isn't correct at all, the iterators still refers to the original offsets in the vertices vector when the current vertex is erased from the graph. i.e. suppose the graph had 7 vertices to begin with and we've already erased the first one, the iterator to current (vi in the example) should point to offset 0 and the end iterator(vi_end in the example) should point to offset 6, instead we have iterators to offsets 1 and 7. am I right? if so, what is the correct way to do it? eyal.

2 1

[graph] Why is there no boost::multimapS?
by David M. Jones 24 Nov '04

24 Nov '04

Hi all, I have a case where I'd like to create an adjacency_list whose edge container is a multimap. When I look through the boost files, I find boost::mapS and boost::multisetS so I don't see any obvious reason why there is no boost::multimapS. Thanks in advance, David

2 1

Serializing a variant
by Richard Peters 24 Nov '04

24 Nov '04

Hello, I'm looking for a way to serialize a variant. I see two possibly difficult things that I don't know how to accomplish: 1) In order to be able to retrieve a variant from an archive, the type of the value held by the variant must be stored. 2) When retrieving the data from an archive, once the type is read, a value of that type must be extracted from the archive and assigned to the variant. Has anybody tried this before, is this as difficult as it looks? Any help would be greatly appreciated. best regards, Richard Peters

5 6

Boost 1.32 vs. tru64cxx65
by Richard Hadsell 24 Nov '04

24 Nov '04

I'm trying to build some of the Boost libraries for the tru64cxx65 toolset. It seems that a header is missing from my compiler (Compaq C++ V6.5-030 for Digital UNIX V4.0F). This kind of error is showing up in a lot of code, since it seems to be a problem in a basic Boost header: cxx: Error: /tmp_mnt/netDISKS/cgi/DIGITAL6/cgi/vendor/library/boost/boost_1_32_0/boost/cstdint.hpp, line 87: #5 could not open source file "inttypes.h" # include <inttypes.h> ----------------------^ cxx: Error: /tmp_mnt/netDISKS/cgi/DIGITAL6/cgi/vendor/library/boost/boost_1_32_0/boost/cstdint.hpp, line 91: #282 the global scope has no "int8_t" using ::int8_t; ----------^ cxx: Error: /tmp_mnt/netDISKS/cgi/DIGITAL6/cgi/vendor/library/boost/boost_1_32_0/boost/cstdint.hpp, line 92: #20 identifier "int8_t" is undefined typedef int8_t int_least8_t; ----------^ ... cxx: Info: 27 errors detected in the compilation of "/tmp_mnt/netDISKS/cgi/DIGITAL6/cgi/vendor/library/boost/boost_1_32_0/libs/filesystem/build/../src/convenience.cpp". cxx -c -timplicit_local -ptr "bin/boost/libs/filesystem/build/libboost_filesystem.so/tru64cxx65/release/cxx_repository" -noimplicit_include -D__USE_STD_IOSTREAM -nousing_std -msg_display_number -msg_disable 186,450,1115 -DNDEBUG -DNDEBUG -DBOOST_FILESYSTEM_DYN_LINK=1 -O2 -model ansi -I"bin/boost/libs/filesystem/build" -I"/tmp_mnt/netDISKS/cgi/DIGITAL6/cgi/vendor/library/boost/boost_1_32_0" -I"/usr/include" -I"/tmp_mnt/netDISKS/cgi/DIGITAL6/cgi/vendor/library/boost/boost_1_32_0" -o "bin/boost/libs/filesystem/build/libboost_filesystem.so/tru64cxx65/release/convenience.o" "/tmp_mnt/netDISKS/cgi/DIGITAL6/cgi/vendor/library/boost/boost_1_32_0/libs/filesystem/build/../src/convenience.cpp" -- Dick Hadsell 914-259-6320 Fax: 914-259-6499 Reply-to: hadsell(a)blueskystudios.com Blue Sky Studios http://www.blueskystudios.com 44 South Broadway, White Plains, NY 10601

4 10

RE: [boost] Thread: Why is my prog aborting after 283 or so threads?
by Tim Laplaca 24 Nov '04

24 Nov '04

I switched the parameter-passing to the bind method, e.g. thrds.create_thread( boost::bind( updatethread, threadid, "123456789" ) ); with no difference. I did find that the same code that "aborts" under Linux seems to run ok under Windows. -----Original Message----- From: boost-bounces(a)lists.boost.org [mailto:boost-bounces@lists.boost.org] On Behalf Of Tim Laplaca Sent: Tuesday, November 23, 2004 3:32 PM To: boost(a)lists.boost.org Subject: [boost] Thread: Why is my prog aborting after 283 or so threads? I wrote a prog that spawns threads (RED HAT Fedora Core 2), and after spawning 283 or so threads, it stops running and 'Aborted' is printed. It doesn't matter if I spawn them one after each other, or only 10 at a time, or if the threads only last 1 second or if they all stick around until the 283rd thread is spawned. Every combination I've tried results in the prog aborting at about the 283rd thread spawn. Does this sound familiar to anybody? Is there something my thread must do to properly shut itself down? Does it need to call some kind of procedure to announce it is going away for proper cleanup? I couldn't see anything in the examples like that. And is there documentation explaining the examples? I failed to find any. My thread procedure: void updatethread(void* inparams) { thread_params *tparam; tparam=(thread_params *)inparams; int local_threadid = tparam->param1; std::string DID = tparam->param2; { boost::mutex::scoped_lock scoped_lock(io_mutex); std::cout << " Thread:" << local_threadid << " running. " "UPDATE for " << DID << std::endl; } // wait some secs (just for debug, remove when real work is being done) boost::xtime xt; boost::xtime_get(&xt, boost::TIME_UTC); xt.sec += 2; boost::thread::sleep(xt); { boost::mutex::scoped_lock scoped_lock(io_mutex); std::cout << " Thread:" << local_threadid << " Exiting. " << std::endl; } { boost::mutex::scoped_lock scoped_lock(numthreads_mutex); --activethreads; } } MAIN calls it with this: //spawn thread tparam.param1=threadid; tparam.param2=dids[i]; boost::thread *pt; pt = thrds.create_thread(thread_adapter(&updatethread, (void*)&tparam)); Thanks, Tim _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

1 0

Another logo proposal
by Joaquín Mª López Muñoz 24 Nov '04

24 Nov '04

Here's my take. I'm providing b/w and color versions. The idea is to provide an abstract logo to associate with Boost while retaining the visual link with the previous artwork (through using the same Impact font for the name, a very appropriate font IMHO.) Some more rationales behind the proposal: * It can be easily rasterized. * It goes well with flat backgrounds. * It works as a transition from the old logo. As for the logo itself, it tries to convey the following connotations: * Its square shape, and the fact that is bottom aligned with the text, gives a sense of solidness. * It reminds the reader of a set of construction toolkit pieces, which associates well with Boost being a repository of general purpose libraries. * The "++" part of C++ is retained, integrated into the logo. Going a little pedantic, one can even recognize the logo as a deconstruction of "C++", where the L-shaped pieces are the two halves of an upper "C", split and shifted. Dya like it? Joaquín M López Muñoz Telefónica, Investigación y Desarrollo

15 23