April 2013 - Boost - lists.preview.boost.org

Re: [boost] GSoC 2013 : Implementing Dynamic Programming Algorithms
by Aman Gupta 09 Apr '13

09 Apr '13

Hi, Thanks for the reply. The first thing I want to implement is a Integer-Knapsack problem which takes in a precision error(i.e. an epsilon which is a indicator of the allowed error in the input) The input parameters are Weights, Values and the error. The first thing to do is massage the values according to the error (e.g. if the value is ~10^4 divide it down to ~10^3 according to the error) then run the a dynamic programming algorithm, which has a running time of O(n^3/e) (n : number of items, e :error) Hence, an arbitrarily close approximation is possible with a running time trade-off. Also, a vanilla variety of the knapsack problems(with small instances) which gives the optimal solution can also be implemented. I also want to implement the assignment problem, which also arises in a lot of situations in real life ( http://en.wikipedia.org/wiki/Assignment_problem) using the Hungarian Algorithm. I realize this requires effort but I'm really interested in adding a feature to the boost library. Regards, Aman Gupta

1 0

GSoC 2013 - Boost registration?
by Paul A. Bristow 09 Apr '13

09 Apr '13

http://www.google-melange.com/gsoc/events/google/gsoc2013 March 18: 19:00 UTC Mentoring organizations can begin submitting applications to Google. March 29: 19:00 UTC Mentoring organization application deadline. Just checking that Boost has/is registering? Paul --- Paul A. Bristow, Prizet Farmhouse, Kendal LA8 8AB UK +44 1539 561830 07714330204 pbristow(a)hetp.u-net.com

3 3

GSoC 2013 : Implementing Dynamic Programming Algorithms
by Aman Gupta 09 Apr '13

09 Apr '13

Hi, I am Aman Gupta from BITS-Pilani India, I am a 4th year Undergraduate Student majoring in Computer Science. I've noticed that boost does not contain dynamic programming algorithms like Integer-Knapsack, Longest Common Sub-sequence. I was thinking that implementing this would be a good project. I realize most of these problems are non-polynomial in complexity but I was thinking implementing them to a certain size will not be problem. Also, since some of the dynamic programming algorithms have alternate greedy algorithms which compromise on correctness but are faster, implementing those can be useful. The knapsack problem(which comes in a lot of situations) for which there exists an algorithm which gives an arbitrarily close approximation to the optimal value can be implemented. ( e.g. f(weights,values,error) could be the function, the user has a trade-off between error and computation time). I think it could be useful in situations where the user just decides the error he wants or perhaps how fast he wants his computation. Please let me know if this seems like a valid project idea to you! Thanks, Aman Gupta

2 1

[move] move's is_convertible does not compile with aligned data
by Tobias Loew 09 Apr '13

09 Apr '13

The implementation of move's is_convertible-type has the same problems on MSVC with aligned types as reported for type_trait's is_convertibale in Ticket #5271 https://svn.boost.org/trac/boost/ticket/5271 As type_trait's implementation has been fixed, a simple solution would be letting the user (and not the code in move.hpp:41) [not] define BOOST_MOVE_AVOID_BOOST_DEPENDENCIES regards Tobias -- View this message in context: http://boost.2283326.n4.nabble.com/move-move-s-is-convertible-does-not-comp… Sent from the Boost - Dev mailing list archive at Nabble.com.

2 2

boost/thread.hpp UBICOM processor
by Aswin Paranji 09 Apr '13

09 Apr '13

Hi, I'm trying to compile boost library 1.53 using the ubicom toolchain provided by our embedded partner. During compilation of the boost library there was a linker error (_sync_fetch_add). This was overcome by adding define statement BOOST_SP_USE_PTHREADS, along with FENCED in user-config.hpp. The application was linked properly. Running the application within the embedded box exits with a segmentation fault happening before printing the first line of the main function. This was narrowed down to boost/thread.hpp header. Removing the header allows the application to print the first line and return. The problem I have is, I do not have GDB/GDBServer to assist me. Also, i could not use back_trace as the toolchain does not have the necessary header files. Can anyone tell me what might be causing the problem. I'm sure there is some sort of conflict between the processor architecture with thread or the toolchain which was used to compile boost. The GCC version is 4.4.1 Appreciate if someone can help me on this. Thanks, Aswin Paranji

2 2

[phoenix] doesn't compile with gcc 4.9 snapshot
by Nathan Ridge 08 Apr '13

08 Apr '13

Hi, I'm trying to compile some code that uses Boost with a GCC 4.9 snapshot, but something seems to be going badly wrong. Something as simple as a file containing the include: #include <boost/phoenix/core.hpp> fails to compile, with the following errors: In file included from boost/proto/matches.hpp:42:0, from boost/phoenix/core/domain.hpp:12, from boost/phoenix/core/actor.hpp:17, from boost/phoenix/core.hpp:15, from test.cpp:1: boost/proto/traits.hpp: In instantiation of 'struct boost::proto::tag_of<boost::proto::_>': boost/phoenix/core/domain.hpp:25:18: required from here boost/proto/traits.hpp:241:42: error: no type named 'proto_tag' in 'struct boost::proto::_' typedef typename Expr::proto_tag type; ^ In file included from boost/phoenix/core/argument.hpp:15:0, from boost/phoenix/core.hpp:17, from test.cpp:1: boost/phoenix/core/terminal.hpp: In instantiation of 'struct boost::phoenix::detail::placeholder_idx<boost::proto::make<boost::is_placeholder<boost::proto::_value>()> >': boost/phoenix/core/terminal.hpp:122:18: required from here boost/phoenix/core/terminal.hpp:115:16: error: 'value' is not a member of 'boost::proto::make<boost::is_placeholder<boost::proto::_value>()>' struct placeholder_idx ^ The exact same code compiles fine with GCC 4.8 and earlier. Any ideas as to what might be going wrong? Thanks, Nate

1 1

Boost.Graph for GSoC
by Daniel Mitchell 08 Apr '13

08 Apr '13

Hi all, I'm a researcher and graduate student at the University of Texas at Austin and I'm interested in doing a Boost.Graph project for GSoC. I was thinking of doing one or more planar graph algorithms, in particular the multiple source shortest paths algorithm for planar graphs described at http://courses.csail.mit.edu/6.889/fall11/lectures/L11.html The algorithm assumes that the sources are located on a single face. It proceeds by calculating the shortest paths tree from one source and then minimally modifying the tree to efficiently get the shortest paths from the other sources. The algorithm uses a dynamic tree data structure, so developing that data structure would be part of the project too. I've made prior contributions to BGL. I worked with Doug Gregor to implement color maps for the breadth first and Dijkstra's algorithms. One of my current areas of research is movement ecology, where planar graphs can be used to study movement. Let me know what you think. Daniel Mitchell

3 4

[container] stable_vector::back() is broken in Boost 1.53
by Klaim - Joël Lamotte 08 Apr '13

08 Apr '13

Tested on both VS2010 and VS2012, boost 1.53, with default boost no option set: ############ #include <boost/container/stable_vector.hpp> #include <iostream> int main() { boost::container::stable_vector< int > values; values.emplace_back( 42 ); int& bad_value = values.back(); // bad address int& good_value = values.front(); int& also_good_value = values.at(0); // imply values[0] std::cout<< " ADDRESS OF BAD VALUE : " << &bad_value << std::endl; std::cout<< " ADDRESS OF GOOD VALUE : " << &good_value << std::endl; std::cout<< " ADDRESS OF ALSO GOOD VALUE : " << &also_good_value << std::endl; } ############ This code displays addresses of the bad_value object very low on Debug and very high on Release. I believe that .back() is broken. However, when I test there : http://liveworkspace.org/code/3F11CK$2 it seems to work with any available compiler. So either it's LiveWorkspace which use an older boost version, or this issue arise only on VC. I made a ticket: https://svn.boost.org/trac/boost/ticket/8412 Joel Lamotte

6 10

GSoC 2013: Boost is a mentoring organization
by Boris Schaeling 08 Apr '13

08 Apr '13

Boost is a mentoring organization in this year's GSoC program. Thanks to everyone who added proposals to <https://svn.boost.org/trac/boost/wiki/SoC2013> and to Google for inviting us! According to the GSoC calendar at <https://google-melange.appspot.com/gsoc/events/google/gsoc2013> we have now two weeks where would-be student participants discuss application ideas. If you are interested in participating in the program - either as a student or as a mentor - get active now! :) 1) Have a look at our ideas list at <https://svn.boost.org/trac/boost/wiki/SoC2013>. Find something which interests you or think of a brand new project. 2) Send a mail to the mailing list at <mailto:boost@lists.boost.org> to let people know what you are interested in and what you have to offer. 3) Discuss your idea with others and try to turn it into an actual GSoC project. You need at least a project description, a goal, a mentor and a student. :) Boris

1 0

Adding some image libs to boost build
by Christian Henning 08 Apr '13

08 Apr '13

I have added jpeg, png, and tiff jam files to boost trunk. These files will be needed by gil::io tests. There are still some remaining issues which I like to discuss in this thread: 1. building these libs sometimes requires renaming header and/or source files to the correct architecture. Should we leave that up to the user or should bjam take care of it. And if so, how will we configure that. One example is jpeg: see jconfig.vc -> jconfig.h 2. Tiff has a file nmake.opt which is included in the makefile. How will we include all those options? Regards, Christian

3 5