- Boost - lists.boost.org

[BGL] [push_relabel_max_flow]
by Pablo Madoery 18 Nov '14

18 Nov '14

Hello, I am having trouble using the push_relabel_max_flow algorithm when i put std::numeric_limits<double>::max() as capacity attribute in some edges. is there a maximum value that I can use as capacities. which ?. This is the example I am using : #include <iostream> #include <boost/graph/adjacency_list.hpp> #include <boost/graph/push_relabel_max_flow.hpp> #include <boost/graph/graphviz.hpp> using namespace std; using namespace boost; struct vertexInfo { }; struct edgeInfo { double capacity; double residualCapacity; double flow; adjacency_list_traits<vecS, vecS, bidirectionalS>::edge_descriptor rev; edgeInfo() { residualCapacity = 1000; } }; typedef adjacency_list<vecS, vecS, bidirectionalS, vertexInfo, edgeInfo> Graph; typedef Graph::edge_descriptor edge_d; const char* names[] = { "SV", "L1", "L2", "L3", "L4", "ET"}; template<typename Vertex> void create_edge(Graph& g, Vertex v0, Vertex v1, double capacity) { //the algorithm requires that for each edge u-v in the graph, the edge v-u also exists Graph::edge_descriptor ep0 = (add_edge(v0, v1, g)).first; Graph::edge_descriptor ep1 = (add_edge(v1, v0, g)).first; g[ep0].capacity = capacity; g[ep0].rev = ep1; g[ep1].capacity = 0; // the capacity of v-u needs to be 0 g[ep1].rev = ep0; } int main() { Graph graph; Graph::vertex_descriptor SV = add_vertex(graph); Graph::vertex_descriptor L1 = add_vertex(graph); Graph::vertex_descriptor L2 = add_vertex(graph); Graph::vertex_descriptor L3 = add_vertex(graph); Graph::vertex_descriptor L4 = add_vertex(graph); Graph::vertex_descriptor ET = add_vertex(graph); create_edge(graph, SV, L1, std::numeric_limits<double>::max()); create_edge(graph, SV, L2, std::numeric_limits<double>::max()); create_edge(graph, SV, L3, std::numeric_limits<double>::max()); create_edge(graph, SV, L4, std::numeric_limits<double>::max()); create_edge(graph, L3, ET, 1000); create_edge(graph, L4, L3, 1000); create_edge(graph, L2, L3, 1000); create_edge(graph, L1, L2, 1000); // arcos de vuelta create_edge(graph, L3, L4, 1000); create_edge(graph, L3, L2, 1000); create_edge(graph, L2, L1, 1000); std::cout << "Max flow: " << push_relabel_max_flow(graph, SV, ET, get(&edgeInfo::capacity, graph), get(&edgeInfo::residualCapacity, graph), get(&edgeInfo::rev, graph), get(boost::vertex_index, graph)) << std::endl; graph_traits<Graph>::vertex_iterator vi, vi_end; graph_traits<Graph>::out_edge_iterator ei, ei_end; cout.precision(20); for (tie(vi, vi_end) = vertices(graph); vi!= vi_end; ++vi) { for (tie(ei, ei_end) = out_edges(*vi, graph); ei != ei_end; ++ei) { graph[*ei].flow = graph[*ei].capacity - graph[*ei].residualCapacity; if (graph[*ei].capacity > 0) { std::cout << names[*vi] << " " << names[target(*ei, graph)] << " " << (graph[*ei].capacity - graph[*ei].residualCapacity) << "/" << graph[*ei].capacity << std::endl; } } } cout<<"end"<<endl; return 0; } ----------------------------------------------------------------------------------------------------------------------------- And this is the exception: /home/madoery/boost_1_55_0/boost/graph/push_relabel_max_flow.hpp:706: typename boost::property_traits<CapacityEdgeMap>::value_type boost::push_relabel_max_flow(Graph&, typename boost::graph_traits<Graph>::vertex_descriptor, typename boost::graph_traits<Graph>::vertex_descriptor, CapacityEdgeMap, ResidualCapacityEdgeMap, ReverseEdgeMap, VertexIndexMap) [with Graph = boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, vertexInfo, edgeInfo>, CapacityEdgeMap = boost::adj_list_edge_property_map<boost::bidirectional_tag, double, double&, long unsigned int, edgeInfo, double edgeInfo::*>, ResidualCapacityEdgeMap = boost::adj_list_edge_property_map<boost::bidirectional_tag, double, double&, long unsigned int, edgeInfo, double edgeInfo::*>, ReverseEdgeMap = boost::adj_list_edge_property_map<boost::bidirectional_tag, boost::detail::edge_desc_impl<boost::bidirectional_tag, long unsigned int>, boost::detail::edge_desc_impl<boost::bidirectional_tag, long unsigned int>&, long unsigned int, edgeInfo, boost::detail::edge_desc_impl<boost::bidirectional_tag, long unsigned int> edgeInfo::*>, VertexIndexMap = boost::vec_adj_list_vertex_id_map<vertexInfo, long unsigned int>, typename boost::property_traits<CapacityEdgeMap>::value_type = double, typename boost::graph_traits<Graph>::vertex_descriptor = long unsigned int]: Assertion `algo.is_flow()' failed. Thank You

1 0

gdb pretty printers
by Paul Fee 18 Nov '14

18 Nov '14

Hi all, On Linux, when using GDB to debug C++ programs that use Boost, it's difficult to get human readable values from variables. e.g. == Source == boost::optional<std::string> s("hello world"); == GDB == (gdb) print s $1 = {<boost::optional_detail::optional_base<std::basic_string<char, std::char_traits<char>, std::allocator<char> > >> = {<boost::optional_detail::optional_tag> = {<No data fields>}, m_initialized = true, m_storage = {dummy_ = {data = "(0`\000\000\000\000", aligner_ = {<No data fields>}}}}, <No data fields>} ======== A set of python pretty printers that understand the internals of some Boost objects can be found here: https://github.com/ruediger/Boost-Pretty-Printer The resulting output is more useful: == GDB == (gdb) print s $2 = boost::optional<std::basic_string<char, std::char_traits<char>, std::allocator<char> > > is initialized = {value = "Hello world"} ========= Some distros, e.g. Fedora, CentOS have STL pretty printers working out of the box. It would be great to also have Boost pretty printers widely available via Linux distros. Since the pretty printers are tightly coupled to the objects they're printing, it would be ideal if they were included with Boost. That way both the class definitions and python printers should stay in sync. Can someone provide guidance on how to get code in the above github repo into Boost? Thanks, Paul

1 0

Boost config macros for 'override' and 'final'?
by Nat Goodspeed 17 Nov '14

17 Nov '14

I don't find in Boost 1.57 any Boost macros to mediate use of the 'override' or 'final' C++11 specifiers. Would that be a reasonable addition?

6 7

RFC/patch: compile boost on Android for platform development
by Wagner, David 17 Nov '14

17 Nov '14

Hi, We are evaluating the pros and cons of using Boost for platform development on Android. We have successfully built and run Asio's "chat" server and client examples on an Android device running Lollipop. The C++ support seems to have been greatly improved since KitKat. Even though it is still early to say that all of Boost runs ok, all the Asio unit tests passed with "*** No errors detected" except the multicast test. I've attached a patch that adds Android makefiles to relevant libraries for compiling Boost.Asio. It's a first draft and it doesn't use the git submodules. The development of this patch has been made on top of the 1.56.0 tag. Platform development on android is different than native development ("NDK", used for JNI libraries). There seem to have been several efforts made for Boost support on NDK but we haven't found any for platform development (which is aimed at device support, e.g., HAL development, native tools). Is there an interest for maintaining a set of Android makefiles on vanilla Boost ? I understand someone would need to run the regression tests on Android; is there any other such requirement ? Kind Regards, -- David Wagner Intel Corp. --------------------------------------------------------------------- Intel Corporation SAS (French simplified joint stock company) Registered headquarters: "Les Montalets"- 2, rue de Paris, 92196 Meudon Cedex, France Registration Number: 302 456 199 R.C.S. NANTERRE Capital: 4,572,000 Euros This e-mail and any attachments may contain confidential material for the sole use of the intended recipient(s). Any review or distribution by others is strictly prohibited. If you are not the intended recipient, please contact the sender and delete all copies.

2 2

Re: [boost] Is there interest in a library for string-convertible enums?
by Jeffrey Bush 17 Nov '14

17 Nov '14

> > Jeffrey Bush wrote: > > > I have also offered a class for doing this as well, although it didn't > draw > > the interest that this one did. > > Here was my attempt at it with a test/example class: > > https://gist.github.com/coderforlife/6d8bac451d49dd1a0c81 > > > > > Looks good to me, and seems to be quite close to what I aim at. > > But the definition seems very user unfriendly. Is it correct that > > you always have to declare enums in the public namespace? > > --- > > Felix > Sorry for the delayed response. It does support being in a public namespace, even as a sub-class. However the definition does get uglier in sub-classes. The major problem I ran into was that the class could not be defined in a header file without getting multiple-definition or as a sub-class without running into problems. Mainly because of the constant arrays in the classes couldn't be defined in-line and in headers. Some C++11 features may help get around this. I do think that when these issues are ignored the declarations are pretty nice: BOOST_FLAGS_WITH_VALUES(MyFlags, std::uint8_t, A, 1, B, 2, AB, 3, C, 4); BOOST_FLAGS(MyDefaultFlags, AX, BX, CX, DX, EX, FX, GX, HX); namespace MyNS { BOOST_FLAGS(MyFlags, M, N, O, P, Q); } That makes 3 different enumerations, first with custom values and a custom base (uint8_t), the second with default values (powers of two) and selects the smallest base type, and the third is the same but in a non-public-namespace. All of these don't work in header files without getting multiple definitions. To avoid that problem you can do something like: // In H file: BOOST_FLAGS_DECL(MyFlags, M, N, O, P, Q); // In CPP file: BOOST_FLAGS_DEFN(MyFlags, M, N, O, P, Q); The same technique can be used to make sub-classes (as in the example file). If I remember correctly if the ability to go from string -> value and get list of values at runtime then the ugliness of the separate DECL/DEFN would be avoided. Jeff

1 0

Re: [boost] [review][sort] Formal review period for Sort library begins today, November 10, and ends Wednesday, November 19
by Niall Douglas 16 Nov '14

16 Nov '14

On 10 Nov 2014 at 0:39, Edward Diener wrote: > - What is your evaluation of the design? It's okay. I would prefer a design where there is a sorted_view which if std::copy gives an actually sorted copy. Obviously one would then specialise that scenario with a more directly optimised specialisation, and you'd also have the API presented here which looks like std::sort(). I'd also prefer to see fallback implementations for less than random iterators, right down to forward only iterators. > - What is your evaluation of the implementation? There seems to be an assumption that user supplied overloads and specialisations e.g. swap() don't throw exceptions. I think that unwise. BOOST_NOEXCEPT can test if something can throw. Explicit guarantees of what happens when something does throw needs to be in the documentation, per API. There seems to be a general lack of explicit C++ 11 support as well. In particular, I think all Boost libraries should use inline namespaces to implement ABI version management. Implementation isn't capable of dual build as standalone use without any dependency on Boost. I'd suggest my forthcoming Boost.BindLib library. > - What is your evaluation of the documentation? Lacks exception guarantees, one per API. Lacks scaling graphs near front so people can quickly evaluate usefulness compared to std::sort. I believe the author will fix this though. > - What is your evaluation of the potential usefulness of the > library? > - Did you try to use the library? With what compiler? Did you > have any problems? No. > - How much effort did you put into your evaluation? A glance? A > quick reading? In-depth study? Glance. > - Are you knowledgeable about the problem domain? Author of a very popular open source indexing algorithm library. > And finally, every review should attempt to answer this question: > > - Do you think the library should be accepted as a Boost library? Yes with these conditions: 1. Either change its name to Boost.Spreadsort, or do a much better job at a general sort library e.g. sorted_view, more than one sort algorithm not in the STL, more than random access iterator support. 2. Exception safety is not obvious, and explicit exception guarantees need to be made and stated per API in the documentation. 3. Explicit ABI version management in C++ 11 using inline namespaces. Forthcoming Boost.BindLib can do this for you, or it can be done by hand. It would also be nice if this library were also capable of standalone build without Boost, but this is not a requirement. Niall -- ned Productions Limited Consulting http://www.nedproductions.biz/ http://ie.linkedin.com/in/nialldouglas/

2 4

Re: [boost] How do I authenticate myself?
by Felix Uhl 14 Nov '14

14 Nov '14

Andrey Semashev wrote: > Note that you can have anonymous read-only access if you change the URL a little: > git://github.com/boostorg/boost.git > That should probably be mentioned in the docs. Thank you very much, that was exactly what I needed. Should've probably thought about that myself. I agree, that should be mentioned. Especially under the point "try out modular boost". --- Felix Uhl ________________________________ Von: Andrey Semashev<mailto:andrey.semashev@gmail.com> Gesendet: ‎14.‎11.‎2014 14:17 An: boost(a)lists.boost.org<mailto:boost@lists.boost.org> Betreff: Re: [boost] How do I authenticate myself? On Friday 14 November 2014 10:55:36 Felix Uhl wrote: > I want to clone the current develop branch > > to verify that a bugfix to a trac item I opened > > does actually fix the bug. > > > It seems like this information should be easy > > to find on the boost webpage or wiki, but neither > > of both explain how to authenticate myself > > when using “git clone --recursive git@ > > github.com:boostorg/boost.git modular-boost >clone.log”. > > The output of this is “Permission denied (publickey)”, > > which seems to mean to me that I need a > > ssh key the server actually knows about or that I have > > to upload my public key somehow. > > > Have I just missed something on the wiki? As Boost is hosted on GitHub, all the options it offers also work with Boost. See here: https://help.github.com/articles/which-remote-url-should-i-use/ Note that you can have anonymous read-only access if you change the URL a little: git://github.com/boostorg/boost.git That should probably be mentioned in the docs. _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

1 0

Re: [boost] How do I authenticate myself?
by Felix Uhl 14 Nov '14

14 Nov '14

Adam Wulkiewicz wrote: >FYI, instead of preparing a patch and attaching it to a bug report you >could consider working directly on the development version of a library >and propose a pull request with the fix on GitHub. The fix is not mine, I have opened a ticket, the author has written a fix and I just wanted to clone to check if the fix has fixed the issue. Thanks for the link, though, I'll make sure to check it out. --- Felix Uhl ________________________________ Von: Adam Wulkiewicz<mailto:adam.wulkiewicz@gmail.com> Gesendet: ‎14.‎11.‎2014 14:48 An: boost(a)lists.boost.org<mailto:boost@lists.boost.org> Betreff: Re: [boost] How do I authenticate myself? Andrey Semashev wrote: > On Friday 14 November 2014 10:55:36 Felix Uhl wrote: >> I want to clone the current develop branch >> >> to verify that a bugfix to a trac item I opened >> >> does actually fix the bug. >> >> >> It seems like this information should be easy >> >> to find on the boost webpage or wiki, but neither >> >> of both explain how to authenticate myself >> >> when using “git clone --recursive git@ >> >> github.com:boostorg/boost.git modular-boost >clone.log”. >> >> The output of this is “Permission denied (publickey)”, >> >> which seems to mean to me that I need a >> >> ssh key the server actually knows about or that I have >> >> to upload my public key somehow. >> >> >> Have I just missed something on the wiki? > As Boost is hosted on GitHub, all the options it offers also work with Boost. > See here: > > https://help.github.com/articles/which-remote-url-should-i-use/ > > Note that you can have anonymous read-only access if you change the URL a > little: > > git://github.com/boostorg/boost.git > > That should probably be mentioned in the docs. FYI, instead of preparing a patch and attaching it to a bug report you could consider working directly on the development version of a library and propose a pull request with the fix on GitHub. Here is a tutorial showing how this could be done: https://github.com/boostorg/geometry/wiki/Contribution-Tutorial It was made for Geometry but the procedure looks the same for any other library. Regards, Adam _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

1 0

How do I authenticate myself?
by Felix Uhl 14 Nov '14

14 Nov '14

I want to clone the current develop branch to verify that a bugfix to a trac item I opened does actually fix the bug. It seems like this information should be easy to find on the boost webpage or wiki, but neither of both explain how to authenticate myself when using “git clone --recursive git@ github.com:boostorg/boost.git modular-boost >clone.log”. The output of this is “Permission denied (publickey)”, which seems to mean to me that I need a ssh key the server actually knows about or that I have to upload my public key somehow. Have I just missed something on the wiki? --- Felix Uhl

3 2

[sort] Review of the Sort library by Steven Ross
by Edward Diener 14 Nov '14

14 Nov '14

As review manager I am forwarding this review sent to me: - What is your evaluation of the design? - What is your evaluation of the implementation? Design an implementation look good to me. Spreadsort has a clean interface and the code is readable. I tried the algorithm out a few years ago in a project at work (our product in the EDA industry) for sorting 32-bit {x,y} coordinate data cast to a 64-bit integer, and for sorting 32-bit values within scanlines. The speedup was about 1.8x that of std::sort() for ~100M values. This translated into a 10-20% overall runtime reduction in that tool, with only a few lines of code changes. - What is your evaluation of the documentation? I haven't read through the documentation in detail, but I have read through the code and the comments so I feel I understand the basics of how the sorting algorithm works. - What is your evaluation of the potential usefulness of the library? I would say this library is very useful for specific tasks involving large datasets that need to be sorted, especially in cases where the data is already partially sorted and contains many duplicate values. For example, it could be useful for EDA applications, computational geometry, some types of databases, etc. It may be a fairly narrow user base but I think it could add significant value. - Did you try to use the library? With what compiler? Did you have any problems? I built and tested spreadsort on both linux/gcc and Windows/MSVC++. I was never successful in running the tests in Cygwin. It seemed to work as expected when I tried using it inside an EDA tool and caused no problems. - How much effort did you put into your evaluation? A glance? A quick reading? In-depth study? I spent some hours reviewing the algorithm a few years ago, and I provided Steve with feedback to improve the code. I was mostly interested in the integer sorting aspect at that time, but did experiment with floating-point numbers as well. I read through the code again recently to familiarize myself with it. - Are you knowledgeable about the problem domain? I would say that I'm knowledgeable of applications and uses of sorting large datasets, and algorithms in general. I don't have any specific experience in developing or testing sorting algorithms. - Do you think the library should be accepted as a Boost library? Yes, I believe Steve has put in enough work to make this a well designed, tested, and documented library. There are real numbers to show the performance improvements over other sorting algorithms. If this was part of Boost, I would probably use it in our product at my company. Frank Gennari

1 0