October 2012 - Boost - lists.boost.org

[graph][heap][coroutine] interruptable dijkstra shortest path function
by Alex Hagen-Zanker 05 Oct '12

05 Oct '12

[apologies for double posting, send it to wrong list before] Hi, A few months ago I posted here to gauge interest for an interruptable and resumable version of the dijkstra_shortest_path algorithm. The initial response was positive, but Jeremiah considered the proposed solution lacking compared to an algorithm object model that inverts the control over the algorithm, Additional to my original solution, I now have two implementations of the algorithm object model. 1. Visitor based interruption. This is my original approach. It separates the algorithm into an init and main function. The main function asks the visitor if it should be halted afer each iteration. After halting, the main function can be used to resume the calculation. auto dijkstra = make_dijkstra_object(graph, named_parameters); dijkstra.init_from_sources(sources); dijkstra.expand( interruptor); dijkstra.expand( other_interruptor); auto distance_map = dijkstra.get<vertex_distance_t>(); auto color_map = dijkstra.get<vertex_color_t>(); 2. Algorithm object implementation. This was suggested by Jeremiah. The algorithm object iterates from control point to control point in the algorithm. Giving at each stop access to the intermediate results of the algorithm. The two implementations are: a) Using the [Coroutine] library that is currently under review to step in and out of the function. b) Fragmenting the function into many subfunctions that are chained together and the other works by fragmenting the original algorithm into a number of small interlinked functions starting at one control point and returning at the next. The interface of a and b is exactly the same and it works like this: auto dijkstra = make_dijkstra_object(graph, sources, named_parameters); while(dijkstra.next() ) { control_point cp = dijkstra.get_control_point(); vertex u = dijkstra.get_u(); auto distance_map = dijkstra.get<vertex_distance_t>(); if(cp == cp_finish_vertex && get(distance_map, u) > 42) { cout << "far enough" << endl; break; } } auto distance_map = dijkstra.get<vertex_distance_t>(); The algorithm object offers most flexibility for interweaving multiple searches. The visitor based solution on the other hand is more efficient. The latter has no loss in performance compared to the existing dijkstra functions. The coroutine algorithm object was extremely easy to implement but it is not very efficient. Does anybody have a suggestion how that can improve? Besides these interruptable and resumable shortest path searches, there are a few more advantages to the implementation. a. All dijkstra parameters are bundled in a light-weight dijkstra_state object that is returned by algorithms, giving direct access to all results of the algorithm, for instance: auto dijkstra_state = dijkstra_shortest_paths(graph, sources, no_named_parameters() ); auto distance_map = dijkstra_state.get<vertex_distance_t>(); b. Named parameters (old style) are also used for the priority queue and the color map c. Boost.Heap mutable queues can be used with Boost.Graph via the named parameter interface. It doesn't help performance now, but may be a good base for experimentation. d. Separation of the dijkstra shortest path algorithm in init and main function makes it easier to provide custom initialization. For instance: multiple sources or only re-initializing changed vertices Can anybody use this? The latest version is here: http://people.pwf.cam.ac.uk/ahh34/dijkstra.zip Kind regards, Alex p.s. below are timings for a large graph: bimba_6M.obj... 2090 ms. Boost Graph Library 2121 ms. With interruption visitor 5601 ms. With Coroutine(*) 2621 ms. With fragmented functions (*) 2840 ms. With Boost.Heap (*) halting at all control points of the dijkstra visitor

8 21

[chrono] bad use of constexpr (was: [1.52.0] Beta release candidates available)
by Eric Niebler 05 Oct '12

05 Oct '12

On 10/5/2012 8:56 AM, Lemay.Steve wrote: > Here's the first problem that pops up for me... QNXNTO gcc 4.7.1 > > qcc.compile.c++ D:\boostBuild_QCC_1_52_0_beta1\boost\bin.v2\libs\chrono\build\qcc\release\link-static\target-os-qnxnto\threadapi-pthread\threading-multi\chrono.o > In file included from ./boost/chrono/chrono.hpp:11:0, > from ./boost/chrono/detail/inlined/chrono.hpp:13, > from libs\chrono\src\chrono.cpp:14: > ./boost/chrono/duration.hpp: In static member function 'static constexpr float boost::chrono::detail::chrono_numeric_limits<float, true>::lowest()': > ./boost/chrono/duration.hpp:355:56: error: call to non-constexpr function 'static std::numeric_limits<float>::_Ty std::numeric_limits<float>::max()' > ./boost/chrono/duration.hpp: In static member function 'static constexpr double boost::chrono::detail::chrono_numeric_limits<double, true>::lowest()': > ./boost/chrono/duration.hpp:363:57: error: call to non-constexpr function 'static std::numeric_limits<double>::_Ty std::numeric_limits<double>::max()' > ./boost/chrono/duration.hpp: In static member function 'static constexpr long double boost::chrono::detail::chrono_numeric_limits<long double, true>::lowest()': > ./boost/chrono/duration.hpp:371:61: error: call to non-constexpr function 'static std::numeric_limits<long double>::_Ty std::numeric_limits<long double>::max()' > cc: d:/qnxsdk/qnxsdk6.5-001/host/win32/x86/usr/lib/gcc/i486-pc-nto-qnx6.5.0/4.7.1/cc1plus caught signal 1 > > "QCC" -Wc,-ftemplate-depth-128 -DFD_SETSIZE=2048 -march=k8-sse3 -mtune=k8-sse3 -mmmx -msse3 -mfpmath=sse -mno-3dnow -mstackrealign -Wc,-fPIC,-std=c++0x,-std=gnu++0x -O3 -Wc,-finline-functions -Wc,-Wno-inline -Wc,-Wall -DBOOST_ALL_NO_LIB=1 -DBOOST_All_STATIC_LINK=1 -DBOOST_SYSTEM_NO_DEPRECATED -DBOOST_SYSTEM_STATIC_LINK=1 -DNDEBUG -I"." -c -o "D:\boostBuild_QCC_1_52_0_beta1\boost\bin.v2\libs\chrono\build\qcc\release\link-static\target-os-qnxnto\threadapi-pthread\threading-multi\chrono.o" "libs\chrono\src\chrono.cpp" > > ...failed qcc.compile.c++ D:\boostBuild_QCC_1_52_0_beta1\boost\bin.v2\libs\chrono\build\qcc\release\link-static\target-os-qnxnto\threadapi-pthread\threading-multi\chrono.o... > common.copy D:\boost\include\boost\checked_delete.hpp > D:\boost_1_52_0_beta1\boost\checked_delete.hpp > 1 file(s) copied. > common.copy D:\boost\include\boost\chrono.hpp > D:\boost_1_52_0_beta1\boost\chrono.hpp > 1 file(s) copied. > qcc.compile.c++ D:\boostBuild_QCC_1_52_0_beta1\boost\bin.v2\libs\chrono\build\qcc\release\link-static\target-os-qnxnto\threadapi-pthread\threading-multi\process_cpu_clocks.o > In file included from ./boost/chrono/process_cpu_clocks.hpp:18:0, > from ./boost/chrono/detail/inlined/process_cpu_clocks.hpp:19, > from libs\chrono\src\process_cpu_clocks.cpp:17: > ./boost/chrono/duration.hpp: In static member function 'static constexpr float boost::chrono::detail::chrono_numeric_limits<float, true>::lowest()': > ./boost/chrono/duration.hpp:355:56: error: call to non-constexpr function 'static std::numeric_limits<float>::_Ty std::numeric_limits<float>::max()' > ./boost/chrono/duration.hpp: In static member function 'static constexpr double boost::chrono::detail::chrono_numeric_limits<double, true>::lowest()': > ./boost/chrono/duration.hpp:363:57: error: call to non-constexpr function 'static std::numeric_limits<double>::_Ty std::numeric_limits<double>::max()' > ./boost/chrono/duration.hpp: In static member function 'static constexpr long double boost::chrono::detail::chrono_numeric_limits<long double, true>::lowest()': > ./boost/chrono/duration.hpp:371:61: error: call to non-constexpr function 'static std::numeric_limits<long double>::_Ty std::numeric_limits<long double>::max()' > cc: d:/qnxsdk/qnxsdk6.5-001/host/win32/x86/usr/lib/gcc/i486-pc-nto-qnx6.5.0/4.7.1/cc1plus caught signal 1 For the record, I hit the same thing recently. In my case, it was a recently built clang that picked up an older libstdc++. The trouble is, just because a compiler supports constexpr doesn't mean the standard library does. Chrono doesn't seem to be making that distinction. It would be great to get this fixed for final release. -- Eric Niebler BoostPro Computing http://www.boostpro.com

1 0

Boost.Generic, C++0x Concepts, and C++1y Concepts
by Matt Calabrese 05 Oct '12

05 Oct '12

Hey everyone, It's been a while since I've made an appearance on this list, but I was contacted regarding the recent discussion of concepts here and Lorenzo's taking the reins of a concept library, and decided to poke my head in. First, I apologize to the community for not getting Boost.Generic on the sandbox earlier (if you are unfamiliar with Boost.Generic, see my 2011 BoostCon talk http://blip.tv/boostcon/boost-generic-concepts-without-concepts-5262126 and/or the corresponding slides https://github.com/boostcon/2011_presentations/raw/master/thu/Boost.Generic… ). I've gotten numerous emails about it since 2011 and I decided to commit the current state of Boost.Generic to the sandbox today. It is still based on the "old" concepts of C++0x with pseudo-signatures. You can find it in the "generic" subdirectory of the sandbox. That said, I'm not sure anyone even cares about Boost.Generic anymore given that the standard seems to be diverging from how it originally was approaching concepts, but here it is anyway. Similarly, I'm not sure there is any interest from people for me to continue developing Boost.Generic, so I guess this is a check for interest again. And, very briefly, without getting too political here (not that my opinion has any bearing) but I personally do not agree with some of the recent design changes for what may turn out to be C++1y concepts -- specifically I think pseudo-signatures were better overall and the C++0x form of associated types was much more useful than what is currently described, especially concerning associated type deduction, which no longer appears to be possible. But I don't think this discussion is suitable for the Boost mailing list and I don't want to ruffle too many feathers beyond that, so I'll take that elsewhere. For this reason, though, I [currently] do not have a desire to support that form of concepts in my library, though I do plan to resume work on Boost.Generic. A recap of what's gone on since my Boostcon talk, for anyone who even remembers it -- I haven't been actively developing Boost.Generic for over a year as I have been busy with other things, but coincidentally in the past couple of weeks I've gone back to it and decided to update some things due to a trick I realized I could use to get full compatibility with the C++0x working paper for explicit concept map templates (N2914's 14.10.3.2 paragraph 3 highlights why it's non-trivial, see http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2009/n2914.pdf) Since then, I've had renewed interest in the project and have updated various facilities. Stuff that changed since my presentation back in 2011 -- it now supports variadic concepts using the syntax ,,, (see line 28 of boost/generic/std_concept/concepts/predicate.hpp for a simple example). All 135 of the concepts from N2914 are now implemented, though not all are working, especially ones that are not auto and use refinement (I'm still in the process of making the concept map backend changes). All of the std_concepts/concepts tests should be working, and same with std_concept/support_concepts tests, with GCC and Clang only failing on FreeStoreAllocatable (in slightly different ways). I'm updating some of the implementation to use the new Boost.Preprocessor variadic macro support that didn't exist when I started development, and Boost.Generic now also is starting to use Edward Diener's variadic_macro_data_library that's in the sandbox. I've only recently test on GCC 4.7 and Clang 3.1, both with libstdc++ on Windows. I don't think any other compilers will be able to handle it because of the amount of C++11 features currently in use... Visual C++ in particular will likely have no chance of compiling ANY of it, even if you use the fully preprocessed form of the library that I provided on the sandbox. Specifically, I currently require the updated C++11 SFINAE support, variadic templates, and template aliases, among other features which I don't believe Visual C++ yet supports. If you want to see how to use the library, for now you'll have to watch the talk, look at the slides, and/or go into generic/test/libs/generic/test/std_concept and examine the tests that are there (the latter will probably be the most enlightening in terms of using the predefined concepts). As for the tests, the ones you should look at if you want to understand how to use the predefined concepts are in the test directory's std_concept/concepts and std_concept/support_concepts subdirectories. If you want to see the syntax for creating your own concepts, the ones in std_concept/concepts are the best choice to look at, as they are simple and most do not require compiler intrinsics, unlike the support_concepts which rely on C++11 type_traits and the C++0x std::True concept. I also recently integrated Boost.Wave support to easily generate preprocessed versions of all of the concepts in the library. You can use the preprocessed headers, including Dave's suggested #line support, without having to run Boost.Wave yourself. To do this you just define a couple of macros when you build the tests. This decreases build times by over 50% on both Clang and GCC -- the tests for me in Clang go from over 7 minutes to just over 3 minutes if I use the preprocessed headers. To activate this support you need the two defines in the following format (easiest to just define them via the command-line) // NOTE: Do not use quotes around the path -- also realize that the path ends in the middle of the word generic, This is necessary. #define BOOST_GENERIC_PREPROCESSED_ROOT put_your_COMPLETE_path_to_boost_sandbox_here/generic/include/boost/gen // Also #define BOOST_GENERIC_USE_PREPROCESSED_HEADERS This will use completely preprocessed concepts, with errors properly pointing to the non-preprocessed headers, and effectively gets rid of all of the "from macro invocation" notes you'd see in clang and gcc 4.8 whenever you hit one of the Boost.Generic generated static_asserts in the non-preprocessed form. It is recommended that you use the preprocessed form unless you are making changes to the library-provided concepts, since compile-times are greatly reduced by using them and error messages are improved. Anyway, as I said, I do not personally like the direction that concepts seem to be going and so I do not currently have much of an interest in implementing what is currently proposed, however, buried somewhere in the source of Boost.Generic I believe is an early implementation of the library that was more similar to how concepts are specified in N3351, though I stopped maintaining it a long time ago -- it allowed for the specification of givens and arbitrary expression matching similar to the current design, with a brief demonstration given in my 2011 Boostcon talk (slide 20: https://github.com/boostcon/2011_presentations/raw/master/thu/Boost.Generic…) It might be useful to revive this now that standard concepts may be going in that direction, but again, I do not think this is a good idea and was why I was convinced by others to switch development to pseudo-signatures to begin with. -- -Matt Calabrese

3 16

[Review Report] ODEInt accepted
by Steven Watanabe 04 Oct '12

04 Oct '12

AMDG The review of the ODEInt library submitted by Mario Mulansky and Karsten Ahnert ended last Friday. Many thanks to everyone who participated in this review. The library is ACCEPTED into Boost unconditionally. Summary: 7 ACCEPT 1 ABSTAIN Reviews: http://lists.boost.org/Archives/boost/2012/09/196733.php http://lists.boost.org/Archives/boost/2012/09/196882.php http://lists.boost.org/Archives/boost/2012/09/196883.php http://lists.boost.org/Archives/boost/2012/10/196966.php http://lists.boost.org/Archives/boost/2012/10/196965.php http://lists.boost.org/boost-users/2012/09/76089.php http://lists.boost.org/boost-users/2012/09/76058.php http://lists.boost.org/boost-users/2012/09/76069.php Other comments: http://lists.boost.org/Archives/boost/2012/09/196756.php The reviews were overwhelmingly positive. Most reviewers were satisfied with the library documentation and interfaces. Issues: These were points brought up by reviewers. The authors are free to accept or reject any of these at their discretion. - A number of minor documentation corrections. - Automatically deduce the correct algebra from the state type. - Use a default initial step size. - Allow breaking out of the algorithms In Christ, Steven Watanabe

2 1

Who maintains boost MPI?
by Ralf Grosse-Kunstleve 04 Oct '12

04 Oct '12

Hi, we're looking for someone to merge a simple patch: https://svn.boost.org/trac/boost/ticket/6123 Ralf

4 4

[release] permission to merge proto fix to release?
by Eric Niebler 04 Oct '12

04 Oct '12

I would like to merge the following changeset to release: https://svn.boost.org/trac/boost/changeset/80820 It's a bug fix for Proto that fixes a failing Phoenix test. The change is only 1 day old, but many of the Sandia testers have cycled already. OK to merge? -- Eric Niebler BoostPro Computing http://www.boostpro.com

2 1

[contract] SFINAE question for concepts
by Lorenzo Caminiti 04 Oct '12

04 Oct '12

Hello all, I have a SFINAE question. The following correctly returns false for eq1<x>::value when x has no operator== template< typename T > struct eq1 { T a; T b; template< typename TX > static char check ( TX a, TX b, char(*)[sizeof (std::is_convertible<decltype(a == b), bool>) ]); template< typename TX > static long check ( ... ); static const bool value = sizeof(char) == sizeof check<T>(a, b, 0); }; However, the following implementation that uses bool{a == b} incorrectly returns true for eq2<x>::value even if x has no operator==... why? BTW, if I just use (a == b) instead of bool{a == b} then it works... template< typename T > struct eq2 { T a; T b; template< typename TX > static char check ( TX a, TX b, char(*)[sizeof bool{a == b} ]); template< typename TX > static long check ( ... ); static const bool value = sizeof(char) == sizeof check<T>(a, b, 0); }; A complete example is attached. I'm using clang++ 3.2 with -std=c++0x. Thanks, --Lorenzo

2 3

[uuid] Merge changes to release
by Andrey Semashev 03 Oct '12

03 Oct '12

Hi, I've noticed that changeset https://svn.boost.org/trac/boost/changeset/80501 was not merged to release branch. The changeset removes a few warnings (including the ones about uninitialized variables) and fix tickets 7375 and 6118. The tests look good. Are these changes planned for 1.52?

3 2

[contract] static if instead of assertion requirements
by Lorenzo Caminiti 03 Oct '12

03 Oct '12

Hello all, I was reading the proposal to add "static if" to C++1x and I will use such a syntax for assertion requirements: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3329.pdf Current syntax for assertion requirements: postcondition( back() == value, requires boost::has_equal<T>::value ) Will be replaced with static if: postcondition( static if(boost::has_equal<T>::value) ( back() == value ) // optional else ( ... ) ) If there were interested, I could even provide a separate BOOST_STATIC_IF(const_condition, then_code, else_code)... however, such a macro could only be used at namespace and class scope, not a function scope :( --Lorenzo

2 2

Boost.Thread does not compile from trunk
by Jeremiah Willcock 02 Oct '12

02 Oct '12

It seems like <boost/thread/future.hpp> is missing an #include of <iostream> and produces errors about missing definitions of cout, etc. because of that. It looks like that is debugging code that may not have been intended to be committed. -- Jeremiah Willcock

2 1