November 2011 - Boost - lists.boost.org

Re: [boost] BGL CSR Format (logarithmic edge search)
by Ryan Lichtenwalter 21 Nov '11

21 Nov '11

> Hello, > > According to: > > http://www.boost.org/doc/libs/1_48_0/libs/graph/doc/compressed_sparse_row.h… > > [Edge search] requires linear time in the number of edges outgoing from u. > > The purpose of the CSR format is to support highly efficient computation > with minimal memory requirements at the cost of mutability and additional > time in construction. Is there a reason, then, that the adjacencies are > stored unsorted within their vertex ranges? With minimal additional time > during construction, edge access could be reduced to logarithmic time in > the number of edges outgoing from u without sacrificing any functionality > elsewhere that I can determine. > > Can somebody explain this design decision to me? If there is no > explanation, does anybody have plans to adjust the representation? I would > probably be willing to contribute an adjusted representation if nobody else > has plans to do so. The edges from each vertex used to be sorted, but that was changed when linear-time graph construction was introduced. One problem is that the standard sorting routines cannot sort corresponding ranges of elements (such as edge targets and properties); also, sorting edges increases the time complexity of the graph construction algorithm. Note that the CSR constructors that do sorting, except for the in-place versions, apply stable sorts to the edges you input, so you could give it a sorted list of edges and then write a logarithmic-time search routine using out_edges(). -- Jeremiah Willcock Hi, Thanks for your response. I'm sorry to hear about the move away from sorted adjacencies. I'm not sure if this is open for discussion, but I'd like to offer my two cents. The construction cost (of sorting) is minimal, especially in sparse networks for which the compressed sparse row format is specifically targeted where it is essentially asymptotically constant-time unless the degree distribution is highly skewed. On the other hand, certain aspects of link prediction, subgraph counting, and any algorithm that requires neighbor set intersections will benefit greatly from the ordering. I actually rolled exactly the solution you suggested for my own needs. Thank you so much. Ryan Lichtenwalter

1 0

Re: [boost] [optional] std::tr2::optional
by Andrzej Krzemienski 21 Nov '11

21 Nov '11

> > Interesting. It looks like optional can be seen as a special container with > > the maximum size of 1, and then functions like clear() or empty() come as > > natural. On the other hand it can be seen as a pointer-like entity with > > value semantics, and then functions like reset() and literal nullptr come > > as natural. > > Ok, I have no strong preference between reset() or clear() for making the > optional empty. However, a explicit empty() member would be useful anyway. > class MyClass > { > optional< int > m_x; > public: > bool has_x() const { return !m_x.empty(); } > }; > With the current interface I should have written has_x() in a more obscure > way, like !!m_x or m_x.get_ptr() != NULL. > > I withdraw my suggestion to use nullptr. Function reset() would be a better > > choice. I also find reset() preferable to clear() because reset can be > > extended to accept parameters and the name does not become confusing; > > similarly to unique_ptr::reset(). > I think, providing the reset() member with construction semantic is not a good > idea because it would make imposible in-place default construction. There > should be another method that would handle construction. In another post I > suggested assign() but I'm happy if someone comes up with a better name. I managed to come up with the following interface for initializing and un-initializing. My goal was also to not introduce in-place factories. template< typename... Args > optional( tr2::in_place_t, Args &&... args ) noexcept( noexcept(T{std::forward<Args>(args)...}) ) the first parameter is a /tag/, much like std::piecewise_construct for pairs. We use it like this: tr2::optional<W> { tr2::in_place, i, str, 1, &g }; The tag indicates that we request an 'in place' initialization of W with remaining arguments.Next functions are more natural: template< typename... Args > void initialize( Args &&... args ) noexcept( noexcept(T{std::forward<Args>(args)...}) ) // for deferred initialization. void uninitialize() noexcept // so that it spells similar to 'initialize' bool is_initialized() const noexcept // as in boost Regards, &rzej

3 2

BGL CSR Format (logarithmic edge search)
by Ryan Lichtenwalter 21 Nov '11

21 Nov '11

Hello, According to: http://www.boost.org/doc/libs/1_48_0/libs/graph/doc/compressed_sparse_row.h… [Edge search] requires linear time in the number of edges outgoing from u. The purpose of the CSR format is to support highly efficient computation with minimal memory requirements at the cost of mutability and additional time in construction. Is there a reason, then, that the adjacencies are stored unsorted within their vertex ranges? With minimal additional time during construction, edge access could be reduced to logarithmic time in the number of edges outgoing from u without sacrificing any functionality elsewhere that I can determine. Can somebody explain this design decision to me? If there is no explanation, does anybody have plans to adjust the representation? I would probably be willing to contribute an adjusted representation if nobody else has plans to do so. Thanks! Ryan Lichtenwalter

2 1

Re: [boost] [optional] std::tr2::optional
by Andrzej Krzemienski 21 Nov '11

21 Nov '11

> > Also, if someone likes the assignment-of-"none" syntax, in C++11 there will > > be a similar syntax available: > > std::tr2::optional<T> op = {}; > > op = {}; > Wouldn't that be confusing with creating a filled optional with the value > constructed with empty initialization list? If there is assignment-of-none > syntax, it should probably be more explicit, pretty much like the current > "none" keyword. I see your point. But note that this confusing syntax will still be available (and is available today on compilers that support the new initialization syntax) even if we have "none" keyword. This is just the new way of requesting value-initialization (default constructor). Personally, I have doubts about introducing entity "none". There would be too many ways of indicating the null-state for different types. You could look at nullptr as a special pointer with special value; but you could also think of it as a keyword for indicating null-state: a stet of not having any meaningful value. Pointers represent addresses: they can either represent a valid address or not-an-address. Now for optionals we will have none for not-a-value, even though it is almost the same concept. I was thinking also about null_value or nullval. But they appear even more confusing than an already familiar "none". I am not English speaker, so I cannot be positive about it, but does "none" fit logically into the context? Is "nothing" or "naught" more suitable, gramatically? Regards, &rzej

1 0

Re: [boost] [local] Review (and resignation from review assistant)
by Andrzej Krzemienski 21 Nov '11

21 Nov '11

> > - What is your evaluation of the design? > The library is very well designed. The function declaration syntax looks a little foreign at first, but it is very easy to get used to. Furthermore, error messages are usually able to point you to what you did wrong. The fact that you can write the body of the function in plain C++ code is a major advantage of this library. Some have referred to Boost.Bind, Boost.Lambda and Boost.Phoenix as essentially being equivalent to this library, but in none of those libraries can you express the body of your function in plain C++; one advantage of this is that errors in your code result in normal C++ error messages rather than cryptic error messages. Lorenzo, given this comment by Greg, I do have one more suggestion for documentation (or did someone already say it?). Given the heated discussion of whether Boost.Bind, Boost.Lambda and Boost.Phoenix are sufficient to render Boost.Local unnecessary, perhaps it would be worth to provide a comparison of how my code (not too trivial, and not too complex) would look in either case. For instance: With C++11 lambdas: for_each( vec.begin(), vec.end(), []( std::string & n ){ if(n.empty()) n = "n/a";} ); With Boost.Lambda + Boost.Bind: for_each( vec.begin(), vec.end(), if_then(boost::bind(&std::string::empty, _1), _1 = "n/a") ); With Phoenix: using boost::phoenix::arg_names::arg1; using boost::phoenix::if_; using boost::phoenix::bind; // right? for_each( vec.begin(), vec.end(), if_(bind(&std::string::empty, arg1)) [ arg1 = "n/a" ] ); With Boost.Local (Boost.Closure): BOOST_CLOSURE_PARAMS( std::string & n ) { if( n.empty() ) n = "n/a"; }BOOST_CLOSURE_NAME(replace_empties); for_each( vec.begin(), vec.end(), replace_empties ); Ok, I am not sure if there are no better ways to write it in each variant, and I may be biased. I also didn't try to compile the examples. But it should give the potential users an overview of options they have. Regards, &rzej

4 4

Boost CRC maintainer (Daryle Walker) missing in action?
by Olaf van der Spek 21 Nov '11

21 Nov '11

Hi, It looks like the Boost CRC maintainer (Daryle Walker) is missing in action? No response to tickets from the past 3 years. What's the procedure in this case? https://svn.boost.org/trac/boost/ticket/2492 https://svn.boost.org/trac/boost/query?component=crc&col=id&col=summary&col… Greetings, -- Olaf

1 3

Re: [boost] Boost.Local Review (Nov 10, 2011 to Nov 19, 2011)
by Andrzej Krzemienski 21 Nov '11

21 Nov '11

> Do you have any preference? > FUNCTION or CLOSURE? > And also a), b1), b2), c) or d)? > (Or something else...) Hi Lorenzo, Now that I have better understood your library, my personal preference goes towards "closure". The reason for that is: 1. "Closure" better reflects the nature of your library: you provide a tool for defining closures: something more than functions, and something less than lambda expressions. 2. This may make the learning of the library easier. If I know I am dealing with closures I already expect binding functionality; there will be less questions like "what is this 'bind' and what does it actually do?" 3. It may be a marketing bonus "closure" sounds (IMO) more attractive than "function". How about Boost.Closure library? "Local" may not even be necessary, because "closure" somehow implies locality. (you do not need a global closure, because global function will do). Regards, &rzej

3 6

Fw: [asio] multicast.
by John Maddock 21 Nov '11

21 Nov '11

Message forwarded from original sender: ~~~~~ Hi I am trying to join multicast group via _VPN_, this means that I cannot see listen-address in ipconfig actually Could I please me explain how should I connect in this case? I am using multicast-reciever sample. http://www.boost.org/doc/libs/1_41_0/doc/html/boost_asio/example/multicast/… with port 9023, listen 172.20.200.42, multicast 239.192.112.3 #include <iostream> #include <string> #include <boost/asio.hpp> #include "boost/bind.hpp" const short multicast_port = 9023; class receiver { public: receiver(boost::asio::io_service& io_service, const boost::asio::ip::address& listen_address, const boost::asio::ip::address& multicast_address) : socket_(io_service) { try{ // Create the socket so that multiple may be bound to the same address. boost::asio::ip::udp::endpoint listen_endpoint( boost::asio::ip::address::from_string("0.0.0.0"), multicast_port); //boost::asio::ip::udp::endpoint listen_endpoint( // listen_address, multicast_port);//if I use listen_address instead of 0.0.0.0, there is an error in socket_.bind(listen_endpoint); socket_.open(listen_endpoint.protocol()); socket_.set_option(boost::asio::ip::udp::socket::reuse_address(true)); socket_.bind(listen_endpoint); // Join the multicast group. socket_.set_option( boost::asio::ip::multicast::join_group(multicast_address)); socket_.async_receive_from( boost::asio::buffer(data_, max_length), sender_endpoint_, boost::bind(&receiver::handle_receive_from, this, boost::asio::placeholders::error, boost::asio::placeholders::bytes_transferred)); } catch (std::exception& e) { std::cerr << "Exception: " << e.what() << "\n"; } } void handle_receive_from(const boost::system::error_code& error, size_t bytes_recvd) { if (!error) { std::cout.write(data_, bytes_recvd); std::cout << std::endl; socket_.async_receive_from( boost::asio::buffer(data_, max_length), sender_endpoint_, boost::bind(&receiver::handle_receive_from, this, boost::asio::placeholders::error, boost::asio::placeholders::bytes_transferred)); } } private: boost::asio::ip::udp::socket socket_; boost::asio::ip::udp::endpoint sender_endpoint_; enum { max_length = 1024 }; char data_[max_length]; }; int main(int argc, char* argv[]) { try { std::string list = "172.20.200.42"; std::string mt = "239.192.112.3"; boost::asio::io_service io_service; receiver r(io_service, boost::asio::ip::address::from_string(list), boost::asio::ip::address::from_string(mt)); io_service.run(); } catch (std::exception& e) { std::cerr << "Exception: " << e.what() << "\n"; } return 0; } //===================================== But with native c++ I can obtain data: #include <winsock2.h> #include <Ws2tcpip.h> #include <mswsock.h> #include <stdio.h> #include <stdlib.h> #include <iostream> using namespace std; #pragma comment(lib, "Ws2_32.lib") int main(){ WSAData data; WSAStartup( MAKEWORD( 2, 2 ), &data ); int sd = socket(AF_INET,SOCK_DGRAM,IPPROTO_UDP); sockaddr_in Sender; int SenderAddrSize = sizeof( Sender ); struct sockaddr_in binda; char *arg1 = new char[100]; char *arg2 = new char[100]; char *arg3 = new char[100]; arg1 = "239.192.112.3"; arg2 = "172.20.200.42"; arg3 = "9023"; binda.sin_family = AF_INET; binda.sin_port = htons( atoi(arg3)); binda.sin_addr.s_addr = htonl(INADDR_ANY); bind(sd,(struct sockaddr*)&binda, sizeof(binda)); struct ip_mreq_source imr; imr.imr_multiaddr.s_addr = inet_addr(arg1); imr.imr_sourceaddr.s_addr = inet_addr(arg2); imr.imr_interface.s_addr = INADDR_ANY; setsockopt(sd, IPPROTO_IP, IP_ADD_SOURCE_MEMBERSHIP, (char *) &imr, sizeof(imr)); char buf[65536]; while(1) { int res=recvfrom(sd,(char*)buf,sizeof(buf),0, (SOCKADDR *)& Sender, &SenderAddrSize); printf(buf); } //WORKS } //===================================== I cannot realize what is the difference in these two samples, Could you please tell me in which way should I use boost library to obtain data in this case? Thanks in advance, -- С уважением, Василий.

1 0

[local] Review (and resignation from review assistant)
by Gregory Crosswhite 21 Nov '11

21 Nov '11

Hey everyone, The discussion on the mailing list has caused me to realize that I have sufficient passion for the Local library that it is difficult for me to stay neutral, so I will be recusing myself from my position as Review Assistant for this library. (I have learned that should I decide to help out again in the future in this role for another review, I will make sure that it is for a library that I don't feel strongly about either way!) On the other hand, this means that there is no longer any reason not to post a review of this library. I have been a fan of this library for a long time because for me it solved the problem of having a nice way to write (pseudo-)closures in C++03 without having to write and maintain a lot of pointless boilerplate code, and without having to use a completely foreign syntax that I could never seem to get to work. Here is my review of it. > - What is your evaluation of the design? The library is very well designed. The function declaration syntax looks a little foreign at first, but it is very easy to get used to. Furthermore, error messages are usually able to point you to what you did wrong. The fact that you can write the body of the function in plain C++ code is a major advantage of this library. Some have referred to Boost.Bind, Boost.Lambda and Boost.Phoenix as essentially being equivalent to this library, but in none of those libraries can you express the body of your function in plain C++; one advantage of this is that errors in your code result in normal C++ error messages rather than cryptic error messages. It is also clear reading through the documentation that Lorenzo has put a great deal of thought into possible use cases of his library; there are a great number of features which most users might never need to use but which are available for those times when they are completely necessary --- such as explicitly providing types of bound parameters, and marking functions inline --- and they are provided in such a way that when they aren't needed they introduce no additional overhead to the syntax. > - What is your evaluation of the implementation? I am not familiar enough with preprocessor programming to be able to make a fully qualified statement on this. However, it looks reasonable based on the Implementation appendix. The virtual function call is a shame as, if I recall correctly, it can make Boost.Local slower than Boost.Phoenix when the compiler is not smart enough to optimize it into a direct call, but Lorenzo has put so much time and expertise into the design of this library that I doubt it is possible to improve on this while maintaining compatibility with C++03. For me this part of the overhead is not a big deal because I primarily have been using Boost.Local in test suites where the difference in performance does not matter. > - What is your evaluation of the documentation? The documentation is some of the best well written I have seen for a Boost library. It does a good job both explaining how the library works, providing a reference for remembering how the syntax works, and explaining why the library was designed the way that it does. As I have told Lorenzo in a separate e-mail, I do have a minor criticism of the Tutorial section: the ordering of the first four sections is probably not what typical user reading it the first time would want because it puts the most important and essential feature, variable binding, after two features, default and empty argument features, which are nice to have but are not likely to be needed in typical usage, especially considering that a first-time user is most likely just looking for a convenient way to create a simple (pseudo-)closure in C++03. Thus, I suggest the following ordering: "Local Functions" "Variable Binding" "Default Parameters" "Empty Parameters" This way a typical user, who will only care about writing a function that binds a few local variables, will be able to get started immediately after reading the second section rather than first having to wade through two sections describing features that they are unlikely to care about right away. The rationale for putting "Default Parameters" before "Empty Parameters" is that a typical user is very unlikely to need to know how to call the macro with no arguments because there are few use cases where a typical user won't want to bind *anything* from the local environment (since most of the time this means that they won't be thinking in terms of local functions in the first place), so they are less likely to care about how to do this than they are about how to specify default parameters. > - What is your evaluation of the potential usefulness of the library? This library is very useful for people who want to use much of the functionality of C++11 lambdas on C++03 compilers, as I can say from personal experience in using it. As I have said before, the existence of Boost.Bind, Boost.Lambda and Boost.Phoenix do not reduce the utility of this library. They do have a large advantage over Boost.Local of being succinct, which is why I often prefer them over Boost.Local when it is easy to do so. However, because they require to you learn completely new syntax for *all* of the code in the function body, and because they make use of heavy metatemplate programming that results in absolutely horrendous error message that do not give you a clue where they are wrong, for anything non-trivial Boost.Local is hands-down *far* easier to use because you can use plain C++ statement syntax which results in plain C++ error message when you get something wrong. Put another way, Boost.Bind, Boost.Lambda and Boost.Phoenix are complementary to rather than competitors of Boost.Local. > - Did you try to use the library? With what compiler? Did you have any > problems? I have used the library extensively in my own codes, though most often in test suites. I have used them on OSX with GCC 4.2, and on Linux with (if I recall correctly) GCC 4.3 and 4.4. > - How much effort did you put into your evaluation? A glance? A quick > reading? In-depth study? I have become accustomed to using the library on a regular basis and hence my evaluation is written based on my personal experience with it. > Please state clearly whether you think this library should be accepted as a Boost library. Definite yes. Cheers, Greg

2 1

[interprocess] Named types ( mutexes, semaphores etc.) and Windows 7
by Edward Diener 20 Nov '11

20 Nov '11

Under Windows 7 fior named types to be global, the name of the type needs to be prefixed by the string "Global\" Is this being done in the interprocess library for Windows 7 ?

2 1