- Boost - lists.boost.org

[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

16 38

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

Boost Asset Stewardship Review Result - Fiscal Committee Name
by Glen Fernandes 30 Sep '24

30 Sep '24

Ion wrote: > Fiscal Sponsorship Committee/Group sounds straightforward to me, > to make clear this group has no other duty than that. Thank you Ion - I agree. "Fiscal Sponsorship Committee" has my acceptance. Glen

3 2

Boost Asset Stewardship Review Result
by Glen Fernandes 29 Sep '24

29 Sep '24

Dear Boost developers and users, This concludes the Boost Asset Stewardship review was conducted between 09/03 and 09/22. I want to thank everyone who submitted a review and everyone who otherwise contributed to the discussion. What follows is my review result. For fairness and for the record, this is my connection to all parties involved: For the Boost C++ libraries I am or have been: - A Boost library author, - A maintainer of at least three Boost libraries, - A contributor to at least ten other Boost libraries, - A review manager of at least two Boost reviews, - A release manager, - A maintainer of the Boost GitHub organization, - A moderator of the Boost mailing lists, For the Boost Foundation I am or have been: - A former member of the Boost Steering Committee - A director on the board, For the C++ Alliance I have been: - A volunteer that helped review project specifications and resumes, On behalf of the Boost community, I accept the C++ Alliance Fiscal Sponsorship proposal with the following condition: - The new committee should be named something which clearly indicates that its purpose is confined to Boost's assets or infrastructure. There should be no confusion or question over whether it has any control or even other influence over the C++ library development. Please avoid any mention of "Steering" or "Direction". I accept the three initial members of the committee as proposed (Ion, Rene, Joaquin) without reservations. All three are Boost developers whom I respect and I am confident of their ability and their desire to serve the Boost community. While I appreciate the invitation to join, and would otherwise never refuse an opportunity to help Boost, I feel like my making the acceptance decision of the founding committee should prohibit me being on that list. The reviews and the discussion has convinced me that the Fiscal Sponsorship model is the right choice for Boost going forward. - It provides us with the financing we need now, and secures a very credible path for depending on them going forward. Moreover, it puts the administration of those resources in the hands of those representing our community. The Foundation can and has tried to achieve the same thing, but it should be obvious that it does not have the same level of financial resources, or technical and legal expertise at its disposal. - It has the support of a great majority of the Boost community. It is no secret that there has been a growing rift between the Boost developers and some of the Foundation members, despite my and others best attempts at healing it. Even with the same resources provided to the Foundation, I don't see it achieving the same level of acceptance and consensus that the C++ Alliance has. I want to thank the C++ Alliance for crafting this proposal, and giving us a solution for supporting those parts of Boost infrastructure that are increasingly expensive and complex to manage. This will allow the rest of us to focus on what we love doing: Working on C++ libraries. And I would be remiss if I did not repeat my gratitude to the C++ Alliance and to Vinnie for those times in the past he has come to Boost's rescue, many of these at my request. Next, I want to thank all present and past members of the Foundation and the Steering Committee for their service to the Boost project. Especially, I want to thank Michael Caisse for all the time and energy he has dedicated over the years to supporting the parts of Boost site and mailing lists that we take for granted. On that same note I want to thank the Foundation for agreeing to this review and committing to its result. If nothing else, I hope this act alone demonstrates to the community that despite past events, the intention of the Foundation is to act in accordance with the community's wishes. I would also like to make it known that I will submit a suggestion in the next meeting that the Boost Foundation rename itself to not include the word "Boost". Ultimately, it will come down to a vote between the board members, but I believe this is the best thing for the Foundation. Just as the rename from BoostCon to C++Now enabled the conference to achieve its goals of reaching the broader C++ community, the hope is that this will similarly enable the Foundation to succeed with its current mission, which spans beyond Boost. Finally, I want to repeat my thanks to the community for their voice in this review. While the list above of my involvement in Boost might seem significant, it really is not. I have contributed a small fraction of what some of the people who participated in this review have. But all of us are here because we are invested in Boost and want it to succeed more than it has already. And I hope that the decision above will help Boost do just that. Sincerely, Glen

8 13

Re: [boost] Boost Digest, Vol 7351, Issue 3
by Alfredo Correa 26 Sep '24

26 Sep '24

Hi Andrzej, Thanks for the continued conversation. > From: Andrzej Krzemienski <akrzemi1(a)gmail.com> > Subject: [boost] [multi] A successor to Boost.MultiArray? > Did I get it right that Multi can be considered a superior alternative to > Boost.MultiArray? > yes If so, it triggers a couple of points: > * Can Boost.MultiArray be upgraded instead? > MultiArray is a superset of BMA. I have a test in the CI to show that this library fulfills all the concepts BMA defines. There are still semantic differences in BMA, such as the quality of implementation issues or plain semantic bugs. Before we go down this road, I did try many times to overhaul BMA. The architecture of BMA is beyond repair. Some obstacles seem to be even purposeful features of the library, such as disallowing the assignment of arrays of different sizes. Layout information is heap allocated. Iterators are broken and too basic. Subblock views have a complicated, inefficient implementation. The lack of responsiveness of the original authors was also an issue. Don't get me wrong, BMA was a tour-de-force at the time. It even spearheaded C++ concept checking in C++98, which I have delayed integrating into the library until C++20 Concepts. * The same questions, "is it useful at all", apply also to Boost.MultiArray. > BMA is useful in principle and was a great leap forward then. In practice, it is unfortunately almost unusable. You can tour Stackoverflow questions on #boost-multi-array and see all its pain points. > * Whatever the motivation for using Boost.MultiArray is, it should also be > a good motivation for Multi. > yes > I read in the Boost.MultiArraydocs that it is a better replacement for > vector<vector<...>>. Yes, but this is a simplistic description. It is mainly used to explain the multi-index element access A[i][j], etc., but the analogy ends there. Of course it is a completely different data structure, vector<vector<...>> is more general (at a price), the "rows" can be staggered. In any case, it is, at worst a replacement for vector<vector<vector.< ....>>> *recursively*. > So, maybe a good use case is for simple use cases, > where you want to store and perform a simple access to relatively > small-sized data sets, where performance is important, but not > super-critical, and changing from nested vectors to Multi is already good > and sufficient an optimization. > I don't know how you conclude this is for small-sized data? Do you mean that vector<vector<...>> would be ok for large-size data in contrast? I don't think so. > As a side note, when comparing Multi with std::mdspan. The latter requires > C++23, while the former, only C++17. So, when someone has C++17, mdspan is > not an option. yes > BTW, why do you require C++17? > - The main reason was for ease of development: - implementing allocator propagation without if-constexpr is a nightmare. - c++17 provides polymorphic allocators, and I wanted to be compatible with them (at the time, I didn't know about __has_include, it was much simpler to just use C++17) - If I remember correctly, I could use some constexpr algorithms and make the arrays fully constexpr. These are not hard reasons to require C++17. I can port it to C++14 as soon as any user asks for it, but it hasn't happened yet. In fact, Vinnie Falco promised a gazillion dollars from Microsoft to port it back to C++14. ;P ( https://cpplang.slack.com/archives/C27KZLB0X/p1682786897070269) Thank you, Alfredo

2 2