- Boost-users - lists.preview.boost.org

Iterating "root" vertices with boost::graph
by Isaac Lascasas 25 Nov '15

25 Nov '15

Hello I want to enumerate all vertices with zero input edge count in a graph, I am using DFS right now: struct vertex_visitor : public boost::default_dfs_visitor { std::vector<vertex_t> Output; void discover_vertex(vertex_t v, graph_t const& g) { graph_t::in_edge_iterator edgeIt, edgeEnd; tie(edgeIt, edgeEnd) = boost::in_edges(v, g); if (edgeIt==edgeEnd) Output.push_back(v); } }; vertex_visitor vis; boost::depth_first_search(g, boost::visitor(v)); However I don't know how to cleanly stop execution after depth 0 inside my visitor and I can't figure out a better way to archieve this. Since I am fairly new to boost graph I supose that I'm missing something. Thanks.

2 1

Extend boost binary serialization with varints encoding
by Ernest Zaslavsky 24 Nov '15

24 Nov '15

Is it feasible to provide boost binary serialization with varint encoding capabilities? How does one achieve that? Can one just create template overload of "save" and "load" for unsigned integrals? anything else should be changed? [Read More]<http://feeds.feedburner.com/~r/sizmek-blog/~6/1> [http://www.sizmek.com/Sizmek.png]<http://www.sizmek.com/>

3 8

[type_erasure] BOOST_TYPE_ERASURE_MEMBER within namespace?
by Nat Goodspeed 23 Nov '15

23 Nov '15

I find that using BOOST_TYPE_ERASURE_MEMBER within my own namespace fails with compilation errors: myprog.cpp:23:1: error: no template named 'concept_interface'; did you mean '::boost::type_erasure::concept_interface'? This is with Boost 1.57, compiled with Apple clang from Xcode 7.1.1. Moving BOOST_TYPE_ERASURE_MEMBER to the global namespace allows successful compilation. I would rather avoid putting my has_member names into the global namespace. How to achieve that?

2 1

Consistency when removing items from boost multi-index using an inner iterator
by Hovnatan Karapetyan 23 Nov '15

23 Nov '15

Hi, I already posted this same question on StackOverflow, since I have not gotten an answer yet reposting it here too. Suppose I am iterating over a boost::multi_index using one of the two indices. Then if I start iterating using the other index and erasing an element according some criteria, does that invalidate the upper iterator? E.g., struct person { string name; string last_name; string age;} typedef multi_index< person, index_by< ordered_non_unique<person, string, &person::name>, ordered_non_unique<person, string, &person::age> >> PersonCollection; PersonCollection pc; //insert some elements into pc auto index0 = pc.get<0>();auto range0 = index0.equal_range("John");while (range0.first != range0.second) { auto index1 = pc.get<1>(); auto range1 = index1.equal_range(34); while (range1.first != range1.second) { if (range1.first->last_name == "Smith") range1.first = index1.erase(range1.first); else ++range1.first; } ++range0.first;} So in this case, is the range0 iterator always valid? Thanks! Hovnatan

2 2

[BGL]Using a function for weightmap to dijkstra_shortest_path
by Amit Prakash Ambasta 23 Nov '15

23 Nov '15

Hi, I am trying to write use BGL.dijkstra to calculate a shortest path in a time dependent network where edge.cost C(u, v) is a function of distance(a)edge.source and a variable wait time dependent on Edge.departure i.e. Cost(Edge(u,v), D(u)) = Wait(Edge(u, v).departure, D(u)) + Edge(u, v).delay The cost function ( and edge property is defined as): struct Eonnection { Eonnection(const Vertex source, const Vertex destination, const double departure, const double duration, const double cost) { this->source = source; this->destination = destination; this->departure = departure; this->duration = duration; this->cost = cost; }; Vertex source; Vertex destination; double departure; // Time of departure double duration; // Duration of traversing edge double cost; // Actual cost of traversing Edge std::pair<double, double> dyn_cost(std::vector<std::pair<double, double> > distances, double t_max) { std::pair<double, double> d_parent = distances[this->source]; double t_parent = d_parent.first; double c_parent = d_parent.second; double t_time_of_day = fmod(t_parent, 24 * 3600); double t_delay = t_time_of_day <= this->departure ? this->departure - t_time_of_day: this->departure + (24 * 3600 - t_time_of_day); double t_total = t_parent + t_delay + this->duration; if(t_total < t_max) { std::cout << "Edge usable with cost " << c_parent + this->cost << ", " << t_total << std::endl; return std::pair<double, double>(c_parent + this->cost, t_total); } else { std::cout << "Edge unusable" << std::endl; return std::pair<double, double>(std::numeric_limits<double>::infinity(), std::numeric_limits<double>::infinity()); } }; }; I'm trying to call dijkstra as dijkstra_shortest_paths_no_color_map( g, source, boost::make_iterator_property_map(pred.begin(), get(boost::vertex_index, g)), boost::make_iterator_property_map(distances.begin(), get(boost::vertex_index, g)), boost::make_transform_value_property_map( boost::bind<std::pair<double, double> >(&Eonnection::dyn_cost, _1, _2, distances, 24 * 3600 * 3), get(boost::edge_bundle, g) ), get(vertex_index, g), smaller, combiner, std::pair<double, double>(std::numeric_limits<double>::infinity(), std::numeric_limits<double>::infinity()), std::pair<double, double>(0, 0), vis ); However, this does not seem to work. How can I pass the weights as a dynamic function to dijkstra_shortest_paths?

1 0

Levelization of DAG in Boost graph -- trying again
by bhattach 20 Nov '15

20 Nov '15

Not sure why my previous attempt to post a new topic didn't succeed -- page kept showing a note that the post was not accepted by the mailing list. Trying one more time. ------------------------ Although I've been using graphs for 30+ years, I'm new to Boost Graph Library. I'd like to do "classical levelization" of a DAG -- as is commonly used in applications like digital logic simulation, etc -- whereby level(v) = max_level(set of predecessors of v) + 1 I used record_distances() with breadth_first_search() and suitably defined property map, but I suspect that's returning level(v) = min_level(set of predecessors of v) + 1 Is there a simple way to use breadth_first_search() to get the level numbers I want, or do I need to write my own levelization routine? Thanks in advance for comments/suggestions/pointers. Debashis Bhattacharya -- View this message in context: http://boost.2283326.n4.nabble.com/Levelization-of-DAG-in-Boost-graph-tryin… Sent from the Boost - Users mailing list archive at Nabble.com.

2 4

Asymmetry between function_input_iterator and function_output_iterator
by Daniel Hofmann 20 Nov '15

20 Nov '15

I experienced some issues and asymmetric behavior in the function input and output iterator interfaces [1] [2]. See the following small self-contained example: const auto two = make_function_input_iterator([]{ return 2; }, infinite{}); copy_n(two, 3, ostream_iterator<int>(cout, "\n")); This does not compile --- but it should, in my opinion. The problem is that make_function_input_iterator has two overloads, one that takes a Function& and one that takes a Function*. Shouldn't this rather take a Function by-values as the stdlib does, and let the user pass a std::ref if needs be? Then we could also pass lambdas, making this a viable feature in C++11 and later. Without being able to pass lambdas, I see almost no value in the input iterator. On a related note, the documentation does not say that the make_function_iterator always needs an Input state. In addition, the link to the function input iterator PDF on the overview page [3] 404s. Now to the function output iterator: const auto dummy_out = make_function_output_iterator([](int) {}); copy_n(nums, 3, dummy_out); Surprisingly this compiles since make_function_output_iterator takes its functor by const-ref (with a defaulted functor argument, which does not really make sense in my opinion, since the reason for the make_* function is type inference through the passed parameter). Note, though, how the function output iterator lives in the same iterators namespace as the functio input iterator, but is not inside the iterator directory. The respective headers are located at: boost/function_output_iterator.hpp boost/iterator/function_input_iterator.hpp I would love to understand the design decisions behind these, and if it would be possible to "modernize" them without breaking much of the interfaces. Cheers, Daniel J H [1] http://www.boost.org/doc/libs/1_59_0/libs/iterator/doc/function_input_itera… [2] http://www.boost.org/doc/libs/1_59_0/libs/iterator/doc/function_output_iter… [3] http://www.boost.org/doc/libs/1_59_0/libs/iterator/doc/index.html

1 0

boost interprocess named_mutex: race condition at creation?
by Liwei Peng 20 Nov '15

20 Nov '15

Hi, I am using named_mutex for synchronization among multiple processes. If all of the processes try to open_or_create the same-name named_mutex: named_mutex mutex(open_or_create, "somename"); 1) Is there any race condition for mutex creation? Or the API will guarantee one will create and all others will open? 2) If there is race condition, what are the work-arounds for this on Linux? Thanks, Liwei

2 1

A few ICL questions.
by Stephen Hewitt 19 Nov '15

19 Nov '15

I'm new to ICL and have a few questions and a problem. Here is my test code which demonstrated (Windows, MSVC 2012): > // "icl_question.cpp" > > >> #include "precomp.hpp" > > #include <iostream> > > #include <utility> > > #include <functional> > > #include <boost/cstdint.hpp> > > #include <boost/icl/closed_interval.hpp> > > #include <boost/icl/interval_map.hpp> > > >> typedef boost::icl::closed_interval<boost::uint16_t> interval_t; > > >> // Based on the in "boost/icl/functors.hpp". > > template <typename Type> struct inplace_assign > > : public boost::icl::identity_based_inplace_combine<Type> > > { > > typedef inplace_assign<Type> type; > > >> void operator()(Type& object, const Type& operand) const > > { > > object = operand; > > } > > }; > > >> // Why is the 7 template parameter not a template template parameter? > > // The code in "boost/icl/detail/design_config.hpp" does not define the > > // ICL_USE_INTERVAL_TEMPLATE_TYPE macro (I assume intentionally) which, if > > // defined, would make it so. > > typedef boost::icl::interval_map > > < > > boost::uint16_t, > > const char*, > > boost::icl::partial_absorber, > > std::less, > > inplace_assign, > > boost::icl::inter_section, > > interval_t > > > map_t; > > >> int main(int argc, char *argv[]) > > { > > using namespace std; > > >> map_t mem; > > // The commented line two down is what I intend, but it asserts at >> runtime. > > // This one works. > > mem += make_pair(interval_t(0, 0xfffe), "RAM"); > > //mem += make_pair(interval_t(0, 0xffff), "RAM"); > > mem += make_pair(interval_t(0xa000, 0xbfff), "Basic ROM"); > > >> cout << hex << mem << endl; > > >> return 0; > > } > > The first question is about the aggregate on collision functionality. I would just like to replace. I have implemented *inplace_assign *which does this but it seems strange that this isn't included. Am I missing something here (I fear I may well be)? The second question is why* interval_map*'s 7th template parameter ( *Interval*) is not a template template parameter. The code in "boost/icl/detail/design_config.hpp" does not define the *ICL_USE_INTERVAL_TEMPLATE_TYPE *macro (I assume intentionally) which, if defined, would make it so. The third question is about a runtime error I'm getting in the above code. The comment in *main *shows the scenario. Basically if I use *0xffff *as the end of the first range I get an ASSERT at runtime whereas 0xfffe works fine. Finally, the documentation seems a little sparse on the function of the *Section* template parameter. Any clarification on that would be appreciated.

2 2

[ICL] seems not to handle sets that contain the maximum element of the domain type.
by Stephen Hewitt 18 Nov '15

18 Nov '15

ICL seems not to handle sets that contain the maximum element of the domain type. I sent a similar mail a day ago, but I've simplified my example. Here's the code: Windows 7 Boost 1.59.0 ----BEGIN CODE--- using namespace std; typedef boost::icl::closed_interval<boost::uint16_t, std::less> interval_t; typedef boost::icl::split_interval_set<boost::uint16_t, std::less, interval_t> set_t; set_t s; s += interval_t(0x0000, 0xffff); s += interval_t(0xa000, 0xbfff); cout << "BAD: " << hex << s << endl; s.clear(); s += interval_t(0x0000, 0xfffe); s += interval_t(0xa000, 0xbfff); cout << "GOOD: " << hex << s << endl; ----END CODE--- ---BEGIN OUTPUT--- BAD: {[0,9fff][a000,ffff]} GOOD: {[0,9fff][a000,bfff][c000,fffe]} ---END OUTPUT--- The bad example seems to fail because the set contains 0xffff. In the good example I use 0xfffe.

2 1