- Boost - lists.preview.boost.org

[Boost] runtime+memory evaluation of 6 BGL planar graph algorithms
by hermann＠stamm-wilbrandt.de 06 Oct '24

06 Oct '24

Half a year ago I copied together Boost examples making use of: boost/graph/make_connected.hpp boost/graph/make_biconnected_planar.hpp boost/graph/make_maximal_planar.hpp boost/graph/boyer_myrvold_planar_test.hpp boost/graph/planar_canonical_ordering.hpp boost/graph/chrobak_payne_drawing.hpp I added "read_leda_graph()" for processing graph files. And added code to write a graphiviz file from the generated straight line drawing. Use of "layout=neato" with fixated vertex coordinates with exclamation mark (pos="3,2!") misuse GraphViz to just draw the BGL determined straight line drawing. I did evaluation on random maximal planar graphs with 10,000 up to 100 million vertices in 10x steps. In 1993 I wrote a technical report on how to create maximal planar random graphs. I published the 1994 code two years ago (self written graph lib, not LEDA nor Boost): https://github.com/Hermann-SW/randomgraph All details of the evaluation including runtime table in this "straight_line_graphviz.cpp" gist comment: https://gist.github.com/Hermann-SW/99d151a273d290ee0d843c79b2da26a8?permali… Total runtime factors are 13.5x and 20.9x between 1, 10 and 100 million vertex graphs. Since the input graphs were maximal planar, the algorithms make_connected / make_biconnected_planar and make_maximal_planar did not have much to do. The resident RAM usage is perfectly linear, 2.8 / 28.1 / 281.4 GB for 1 / 10 / 100 million vertices. 100 million vertices, 300 million edges, edge property, planar ordering, planar straight line drawing and 8 byte storage for numbers on 64bit OS cause a factor of 2800 comparing resident RAM used with number of vertices. Regards, Hermann.

1 0

Scheduled review of MQTT library
by Mateusz Loskot 06 Oct '24

06 Oct '24

Folks, On behalf of the Review Wizards Team, formal review of proposed MQTT library has now been scheduled: - https://github.com/boostorg/website/pull/877 The review details should be soon displayed on the website - https://www.boost.org/community/review_schedule.html Best regards, Mateusz Loskot

2 4

[optional] Feedback on the range interface for Boost.Optional
by Andrzej Krzemienski 05 Oct '24

05 Oct '24

Hi Everyone, I have just recorded the following message in the Mailing List. sob., 14 wrz 2024 o 02:44 Alan de Freitas via Boost <boost(a)lists.boost.org> napisał(a): > - As people seem to imply, the WG21 issue goes way beyond the motivation > behind the proposals or the difficulty behind the Boost review process. Not > all Boost libraries are intended to go through WG21. Not all WG21 proposals > would make good Boost libraries (like begin/end iterators for > std::optional). We are in the process of implementing the range interface for Boost.Optional, as proposed in P3168R2 <https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2024/p3168r2.html> and to the extent possible in C++11. I would like to hear opinions from the people in this list, on if and why this would be a bad idea. Regards, &rzej;

9 18

[Boost][BGL] "is_straight_line_drawing()" is buggy for large graphs
by hermann＠stamm-wilbrandt.de 05 Oct '24

05 Oct '24

A while back I combined all BGL planarity functions (make_"connected / biconnected_planar / maximal_planar" + straight_line_drawing) prepended with "read_leda_graph()" and writing GraphViz output. The Graphviz output uses neato engine because that allows for fixed vertex coordinates with exclamation mark: 2 [pos="3,2!" label="2"] So GraphViz is just misused to display BGL straight line drawing Recently I enhanced it to time each relevant BGL function call in order to verify linear runtime as well as to investigate RAM usage. In 1993 I created a technical report about creation of random maximal planar graphs and published the code 2 years ago: https://gist.github.com/Hermann-SW/99d151a273d290ee0d843c79b2da26a8 I created maximal planar randomgraphs on 10,000, 100,000, 1million and 10million vertices, and used them as input for above timing code. All was fine until and including 1million vertex graph. But for 10million vertex graph final "is_straight_line_drawing()" incorrectly asserted: hermann@7950x:~$ randomgraph/randomgraph 10000000 -t maximal_planar -o 10000000.u ------------------------------------- malloc: 18 malloc-free: 0 hermann@7950x:~$ time ./straight_line_graphviz 10000000.u t read_leda_graph(g, argv[1]); 9.63147 make_connected(g); 1.82002 assert(boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g, boyer_myrvold_params::embedding = &embedding2[0])); 73.5683 make_biconnected_planar(g, &embedding2[0]); 25.9196 assert(boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g, boyer_myrvold_params::embedding = &embedding2[0])); 88.7905 make_maximal_planar(g, &embedding2[0]); 42.7211 assert(boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g, boyer_myrvold_params::embedding = &embedding2[0])); 96.7233 assert(boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g, boyer_myrvold_params::embedding = embedding)); 68.5428 planar_canonical_ordering(g, embedding, std::back_inserter(ordering)); 24.2465 chrobak_payne_straight_line_drawing( g, embedding, ordering.begin(), ordering.end(), straight_line_drawing); 4.49772 assert(is_straight_line_drawing(g, straight_line_drawing)); a.out: straight_line.cpp:163: int main(int, char**): Assertion `is_straight_line_drawing(g, straight_line_drawing)' failed. Aborted (core dumped) real 7m25,836s user 7m15,357s sys 0m10,356s hermann@7950x:~$ I added code into "graph/include/boost/graph/is_straight_line_drawing.hpp" to write the coordinates of the two edges that intersect: hermann@7950x:~$ cat intersect.txt a 4143438 86426 4064945 7932 4064944 7931 4143438 86426 hermann@7950x:~$ As you can see, both edges share vertex at coordinate "4143438,86426", but they do not intersect. Until that point in code the coordinates are std::size_t. But the called function uses double, causing false report: inline bool intersects(double x1, double y1, double x2, double y2, double a1, double b1, double a2, double b2, double epsilon = 0.000001) { I played with different epsilon values including 0, but the valid straight line drawing was always stated to be wrong. There are several algorithms for segment intersection with integer coordinates that don't need division and are correct for integer coordinates that are result of chrobak_payne_straight_line_drawing( g, embedding, ordering.begin(), ordering.end(), straight_line_drawing); https://en.wikipedia.org/wiki/Line%E2%80%93line_intersection#Given_two_poin… or https://www.dcs.gla.ac.uk/~pat/52233/slides/Geometry1x1.pdf#page=4 1) I want to create a BGL issue on this, is that OK? At least the doc does not state any limit on graph sizes: https://www.boost.org/doc/libs/1_86_0/libs/graph/doc/is_straight_line_drawi… 2) I want to create a pull request with new implementation for "intersects()" with integer coordinates. 2 days ago I created pull requests with 7 commits ahead on new "planar_vertex_six_coloring()": https://github.com/boostorg/graph/pull/387 Do I have to wait until that pull request was decided on? Or can I submit separate pull request not interfering with that request on my graph fork? Regards, Hermann.

2 7

Boost.Decimal Seeking Endorsment
by Matt Borland 05 Oct '24

05 Oct '24

Hello, Chris Kormanyos and I are seeking endorsement for our library proposal, Decimal (https://github.com/cppalliance/decimal) What is Decimal? It is an implementation of IEEE 754 and TR 24733[3][5], along with extensions to both. We provide three IEEE 754 compliant types: decimal32, decimal64, and decimal128, as specified in both documents. Since announcing the beta in the first half of the year, we have added three similar but non-compliant types: decimal32_fast, decimal64_fast, and decimal128_fast. These types perform all operations faster than the compliant types, with identical numerical results, at the cost of extra space. We also provide implementations of the majority of the STL as it apply to numerical types. The library is header-only, has no dependencies, and only requires C++14. Why should we have this in Boost? Decimal Floating Point types were standardized in IEEE 754 in the 2008 revision, but it has not been standardized in C++. We believe this library can serve as a reference implementation. An existing alternative would be one of the authors of the IEEE 754 standard helped write libdfp[4]. This is also available in C with GCC as _Decimal32, _Decimal64, and _Decimal128 [1]. We bring these to C++ with similar or better performance. We also bring interoperability with the STL which is missing in the aforementioned libraries. Since the announcement of our beta in the spring we have improved correctness, performance, and gained users. We added the fast types after conversation with Glen Fernandes, and bit conversions for both encodings of the types [2]. I am aware of at least one US-based trading firm using this library in production so the library is out in the field making money today. Should the library be endorsed John Maddock has graciously offered to be our review manager, and are targeting a post-holiday review period in mid-January 2025. Feel free to ask any questions, and open issues prior to the review period. Matt [1] https://gcc.gnu.org/onlinedocs/gcc/Decimal-Float.html [2] https://cppalliance.org/decimal/decimal.html#conversions [3] https://www.open-std.org/JTC1/SC22/WG21/docs/papers/2009/n2849.pdf [4] https://github.com/libdfp/libdfp [5] https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n3871.html

3 4

Scheduled review of SQLite library
by Mateusz Loskot 05 Oct '24

05 Oct '24

Folks, On behalf of the Review Wizards Team, formal review of proposed SQLite library has now been scheduled: - https://github.com/boostorg/website/pull/877 The review details should be soon displayed on the website - https://www.boost.org/community/review_schedule.html Best regards, Mateusz Loskot

1 0

Boost.Parser need final approval
by Zach Laine 04 Oct '24

04 Oct '24

I've *finally* gotten back around to making Boost.Parser properly ready for bringing into the next Boost release. Marshall suggested I post here to make sure that people who participated in the review have a chance to check that the notes from the review all got fixed/implemented. So, this is that email. Please have a look if you get the chance. The issue tracker for the github project is down to 8 items, all of which are nice-to-haves. All the issues raised during the review were captured in the issues list, and taken care of. Zach

3 2

Two mqtt libraries
by Robert Ramey 03 Oct '24

03 Oct '24

I've been contacted by my friend and sometime collaborator Takatoshi Kondo regarding his submission of a boost library: https://github.com/redboltz/async_mqtt. It has received two endorsements. He has asked me to be review manager and I'm inclined to accept this request as he was very helpful to me during the refinement of the boost serialization library. There is also mqtt client library that is proposed to the Boost. https://github.com/mireo/async-mqtt5 It also has endorsements and a review manager. A cursory examination of the git hub pages suggest considerable overlap between the two submissions. In general, boost has discouraged the acceptance of multiple libraries with this much overlap - and for good reason. An accepted library often becomes the canonical implementation in large parts of the C++ world. Having two high quality libraries that do almost the same thing is not where we would like to be. I would like to propose that we review both libraries simultaneously in order to try to reach a consensus as to which, if either we want to accept. I know this is a difficult task, but I think it is important that we do this. It's going to be tough to reject a well written library because a better one has been accepted. But it would be worse to reject a well written library merely because another one was submitted first. Normally I don't participate as a review manager as I'm pretty bogged down in Boost stuff as it is. But I'm willing to make an exception in this case due to the importance of this case and my strong personal ties to Takatoshi. BTW - who is the review wizard these days? I presume that he will be the one making the decision about this. Robert Ramey

10 17

std::multiset functionality support in boost interprocess headers
by Murali Kishore 30 Sep '24

30 Sep '24

Hi all, I see multiset is not present in boost interprocess, so I tried to use a "set" with a customized comparator to achieve multiset functionality. sample code: struct set_comparator { bool operator()(const int& a, const int& b) const { return a < b; // if change a <= b then seeing an errror } }; bip::shared_memory_object::remove("SHM"); bip::managed_shared_memory segment(bip::open_or_create, "SHM", 2047*1024*1024); typedef bip::allocator<int, bip::managed_shared_memory::segment_manager> ShmemAllocator; typedef bip::set<int, set_comparator, ShmemAllocator> ShmemSet; segment.destroy<ShmemSet>("MySet"); ShmemSet *sample1 = segment.construct<ShmemSet>("MySet")(set_comparator(), segment.get_segment_manager()); std::cout << "Insert in shared set:" << std::endl; sample1->insert(40); std::cout << "Insert in shared set:" << std::endl; sample1->insert(40); // Crashing here sample1->insert(40); sample1->insert(40); sample1->insert(20); sample1->insert(20); sample1->insert(20); sample1->insert(20); sample1->insert(20); when i try duplicate insertion, seeing following error, /usr/include/boost/intrusive/bstree.hpp:1331: boost::intrusive::bstree_impl<ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder>::iterator boost::intrusive::bstree_impl<ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder>::insert_unique_commit(boost::intrusive::bstree_impl<ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder>::reference, const insert_commit_data&) [with ValueTraits = boost::intrusive::bhtraits<boost::container::dtl::tree_node<int, boost::interprocess::offset_ptr<void>, boost::container::red_black_tree, true>, boost::intrusive::rbtree_node_traits<boost::interprocess::offset_ptr<void>, true>, boost::intrusive::normal_link, boost::intrusive::dft_tag, 3>; VoidOrKeyOfValue = void; VoidOrKeyComp = boost::container::value_to_node_compare<boost::container::dtl::tree_node<int, boost::interprocess::offset_ptr<void>, boost::container::red_black_tree, true>, boost::intrusive::tree_value_compare<boost::interprocess::offset_ptr<int, long int, long unsigned int, 0>, main()::set_comparator, boost::move_detail::identity<int>, bool, true>, bool>; SizeType = long unsigned int; bool ConstantTimeSize = true; boost::intrusive::algo_types AlgoType = boost::intrusive::RbTreeAlgorithms; HeaderHolder = void; boost::intrusive::bstree_impl<ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder>::iterator = boost::intrusive::tree_iterator<boost::intrusive::bhtraits<boost::container::dtl::tree_node<int, boost::interprocess::offset_ptr<void>, boost::container::red_black_tree, true>, boost::intrusive::rbtree_node_traits<boost::interprocess::offset_ptr<void>, true>, boost::intrusive::normal_link, boost::intrusive::dft_tag, 3>, false>; boost::intrusive::bstree_impl<ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder>::reference = boost::container::dtl::tree_node<int, boost::interprocess::offset_ptr<void>, boost::container::red_black_tree, true>&; boost::intrusive::bstree_impl<ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder>::insert_commit_data = boost::intrusive::insert_commit_data_t<boost::interprocess::offset_ptr<boost::intrusive::compact_rbtree_node<boost::interprocess::offset_ptr<void> >, long int, long unsigned int, 0> >]: Assertion `( p == this->end() || !this->comp()(*p, value) )' failed. "Need input on this or is this expected behaviour as per boost??" -- Regards, Murali Kishore

4 7

Shorter syntax for using a class constructor as a transform function.
by Andrzej Krzemienski 30 Sep '24

30 Sep '24

Hi Everyone, I would like to check if something like the following would be a useful addition to Boost.Core, or if something like this maybe exists: I have a class like ``` struct X { std::string str; explicit X(const std::string& s) : str(s) {} }; ``` I need to transform a vector of strings into a vector of X through invoking the constructor of X: ``` std::vector<std::string> strings = {"cat", "dog", "emu", "fox"}; std::vector<X> xs; std::transform(strings.begin(), strings.end(), std::back_inserter(xs),[](auto const& s) { return X(s); })); ``` It works, but a shorter version would be to introduce a component that is equivalent to the lambda: ``` std::transform(strings.begin(), strings.end(), std::back_inserter(xs), construct<X>)); ``` The full example: https://godbolt.org/z/85YoP9Pa9 Regards, &rzej;

4 4