September 2014 - Boost-users

[Thread] thousands of spurious wakeups from timed_wait() per second
by Steven Clark 15 Sep '14

15 Sep '14

I've been trying to get useful behavior out of condition_variable::timed_wait() with little success. Depending on the platform, I'm getting about 3000 or nearly 100000 spurious wakeups per second. I'm working on a few different Linux platforms with different versions of Boost: 1.46, 1.48, and another in the high 40's. The eventual target is 1.48. I've looked for bug reports and haven't found any, and I have no evidence yet that suggests the different versions are significant to this problem. Because of the lack of problem reports, I figure I'm doing something wrong. That's my question: "What am I doing wrong here?" I have a test program that sets up a typical producer/consumer example. The main program spawns a thread, the producer, that notifies the main thread via a condition_variable once a second for a few seconds, then ends. The main thread, the consumer, waits efficiently for notifications with a 2-second timeout. When the producer thread finishes, the main (consumer) thread eventually times out, joins the spawned thread, and exits. At least, that's what is supposed to happen. If I don't bother with timeouts and use condition_variable::wait(), it works perfectly - except for the timeout, join, and exit. This is as expected. So far I have seen no spurious wakeups at all with this test. There is an ominous yet ambiguous remark in the documentation "The duration overload of timed_wait is difficult to use correctly. The overload taking a predicate should be preferred in most cases." Due to that remark I stopped experimenting with relative timeouts before I got anything to work. Using absolute timeouts, I get very high numbers of spurious wakeups as mentioned above - 3000 and about 100000 per second depending on the platform. I see no difference between timed_wait with a predicate and without a predicate. I'm also having trouble with the return value of timed_wait(). The documentation carefully states that timed_wait() returns "false if the call is returning because the time specified by abs_time was reached, true otherwise". This seems to mean that spurious wakeups return true -- and if you think about it, the return value is useless if spurious wakeups could return false. You'd have to add your own check for timeout. I was quite surprised to find that every spurious wakeup of timed_wait() that I've ever seen returns false. That just doesn't make sense to me. Here is the version of my test program that uses timed_wait without a predicate, followed by its output. #include <boost/thread.hpp> #include <boost/date_time.hpp> #include <iostream> boost::condition_variable gCond; boost::mutex gMutex; bool gGotData; unsigned gValue; void threadfn() { for (unsigned i = 0; i < 7; i++) { std::cerr << "hello from threadfn(), #" << i << std::endl; { boost::lock_guard<boost::mutex> guard(gMutex); gGotData = true; gValue = i; } gCond.notify_one(); boost::this_thread::sleep(boost::posix_time::seconds(1)); } } int main() { std::cerr << "******* Using timed_wait()" << std::endl; gGotData = false; gValue = 999; boost::thread t(threadfn); while (true) { boost::system_time deadline( boost::posix_time::microsec_clock::local_time()); std::cerr << "now is " << deadline << std::endl; deadline += boost::posix_time::seconds(2); std::cerr << "deadline is " << deadline << std::endl; boost::unique_lock<boost::mutex> lock(gMutex); unsigned nWakeups = 0; while(!gGotData) { bool ret = gCond.timed_wait(lock, deadline); nWakeups++; if (ret) std::cerr << "timed_wait() returned true on wakeup #" << nWakeups << std::endl; } std::cerr << "main() exited inner loop with " << nWakeups << " wakeups; gGotData is " << (gGotData ? "true" : "false") << std::endl; if (gGotData) { std::cerr << "main(), notified, gValue is " << gValue << std::endl; gGotData = false; } } // not reached in this incarnation of the code t.join(); std::cerr << "main(), after joining" << std::endl; } ******* Using timed_wait() now is 2014-Sep-09 20:48:12.183781 deadline is 2014-Sep-09 20:48:14.183781 hello from threadfn(), #0 timed_wait() returned true on wakeup #1451 main() exited inner loop with 1451 wakeups; gGotData is true main(), notified, gValue is 0 now is 2014-Sep-09 20:48:12.215471 deadline is 2014-Sep-09 20:48:14.215471 hello from threadfn(), #1 timed_wait() returned true on wakeup #96864 main() exited inner loop with 96864 wakeups; gGotData is true main(), notified, gValue is 1 now is 2014-Sep-09 20:48:13.216511 deadline is 2014-Sep-09 20:48:15.216511 hello from threadfn(), #2 timed_wait() returned true on wakeup #95911 main() exited inner loop with 95911 wakeups; gGotData is true main(), notified, gValue is 2 now is 2014-Sep-09 20:48:14.216805 deadline is 2014-Sep-09 20:48:16.216805 hello from threadfn(), #3 timed_wait() returned true on wakeup #97526 main() exited inner loop with 97526 wakeups; gGotData is true main(), notified, gValue is 3 now is 2014-Sep-09 20:48:15.217191 deadline is 2014-Sep-09 20:48:17.217191 hello from threadfn(), #4 timed_wait() returned true on wakeup #104710 main() exited inner loop with 104710 wakeups; gGotData is true main(), notified, gValue is 4 now is 2014-Sep-09 20:48:16.217453 deadline is 2014-Sep-09 20:48:18.217453 hello from threadfn(), #5 timed_wait() returned true on wakeup #102404 main() exited inner loop with 102404 wakeups; gGotData is true main(), notified, gValue is 5 now is 2014-Sep-09 20:48:17.217685 deadline is 2014-Sep-09 20:48:19.217685 hello from threadfn(), #6 timed_wait() returned true on wakeup #97906 main() exited inner loop with 97906 wakeups; gGotData is true main(), notified, gValue is 6 now is 2014-Sep-09 20:48:18.217291 deadline is 2014-Sep-09 20:48:20.217291 ^C Thank you very much, Steven Clark

4 9

[fusion] BOOST_FUSION_DEFINE_STRUCT with user defined methods
by Tobias Loew 15 Sep '14

15 Sep '14

Hi, I often use BOOST_FUSION_DEFINE_STRUCT not to generate a fusion-sequence per se, but to get a struct with - default initialisation for all members - a reasonable set of constructors - equality-check - all above without additional code But sometimes I would like to have additional methods in those structs, but deriving from those or fusion-adapting them loses at least one of the nice properties above. After looking at the BOOST_FUSION_DEFINE_STRUCT implementation I though about splitting the makro BOOST_FUSION_DEFINE_STRUCT_IMPL an inject my code in-between. Now my questions are: - Is there anything I've overseen and might detroy some fusion-mechanism? - Is there any chance to get macros like BOOST_FUSION_DEFINE_STRUCT_[BEGIN|END] (and also for the other BOOST_FUSION_DEFINE_... macros? Tobias -- View this message in context: http://boost.2283326.n4.nabble.com/fusion-BOOST-FUSION-DEFINE-STRUCT-with-u… Sent from the Boost - Users mailing list archive at Nabble.com.

4 8

WG: [atomic] can it bechecked that boost::atomic<T> *v = reinterpret_cast<boost::atomic<T>*>(var); is safe?
by Tim Odenthal 15 Sep '14

15 Sep '14

On 15 Sep 2014, at 18:00, boost-users-request(a)lists.boost.org<mailto:boost-users-request@lists.boost.org> wrote: On Monday, September 15, 2014 07:31 PM, Tim Odenthal wrote: Dear experts, essentially, I use this type of reinterpret_cast for doubles, and it __seems__ to work fine. I compile-time check that the sizeof(boost::atomic<T>) == sizeof( T ), but is that enough to ensure that this will always work? Should/could I check alignment issues as well? Even if the "atomic_cast" function has a (small) run-time overhead, it would be very much worth it in my setting, where I actually want to safely add to a double at some location in memory. Obviously, I want to use boost::atomic to be system/compiler agnostic, since it's supposed to eventually run with clang, gcc, (linux, OS X) as well as MS compilers, and so far we didn't see the need to move to C++11... I'm not sure I can figure out what problem you're trying to solve. Well, essentially, I have an array of doubles that at exactly one point in the code needs to be added to where I cannot ensure that each thread only adds to its own part of the array, so I want to ensure that each addition there is executed atomically. I think the cast is probably "safe", but far less can be said of it when it's dereferenced. That would depend entirely on the type of var. Is *var actually a boost::atomic<T> in the first place? If it is, why are you erasing its type? No, as I was saying, it’s a double *. How can you be sure there is nobody else aliasing var or *var and then reading or writing it? That is actually a problem, but since I completely control that part of the code, I hope to not make that mistake ;-). If *var is not a boost::atomic<T>, reinterpret_cast isn't going to magically convert it, you have undefined behaviour. Of course, one effect of UB is that it __seems__ to work, until, presumably, it doesn’t. But what, then, is the difference between an atomic<double>* and a normal double*, if the sizes (and possibly alignments) are the same? Hmmm, I just read up on what a reinterpret_cast<> is supposed to be good for, which is very little indeed, so it seems that the behaviour is undefined - but then there is no way to solve that problem? (So far I only ever used it to print the address of a pointer...) Since openMP allows for a pragma atomic, somehow, it seems that there should be a way. Using a simple spin_lock is way too slow (tested), since it doesn’t lock a specific memory location, but essentially everything, and I suspect that more complicated locking schemes will be also more expensive, just for different reasons. Ben Thanks for your insight! Tim

2 1

[atomic] can it bechecked that boost::atomic<T> *v = reinterpret_cast<boost::atomic<T>*>(var); is safe?
by Tim Odenthal 15 Sep '14

15 Sep '14

Dear experts, essentially, I use this type of reinterpret_cast for doubles, and it __seems__ to work fine. I compile-time check that the sizeof(boost::atomic<T>) == sizeof( T ), but is that enough to ensure that this will always work? Should/could I check alignment issues as well? Even if the "atomic_cast" function has a (small) run-time overhead, it would be very much worth it in my setting, where I actually want to safely add to a double at some location in memory. Obviously, I want to use boost::atomic to be system/compiler agnostic, since it's supposed to eventually run with clang, gcc, (linux, OS X) as well as MS compilers, and so far we didn't see the need to move to C++11... Thanks for any advice in advance Tim

2 1

program_options Parsing Suboptions
by Robert 14 Sep '14

14 Sep '14

Hi, I am trying to use program_options to parse suboptions: Command –S “-a 1 –b test –c 1.2” (the suboptions in –S are to be passed into other programs) Using the example source code, I tried something like the code below, but get the following error The argument (‘ 1’) for option ‘—TestA’ is invalid. Apparently the space between –a and 1 is treated as part of the argument and thus will not convert to an integer. I tried at the top argument level (e.g. command –M 1) and it works as expected, so something about creating the vector of suboptions is confusing program_options. Any suggestions? Thanks very much. options_description desc("Allowed options"); desc.add_options()("subopt,S",value<string>(),"Sub Options"); variables_map vm; store(command_line_parser(ac, av).options(desc).run(), vm); vm.notify(); if (vm.count("subopt")) { string substring=vm["subopt"].as<string>(); boost::regex re("\\s+(?=-)"); boost::sregex_token_iterator i(substring.begin(), substring.end(), re, -1); boost::sregex_token_iterator j; vector<string> splitResults; copy(i,j,back_inserter(splitResults)); int ta; string tb; float tc; options_description subopt_desc("Suboptions"); subopt_desc.add_options() ("TestA,a", value<int>(&ta)->default_value(0), "integer") ("TestB,b",value<string>(&tb),"string") ("TestC,c",value<float>(&tc), "float") ; variables_map subopt_vm; store(command_line_parser(splitResults).options(subopt_desc).run(), subopt_vm); subopt_vm.notify(); cout<<"a="<<ta<<endl; cout<<"b="<<tb<<endl; cout<<"c="<<tc<<endl; } -- http://www.fastmail.fm - Choose from over 50 domains or use your own

1 1

[graph] how to find all vertices reachable from one edge of a starting vertex
by Michael Marcin 14 Sep '14

14 Sep '14

How can I find all vertices reachable by following one specified out-edge? Is there already an algorithm that does this? If not I think I could do it by: - marking all vertices white - mark starting vertex gray - depth_first_visit the target of the specified edge Does this work?

2 2

[container][slist] constant time splice_after
by Aaron Levy 14 Sep '14

14 Sep '14

What happens if I call slist::splice_after(this_iter, that_list, that_begin, that_end, nelems) with an nelems value that does not match std::distance(that_begin, that_end). In other words, is there any kind of validations performed on nelems and is it just used to update the size of the list? Aaron

2 1

how to construct an iterator_archetype<single_pass_traversal_tag>
by Peter Johansson 13 Sep '14

13 Sep '14

Hi, I'm writing tests using the iterator_archetype [http://www.boost.org/doc/libs/1_55_0/libs/iterator/doc/iterator_archetypes.…] and get confused how to use a single_pass_iterator such as e.g. iterator_archetype<int, readable_iterator_t, single_pass_iterator> The default constructor does not work as expected (since single_pass_iterators are not necessarily default constructible). The copy constructor is not very useful and that is all can find. I noticed the detail::ctor_arg and was hoping there were a constructor thaing that struct as argument - but no. How am I supposed to construct this class if I e.g. wanna passed it to a function that I intend to test. Thank you, Peter

1 0

[container][flat_map] Internal storage for flat_maps / flat_sets
by Aaron Levy 13 Sep '14

13 Sep '14

What is the type of the underlying contiguous storage used by the flat_map / flat_set containers? Does the following code make sense: flat_map<T> container; ... if (container.size() > 0) { const T& elem = *(container.begin()); const T& elem_1 = *(container.begin() + 1); assert(&elem_1 == &elem + 1); } Aaron

2 1

Problem linking with boost::program_options with clang 3.5 (OSX)
by Jürgen Simon 12 Sep '14

12 Sep '14

Hello, I require OpenMP on OSX and had to build OpenMP/Clang to that end. The compiler reads as clang 3.5. For some reason, the compiler seems to have a problem linking executables with boost. I tried boost version 1.55 but got a compilation error. Boost 1.56 compiles with this warning: clang-3.5: warning: argument unused during compilation: '-finline-functions' but other than that compiles through and installs just fine. When trying to link an executable with program_options however, I get the following linker error: Undefined symbols for architecture x86_64: "__ZN5boost15program_options11to_internalERKSs", referenced from: __ZN5boost15program_options11to_internalISsEESt6vectorISsSaISsEERKS2_IT_SaIS5_EE in radolan2cf.cpp.o "__ZN5boost15program_options19options_descriptionC1ERKSsjj", referenced from: _main in radolan2cf.cpp.o "__ZN5boost15program_options20invalid_option_valueC1ERKSs", referenced from: __ZN5boost15program_options8validateIfcEEvRNS_3anyERKSt6vectorISbIT0_St11char_traitsIS5_ESaIS5_EESaIS9_EEPT_l in radolan2cf.cpp.o "__ZN5boost15program_options22error_with_option_nameC2ERKSsS3_S3_i", referenced from: __ZN5boost15program_options16validation_errorC2ENS1_6kind_tERKSsS4_i in radolan2cf.cpp.o "__ZN5boost15program_options6detail7cmdline21set_additional_parserENS_9function1ISt4pairISsSsERKSsEE", referenced from: __ZN5boost15program_options25basic_command_line_parserIcE12extra_parserENS_9function1ISt4pairISsSsERKSsEE in radolan2cf.cpp.o "__ZN5boost15program_options6detail7cmdlineC2ERKSt6vectorISsSaISsEE", referenced from: __ZN5boost15program_options25basic_command_line_parserIcEC2EiPKPKc in radolan2cf.cpp.o "__ZN5boost15program_options8validateERNS_3anyERKSt6vectorISsSaISsEEPSsi", referenced from: __ZNK5boost15program_options11typed_valueISscE6xparseERNS_3anyERKSt6vectorISsSaISsEE in radolan2cf.cpp.o "__ZN5boost15program_optionslsERSoRKNS0_19options_descriptionE", referenced from: _main in radolan2cf.cpp.o "__ZNK5boost15program_options22abstract_variables_mapixERKSs", referenced from: __ZNK5boost15program_options13variables_mapixERKSs in radolan2cf.cpp.o "__ZNK5boost15program_options22error_with_option_name23substitute_placeholdersERKSs", referenced from: __ZTVN5boost16exception_detail10clone_implINS0_19error_info_injectorINS_15program_options20invalid_option_valueEEEEE in radolan2cf.cpp.o __ZTVN5boost16exception_detail19error_info_injectorINS_15program_options20invalid_option_valueEEE in radolan2cf.cpp.o __ZTVN5boost15program_options20invalid_option_valueE in radolan2cf.cpp.o __ZTVN5boost15program_options16validation_errorE in radolan2cf.cpp.o __ZTVN5boost16exception_detail10clone_implINS0_19error_info_injectorINS_15program_options16validation_errorEEEEE in radolan2cf.cpp.o __ZTVN5boost16exception_detail19error_info_injectorINS_15program_options16validation_errorEEE in radolan2cf.cpp.o "__ZNK5boost15program_options29value_semantic_codecvt_helperIcE5parseERNS_3anyERKSt6vectorISsSaISsEEb", referenced from: __ZTVN5boost15program_options11typed_valueIfcEE in radolan2cf.cpp.o __ZTVN5boost15program_options11typed_valueISscEE in radolan2cf.cpp.o ld: symbol(s) not found for architecture x86_64 clang-3.5: error: linker command failed with exit code 1 (use -v to see invocation) I’m a little stumped as to how to fix this problem. Can someone help me out? Kind Regards, Jürgen

1 0

[Range] Strange!
by Robert Jones 10 Sep '14

10 Sep '14

Can anyone explain why my last output line is garbage? #include <iostream> #include <boost/range/algorithm/copy.hpp> #include <boost/range/counting_range.hpp> #include <boost/range/adaptor/reversed.hpp> #include <boost/range/adaptor/transformed.hpp> #include <boost/phoenix/bind/bind_function.hpp> #include <boost/phoenix/core/argument.hpp> int doubled( int i ) { return i * 2; } template <typename Range> void print_it( const Range & range ) { boost::copy( range, std::ostream_iterator<int>( std::cout, " " ) ); std::cout << std::endl; } int main( ) { using boost::adaptors::reversed; using boost::adaptors::transformed; using boost::counting_range; using boost::phoenix::arg_names::_1; print_it( counting_range( 1, 5 ) ); print_it( counting_range( 1, 5 ) | reversed ); print_it( counting_range( 1, 5 ) | transformed( doubled ) ); print_it( counting_range( 1, 5 ) | reversed | transformed( doubled ) ); print_it( counting_range( 1, 5 ) | transformed( bind( doubled, _1 ) ) ); print_it( counting_range( 1, 5 ) | reversed | transformed( bind( doubled, _1 ) ) ); } Output is 1 2 3 4 4 3 2 1 2 4 6 8 8 6 4 2 2 4 6 8 -711713824 -711713824 -711713824 -711713824 Compiling with gcc-4.9.1, Boost 1.56 on Fedora 20 64-bit. Thx, Rob.

6 16

[filesystem] directory_iterator and filter in 1.56.0
by Braden McDaniel 10 Sep '14

10 Sep '14

This sort of thing worked in Boost 1.55.0: #include <boost/filesystem.hpp> #include <boost/range.hpp> #include <boost/range/adaptor/filtered.hpp> struct pred { bool operator()(const boost::filesystem::directory_entry & dirent) const { return true; } }; int main() { const auto dirent_range = boost::make_iterator_range(boost::filesystem::directory_iterator("/"), boost::filesystem::directory_iterator()); const auto filtered_dirent_range = boost::adaptors::filter(dirent_range, pred()); } Not so in 1.56.0 [output from Apple's clang 3.4]: boost/concept_check.hpp:210:9: error: no viable conversion from 'boost::single_pass_traversal_tag' to 'boost::forward_traversal_tag' Y y = x; ^ ~ The full error output is much more verbose and I can provide it if desired; but the above is the gist of the situation, as I understand it: directory_iterators are SinglePass iterators; filter operates on ForwardTraversal iterators; and the SinglePass iterator cannot be converted to the ForwardTraversal one. Is this situation deliberate or an unintended side effect? Is there some similarly succinct means of filtering a file/directory listing? -- Braden McDaniel <braden(a)endoframe.com>

1 0

Re: [Boost-users] [context] Compiling error with context and bind
by José 10 Sep '14

10 Sep '14

3 2

[context] Compiling error with context and bind
by José 09 Sep '14

09 Sep '14

2 1

[msm] extending msm::back::state_machine
by Manuel Schiller 09 Sep '14

09 Sep '14

Hi, I tried to enhance the backend of boost::msm by inheriting from boost::msm::back::state_machine. When doing so, I cannot access members of my subclass in the states. When compiling the attached example, I get this error message: *error: ‘class boost::msm::back::state_machine<fsm_, boost::parameter::void_, boost::parameter::void_, boost::parameter::void_, boost::parameter::void_>’ has no member named ‘test’* How can I "inject" extended_back_machine as the type being passed as "FSM" to the state? Bye Manuel #################################### template<typename FrontMachine> struct extended_back_machine : public boost::msm::back::state_machine<FrontMachine> { void test() { std::cout << "test" << std::endl; } }; struct fsm_ : public boost::msm::front::state_machine_def<fsm_> { struct State : public boost::msm::front::state<> { template <class Event,class FSM> void on_entry(Event const&, FSM& fsm) { fsm.test(); } }; typedef State initial_state; }; int main() { typedef extended_back_machine<fsm_> fsm; fsm m; m.start(); return 0; } ####################################

3 3

[boost][container][static_vector] Stack or heap?
by Aaron Levy 08 Sep '14

08 Sep '14

Does the boost::container::static_vector allocate its memory on the stack or heap. From what I could make of the code, it seems to allocate on the stack. What happens if the requested size exceeds the stack size limits? Aaron

2 1

[boost][assign][bimap] Assign support for bimap
by Aaron Levy 08 Sep '14

08 Sep '14

Are there any Boost.Assign overloads available for Boost.Bimap? Aaron

2 2

linking with Intel compiler to Boost libs compiled with Visual Studio
by Damien 05 Sep '14

05 Sep '14

Hi, I'm trying to link to Boost 1.56 libs that I built with VS2013. We compile with both Intel and VS. We build Boost with layout=tagged (e.g. boost_serialization-mt-gd.lib), and these link fine with VS2013. When linking with Intel 2015 the linker complains about a missing library, looking for the layout=versioned lib name (e.g. libboost_serialization-iw-mt-gd-1_56.lib). Even if you specify the library name directly on the link line, it still complains. I'm sure this is just an include or #define issue but I don't know where to look. If anyone can point me in the right direction I'd be grateful. Cheers, Damien

2 2

Testers required
by Antony Polukhin 05 Sep '14

05 Sep '14

Hi, There is a big need in testers that have access to exotic platforms(zArch, MIPS) and compilers (Cray, IBM xlc ...). Could you please run `b2` in `boost/libs/type_index/test` and report results. This will help to test Boost.TypeIndex library and other libraries that depend on `demangle.hpp` I'll appreciate any help. Thanks in advance! -- Best regards, Antony Polukhin

1 0

[graph] Vertex order and VertexList type changes boykov_kolmogorov_max_flow result
by Michael J Iatauro 04 Sep '14

04 Sep '14

In the code below, using listS to store vertices results in vertex instantiation order changing the amount of flow computed by boykov_kolmogorov_max_flow. As given, it computes a flow of 0. If I move the instantiation of "T-" to be before "t-" or switch the VertexList parameter of adjacency_list to vecS, it computes the correct flow of 1000. Stepping through the code, it looks like when the max_flow function iterates over vertices that are targets of out-edges from the source, the call to get(m_in_active_list_map, v) at boykov_kolmogorov_max_flow.hpp:528 returns true for the second vertex, preventing it from getting added to m_active_nodes. I tested this using g++ 4.4.7 and with Boost 1.55 and 1.56. Has anybody else seen anything like this? Code follows: #include <boost/graph/adjacency_list.hpp> #include <boost/graph/boykov_kolmogorov_max_flow.hpp> #include <boost/graph/properties.hpp> #include <boost/graph/graph_traits.hpp> #include <iostream> #include <limits> using namespace boost; typedef adjacency_list_traits<vecS, listS, directedS> Traits; typedef Traits::vertex_descriptor Vertex; typedef Traits::edge_descriptor Edge; typedef adjacency_list<vecS, listS, directedS, property<vertex_name_t, std::string, property<vertex_index_t, long, property<vertex_color_t, default_color_type, property<vertex_distance_t, long, property<vertex_predecessor_t, Edge > > > > >, property<edge_flow_t, double, property<edge_capacity_t, double, property<edge_residual_capacity_t, double, property<edge_reverse_t, Edge > > > > > Graph; void addEdge(Graph& g, const Vertex& source, const Vertex& target, const double capacity, const double reverseCapacity) { property_map<Graph, edge_reverse_t>::type rev = get(edge_reverse, g); Edge e1 = add_edge(source, target, g).first; Edge e2 = add_edge(target, source, g).first; put(edge_capacity, g, e1, capacity); put(edge_capacity, g, e2, reverseCapacity); rev[e1] = e2; rev[e2] = e1; } int main(void) { Graph g; property_map<Graph, vertex_name_t>::type nameMap = get(vertex_name, g); Vertex source = add_vertex(g); nameMap[source] = "source"; Vertex sink = add_vertex(g); nameMap[sink] = "sink"; Vertex tminus = add_vertex(g); nameMap[tminus] = "t-"; addEdge(g, source, tminus, 1, 0); Vertex Tminus = add_vertex(g); nameMap[Tminus] = "T-"; addEdge(g, source, Tminus, 1000, 0); Vertex Tplus = add_vertex(g); nameMap[Tplus] = "T+"; addEdge(g, Tplus, sink, 1000, 0); addEdge(g, Tplus, Tminus, 0, std::numeric_limits<int>::max()); double flow = boykov_kolmogorov_max_flow(g, source, sink); std::cout << flow << std::endl; return 0; } -- ------------------ Michael J. Iatauro Software Engineer QTS, Inc. NASA Ames Research Center Office: 650-604-0662 Mail stop: 269-2 P.O. Box 1 Moffett Field, CA 94035-0001

1 0

Batch job processing with Boost Spirit parser
by Michael Levine 04 Sep '14

04 Sep '14

I have been using Boost Sprit as a parser for a project that I have been working on lately. At this point, I have been trying to expand the software and, in doing so, have had the nagging feeling that there is something wrong with my overall design. In the best case, I am not making the best use of my tools, and in the worst case, I am concerned that the design/code is becoming overly brittle. As an aside, I don’t have a huge amount of programming experience with this type of application. A word of background / context : Essentially, the program performs batch ‘jobs’ which are specified in a text file (not dissimilar in that sense from a scheduler like Condor). Spirit parses these ‘Job Description’ files into ‘specification objects’ (my vocabulary) that are used with a builder pattern and factories to create the appropriate objects. I have some concerns about this which I will describe later. The job description (henceforth: JD) file should have 3 parts: 1. Data 2. Tools 3. Operations The Data section is just a list of data that is to be operated on. At this stage, this is just a vector of std::pair<std::string, std::string> containing an identifier and the path of the file. The ‘Tools’ and ‘Operations’ sections are likely composed of nested specifications (the resulting objects use either a decorator pattern or composite pattern – depending on the type of tool) – which was the main reason that I started using Spirit altogether. My question is really a request for some guidance – to better utilize the tools available: I have just received the requirement for section #3 (Operations), to be included in the JD file (previously it was assumed that this would be provided in a different manner). So – at this time, I have a working parser for the Data and Tools portions. I have concerns with the ‘Tools’ portion that I would like to correct and not duplicate in the ‘Operations’ section that I am to be working on next. At present, I am parsing the JD file mostly into strings, and vectors of boost::variant<int,double> -- the latter being a list of parameters in a completely arbitrarily imposed order. As I’ve previously mentioned, I have a few problems with this approach. - The parameters are required to be input in an arbitrary order. - Different ‘Tool’s and ‘Operation’s have different parameters that are required and/or optional. For the past weeks (I only work on this project on a very part-time basis), I have been going in circles trying to figure out a better way to do this. I have a strong suspicion that Fusion can be used for this. I am also concerned about over-complicating the design, but am weary of leaving the design too simplistic. I.e., I know that I can treat the parameters as a std::pair<std::string, boost::variant<int, double>> and then parse key-value pairs with a given delimiter. I am just not convinced that this is the best way to do this. I am able to use any Boost Library, and have no restrictions about compilers (I’m using a recent version of Clang, primarily, right now). The following is a selection of the data structures and Spirit grammar that I am using here: struct Tool_Spec; typedef std::vector<boost::variant<int, double> > Tool_Options_t; typedef std::vector<Tool_Spec > Children_Tool_t; typedef std::pair<std::string, std::string> Data_Spec; struct Job_Request { Data_Spec data_spec; Tool_Spec model_spec; Operation_Spec operation_spec; boost::optional<std::string> description; }; struct Tool_Spec{ std::string type; std::string data_designation; Tool_Options_t; options; Children_Tool_t children; boost::optional<std::string> designation; }; struct Operation_Spec{ /* Unknown at this time. Need help */ }; Datafile %= lit("@START") >> *Data_Description >> Tool_Description >> Operation_Description >> lit("@END") ; Data_Description %= lit('%') >> Datasource >> lit(';') ; Datasource = Designator >> lit(':') >> Designator ; Designator %= +(char_("0-9a-zA-Z/._") | char_('-') ); Comment_Designator %= +(char_("0-9a-zA-Z/._, ()") | char_('-')); Tool_Description %= Designator >> ':' >> ('@' >> Designator) >> '[' >> +Options >> ']' >> -('{' >> *Child_Tool >> '}') >> -qi::lexeme[Comment_Designator] >> ';' ; Child_Tool %= Designator >> ':' >> ('@' >> Designator) >> '[' >> +Options >> ']' >> -('{' >> *Child_Tool >> '}') >> -qi::lexeme[Comment_Designator] >> ';' ; Options %= (int_ | double_ ) % '|';

1 0

[graph] filtered graph and num_vertices
by Miklós Tóth 03 Sep '14

03 Sep '14

Hi All, I have a graph, and I use a filter like this. struct FilteredGraph : public boost::filtered_graph<SomeGraph, SomeFilter > { FilteredGraph(SomeGraph g) : boost::filtered_graph<SomeGraph, SomeFilter>(g, SomeFilter(g)) {} }; I want to use in this function. template <class Graph>void some_graph_function(const Graph& g) { const size_t vertex_num = boost::num_vertices(g); //... } Like this: FilteredGraph fg(g) some_graph_function(fg); And I get: > error: no matching function for call to 'num_vertices(const FilteredGraph&)' > const size_t vertex_num = boost::num_vertices(g); > ^ >From the boost 1.55 documentation: > The num_vertices <http://www.boost.org/doc/libs/1_55_0/libs/graph/doc/filtered_graph.html#num…> and num_edges <http://www.boost.org/doc/libs/1_55_0/libs/graph/doc/filtered_graph.html#num…> functions do not filter > before returning results, so they return the number of vertices or > edges in the underlying graph, unfiltered [2] <http://www.boost.org/doc/libs/1_55_0/libs/graph/doc/filtered_graph.html#2>. So it should work. What am I missing? Regards, Miklós

1 0

Re: [Boost-users] [graph] Unique vertices using setS
by Nicholas Dahm 02 Sep '14

02 Sep '14

> On Tue, Sep 2, 2014 11:29 AM MDT Jeremiah Willcock wrote: > >> >> >>On Sun, Aug 31, 2014 10:53 PM MDT Nicholas Dahm wrote: >> >>>On Wed, Aug 27, 2014 7:24 PM EDT Nicholas Dahm wrote: >>> >>>Is there any place where I could enforce unique properties? (i.e. not add a new vertex if it's properties are the same as an existing vertex) >>> >>>Not that I know of. >>> >>>My graph is actually an implicit search tree for an A* search so there's lots of nodes which will be revisited via different paths. My current thought is to create the new vertex (which is a search tree state), then simply iterate through all existing vertices to see if any are identical in properties. However if the vertices were sorted by their properties in a set (i.e. weakly ordered), this would be much faster. >>> >>>Do you need to store the explored part of the search tree explicitly? You could instead use a custom graph type with your choice of vertex descriptor, then use associative_property_map to check for multiple visits to the same state. >>> >>>No need to store the explored part. I have exactly zero clue on how to create a custom graph type with a special vertex descriptor. At current I've gotten around it by having a "set" of vertex descriptors which use a custom "less" function which actually checks the vertex bundled properties instead of the descriptor. It's not the perfect solution but it wasn't very ugly either so it'll do. If you have a link to info on how to create custom graph types with special vertex descriptors please do let me know >> >>Please look at https://github.com/wpm/Boost-Implicit-Graph-Example for a simple example. You only need to do the incident edge iterator and property parts from that example, and can skip the other iterator types. There is also an A*-specific example at https://github.com/wpm/Astar-Maze-Solver, but it stores more of the data explicitly and uses existing BGL graph types. >> >>-- Jeremiah Willcock >> > >There is also http://www.boost.org/doc/libs/1_56_0/libs/graph/example/knights-tour.cpp as an example, but you'll probably need the BGL book for its documentation. > >-- Jeremiah Willcock Ok I'm getting the hang of it now. Thanks for all your help Jeremiah :)

1 0

problem with asio signal_set and consecutive signals
by Lutz Schneider 02 Sep '14

02 Sep '14

Hi, I have a program and would like to stop it by sending SIGINT for writing some data to a file instead of exiting immediately. However, if the user of the program sends SIGINT again then the program should quit immediately and forget about writing data to a file. For portability reason I would like to use boost::asio for this purpose. My initial (simplified) approach (see below) did not work. Is this not possible or am I missing something? handler seems to be called only once (printing out the message) and the program always stops when the loop has reached the max iteration number. void handler( const boost::system::error_code& error, int signal_number) { if (!error) { static bool first = true; if(first){ std::cout << " A signal(SIGINT) occurred." << std::endl; // do something like writing data to a file first = false; }else{ std::cout << " A signal(SIGINT) occurred, exiting...." << std::endl; exit(0); } } } int main(){ // Construct a signal set registered for process termination. boost::asio::io_service io; boost::asio::signal_set signals(io, SIGINT); // Start an asynchronous wait for one of the signals to occur. signals.async_wait(handler); io.run(); size_t i; for(i=0;i<std::numeric_limits<size_t>::max();++i){ // time stepping loop, do some computations } std::cout << i << std::endl; return 0; } Cheers, LS

2 3

Re: [Boost-users] [graph] Unique vertices using setS
by Jeremiah Willcock 02 Sep '14

02 Sep '14

On Tue, Sep 2, 2014 11:29 AM MDT Jeremiah Willcock wrote: > > >On Sun, Aug 31, 2014 10:53 PM MDT Nicholas Dahm wrote: > >>On Wed, Aug 27, 2014 7:24 PM EDT Nicholas Dahm wrote: >> >>Is there any place where I could enforce unique properties? (i.e. not add a new vertex if it's properties are the same as an existing vertex) >> >>Not that I know of. >> >>My graph is actually an implicit search tree for an A* search so there's lots of nodes which will be revisited via different paths. My current thought is to create the new vertex (which is a search tree state), then simply iterate through all existing vertices to see if any are identical in properties. However if the vertices were sorted by their properties in a set (i.e. weakly ordered), this would be much faster. >> >>Do you need to store the explored part of the search tree explicitly? You could instead use a custom graph type with your choice of vertex descriptor, then use associative_property_map to check for multiple visits to the same state. >> >>No need to store the explored part. I have exactly zero clue on how to create a custom graph type with a special vertex descriptor. At current I've gotten around it by having a "set" of vertex descriptors which use a custom "less" function which actually checks the vertex bundled properties instead of the descriptor. It's not the perfect solution but it wasn't very ugly either so it'll do. If you have a link to info on how to create custom graph types with special vertex descriptors please do let me know > >Please look at https://github.com/wpm/Boost-Implicit-Graph-Example for a simple example. You only need to do the incident edge iterator and property parts from that example, and can skip the other iterator types. There is also an A*-specific example at https://github.com/wpm/Astar-Maze-Solver, but it stores more of the data explicitly and uses existing BGL graph types. > >-- Jeremiah Willcock > There is also http://www.boost.org/doc/libs/1_56_0/libs/graph/example/knights-tour.cpp as an example, but you'll probably need the BGL book for its documentation. -- Jeremiah Willcock

1 0

Re: [Boost-users] [graph] Unique vertices using setS
by Jeremiah Willcock 02 Sep '14

02 Sep '14

On Sun, Aug 31, 2014 10:53 PM MDT Nicholas Dahm wrote: >>On Wed, Aug 27, 2014 7:24 PM EDT Nicholas Dahm wrote: >> >>Is there any place where I could enforce unique properties? (i.e. not add a new vertex if it's properties are the same as an existing vertex) >> >>Not that I know of. >> >>My graph is actually an implicit search tree for an A* search so there's lots of nodes which will be revisited via different paths. My current thought is to create the new vertex (which is a search tree state), then simply iterate through all existing vertices to see if any are identical in properties. However if the vertices were sorted by their properties in a set (i.e. weakly ordered), this would be much faster. >> >>Do you need to store the explored part of the search tree explicitly? You could instead use a custom graph type with your choice of vertex descriptor, then use associative_property_map to check for multiple visits to the same state. > >No need to store the explored part. I have exactly zero clue on how to create a custom graph type with a special vertex descriptor. At current I've gotten around it by having a "set" of vertex descriptors which use a custom "less" function which actually checks the vertex bundled properties instead of the descriptor. It's not the perfect solution but it wasn't very ugly either so it'll do. If you have a link to info on how to create custom graph types with special vertex descriptors please do let me know Please look at https://github.com/wpm/Boost-Implicit-Graph-Example for a simple example. You only need to do the incident edge iterator and property parts from that example, and can skip the other iterator types. There is also an A*-specific example at https://github.com/wpm/Astar-Maze-Solver, but it stores more of the data explicitly and uses existing BGL graph types. -- Jeremiah Willcock

1 0

Very interesting problem with TCP sockets
by Igor Mironchik 01 Sep '14

01 Sep '14

Hi guys, I was trying to connect Qt TCP Socket with Boost Asio TCP socket. And what I found. Qt writes simple 12 bytes message to the Boost and in most situations Boost reads garbage. Even more Boost can crash. And my question is: who is so bad guy, Boost or Qt? You can find simple implementation of the problem in the attachment. Thanks. P.S. Problem is on Windows 7, on Linux or Mac OS I have no possibility to test...

2 2

Boost MPI Collective
by Nolen, Steven Douglas 01 Sep '14

01 Sep '14

In boost/mpi/collectives/reduce.hpp The template function specialization for reduce-ing a std::vector, should probably be modified. Ffrom template<typename T, typename Op> void reduce(const communicator & comm, std::vector<T> const & in_values, std::vector<T> & out_values, Op op, int root) { out_values.resize(in_values.size()); reduce(comm, &in_values.front(), in_values.size(), &out_values.front(), op, root); } To template<typename T, typename Op> void reduce(const communicator & comm, std::vector<T> const & in_values, std::vector<T> & out_values, Op op, int root) { if( comm.rank() == root ) out_values.resize(in_values.size()); reduce(comm, &in_values.front(), in_values.size(), &out_values.front(), op, root); } This will save an extraneous allocation on the non-root nodes. -steve

2 1

[MSM] eUML compilation fails with gcc and -std=c++11
by caligano 01 Sep '14

01 Sep '14

Hi, I tried to compile some of the eUML MSM samples (e.g. http://www.boost.org/doc/libs/1_56_0/libs/msm/doc/HTML/examples/SimpleTimer…) using gcc 4.8 and with C+11 support enabled. However, I always get errors like the following one: error: ‘BOOST_PP_REPEAT_FROM_TO_M_1’ has not been declared I did not find anything about C++11 being not supported by Boost MSM, so I would like to know if I am doing anything wrong? Bye Manuel

3 2

[spirit,units] Linker problem on msvs platform
by Johannes Brunen 01 Sep '14

01 Sep '14

Hello, I have created two little helper functions for parsing strings with respect to unit length values: OptLengthQuantityT parse_length_quantity(...) PairOptLengthQuantityT parse_dbl_length_quantity(...) My problem is that my implementation based on the spirit and units libraries does compile fine, but fails on linking on 32Bit Debug with the following error message: Quantity.obj : fatal error LNK1179: invalid or corrupt file: duplicate COMDAT '?value@?$result_@U?$member_variable@$$A6E?AUlength_quantity_t@Quantitie s@@XZP8?$length_quantity_grammer@V?$_String_const_iterator@DU?$char_trai ts@D@std@@V?$allocator@D@2@@std@@U?$expr@Uterminal@tag@tagns_@proto@boos t@@U?$term@U?$char_code@Uspace@tag@spirit@boost@@Uiso8859_1@char_encodin g@34@@tag@spirit@boost@@@argsns_@45@$0A@@exprns_@proto@boost@@@2@AE?AU12 @XZ@detail@phoenix@boost@@@?$is_mem_fun_pointer_select@$0A@@detail@boost @@2_NB' I'm working with the msvc 2010Sp1 compiler from microsoft on windows 7. I have tried to shorten the symbol names but I could not get it to work. Does anyone has experience with this kind of errors? Is there something wrong with the implementation of the two functions? You can find the implementation in the attached files. Best, Johannes

1 0

[Boost.Log] translate 3rd party log entries
by Olaf Peter 01 Sep '14

01 Sep '14

Hello, from 3rd party lib I have to integrate the logging message - incorporating into boost.log. But I run into the problem with scopes: main.cpp: In function 'int main(int, char**)': main.cpp:55:5: error: no matching function for call to 'boost::log::v2s_mt_posix::attributes::named_scope_entry::named_scope_entry(const char [6], const char*&, int&)' main.cpp:55:5: note: candidates are: /opt/boost/boost_1_55_0/boost/log/attributes/named_scope.hpp:88:5: note: boost::log::v2s_mt_posix::attributes::named_scope_entry::named_scope_entry(const string_literal&, const string_literal&, unsigned int) /opt/boost/boost_1_55_0/boost/log/attributes/named_scope.hpp:88:5: note: no known conversion for argument 2 from 'const char*' to 'const string_literal& {aka const boost::log::v2s_mt_posix::basic_string_literal<char>&}' /opt/boost/boost_1_55_0/boost/log/attributes/named_scope.hpp:63:8: note: boost::log::v2s_mt_posix::attributes::named_scope_entry::named_scope_entry(const boost::log::v2s_mt_posix::attributes::named_scope_entry&) /opt/boost/boost_1_55_0/boost/log/attributes/named_scope.hpp:63:8: note: candidate expects 1 argument, 3 provided The problem rises on string_literal of __FILE__ entry. How can I get this working?? Thanks, Olaf

1 2

Trouble with compiling/linking the unit test library
by Christoff Kok 01 Sep '14

01 Sep '14

Hi, I am struggling to compile a simple test with the Unit test library. It seems to be a linker error when trying to link the unit_test_framework library. I have tried diffrerent options but to no avail. I have tried to link it with a visual studio library as well, but I am still receiving the same error. clang++.exe -o bin\Debug\QuickTest.exe obj\Debug\functions.o obj\Debug\functionsTest.o obj\Debug\maintest.o *C:\boost_1_55_0\stage\lib\libboost_unit_test_framework-mgw48-mt-1_55.a* obj\Debug\functionsTest.o: In function `_cxx_global_var_init2': D:\Ex Mente\Software\_CHK.Sandbox\quickCplusplusTest\QuickTest/functionsTest.cpp:4: undefined reference to `_imp___ZN5boost9unit_test9ut_detail24auto_test_unit_registrarC1EPNS0_9test_caseEm' obj\Debug\functionsTest.o: In function `ZN8Multiply11test_methodEv': D:\Ex Mente\Software\_CHK.Sandbox\quickCplusplusTest\QuickTest/functionsTest.cpp:6: *undefined reference to * `_imp___ZN5boost9unit_test15unit_test_log_t14set_checkpointENS0_13basic_cstringIKcEEjS4_' D:\Ex Mente\Software\_CHK.Sandbox\quickCplusplusTest\QuickTest/functionsTest.cpp:6: undefined reference to `_imp___ZN5boost10test_tools16predicate_resultC1Eb' D:\Ex Mente\Software\_CHK.Sandbox\quickCplusplusTest\QuickTest/functionsTest.cpp:6: *undefined reference to * `_imp___ZN5boost10test_tools9tt_detail10check_implERKNS0_16predicate_resultERKNS_9unit_test12lazy_ostreamENS5_13basic_cstringIKcEEjNS1_10tool_levelENS1_10check_typeEjz' D:\Ex Mente\Software\_CHK.Sandbox\quickCplusplusTest\QuickTest/functionsTest.cpp:6: *undefined reference to* `_imp___ZN5boost10test_tools16predicate_resultD1Ev' D:\Ex Mente\Software\_CHK.Sandbox\quickCplusplusTest\QuickTest/functionsTest.cpp:7: undefined reference to `_imp___ZN5boost10test_tools16predicate_resultD1Ev' obj\Debug\functionsTest.o: In function `_dtor__ZZN5boost9unit_test9singletonINS0_15unit_test_log_tEE8instanceEvE8the_inst': D:\Ex Mente\Software\_CHK.Sandbox\quickCplusplusTest\QuickTest/functionsTest.cpp:38: *undefined reference to* `_imp___ZN5boost9unit_test15unit_test_log_tD1Ev' obj\Debug\functionsTest.o: In function `ZN5boost9unit_test9singletonINS0_15unit_test_log_tEE8instanceEv': C:\boost_1_55_0\boost/test/utils/trivial_singleton.hpp:38: undefined reference to `_imp___ZN5boost9unit_test15unit_test_log_tC1Ev' obj\Debug\functionsTest.o: In function `ZN5boost9unit_test14make_test_caseERKNS0_9callback0INS0_9ut_detail6unusedEEENS0_13basic_cstringIKcEE': C:\boost_1_55_0\boost/test/unit_test_suite_impl.hpp:255: undefined reference to `_imp___ZN5boost9unit_test9ut_detail24normalize_test_case_nameENS0_13basic_cstringIKcEE' C:\boost_1_55_0\boost/test/unit_test_suite_impl.hpp:255: undefined reference to `_imp___ZN5boost9unit_test9test_caseC1ENS0_13basic_cstringIKcEERKNS0_9callback0INS0_9ut_detail6unusedEEE' obj\Debug\maintest.o: In function `main': C:\boost_1_55_0\boost/test/unit_test.hpp:59: undefined reference to `_imp___ZN5boost9unit_test14unit_test_mainEPFbvEiPPc' obj\Debug\maintest.o: In function `_cxx_global_var_init2': D:\Ex Mente\Software\_CHK.Sandbox\quickCplusplusTest\QuickTest/maintest.cpp:5: undefined reference to `_imp___ZN5boost9unit_test9ut_detail24auto_test_unit_registrarC1EPNS0_9test_caseEm' obj\Debug\maintest.o: In function `ZN29SimpleTestInMainTestingModule11test_methodEv': D:\Ex Mente\Software\_CHK.Sandbox\quickCplusplusTest\QuickTest/maintest.cpp:7: undefined reference to `_imp___ZN5boost9unit_test15unit_test_log_t14set_checkpointENS0_13basic_cstringIKcEEjS4_' D:\Ex Mente\Software\_CHK.Sandbox\quickCplusplusTest\QuickTest/maintest.cpp:7: undefined reference to `_imp___ZN5boost10test_tools16predicate_resultC1Eb' D:\Ex Mente\Software\_CHK.Sandbox\quickCplusplusTest\QuickTest/maintest.cpp:7: undefined reference to `_imp___ZN5boost10test_tools9tt_detail10check_implERKNS0_16predicate_resultERKNS_9unit_test12lazy_ostreamENS5_13basic_cstringIKcEEjNS1_10tool_levelENS1_10check_typeEjz' D:\Ex Mente\Software\_CHK.Sandbox\quickCplusplusTest\QuickTest/maintest.cpp:7: undefined reference to `_imp___ZN5boost10test_tools16predicate_resultD1Ev' D:\Ex Mente\Software\_CHK.Sandbox\quickCplusplusTest\QuickTest/maintest.cpp:8: undefined reference to `_imp___ZN5boost10test_tools16predicate_resultD1Ev' obj\Debug\maintest.o: In function `_dtor__ZZN5boost9unit_test9singletonINS0_15unit_test_log_tEE8instanceEvE8the_inst': D:\Ex Mente\Software\_CHK.Sandbox\quickCplusplusTest\QuickTest/maintest.cpp:38: undefined reference to `_imp___ZN5boost9unit_test15unit_test_log_tD1Ev' collect2.exe: error: ld returned 1 exit status clang++.exe: error: linker (via gcc) command failed with exit code 1 (use -v to see invocation) Kind Regards, Christoff

1 0

A* search on Implicit graph (search tree)
by Nicholas Dahm 31 Aug '14

31 Aug '14

Hi All, I'm trying to run an A* search using boost's astar_search, but I'm running into issues with 'const'. I'm trying to add the examine_vertex(my_vdesc_type &v, my_graph_type &g) function, but of course boost says that I need to make it const like examine_vertex(my_vdesc_type &v, const my_graph_type &g) However since I'm searching an implicit graph, I need to call add_vertex(g) within this function. But then I of course get an error because i'm trying to do add_vertex(const my_graph_type &g) which is invalid. I've read the example astar_maze.cpp which CLAIMS to be implicit but certainly doesn't appear to be. I've also seen the pdf at http://cs.krisbeevers.com/research/astar_bgl04.pdf which says you need to basically create non-const versions of a bunch of functions. Considering that http://www.boost.org/doc/libs/1_56_0/libs/graph/doc/astar_search.html says that "A* is particularly useful for searching implicit graphs", I'm assuming that boost ALREADY HAS some way of actually searching implicit graphs. Any ideas? cheers Nick

1 0

Re: [Boost-users] [graph] Unique vertices using setS
by Nicholas Dahm 31 Aug '14

31 Aug '14

>On Wed, Aug 27, 2014 7:24 PM EDT Nicholas Dahm wrote: > >>Is there any place where I could enforce unique properties? (i.e. not add a new vertex if it's properties are the same as an existing vertex) > >Not that I know of. > >>My graph is actually an implicit search tree for an A* search so there's lots of nodes which will be revisited via different paths. My current thought is to create the new vertex (which is a search tree state), then simply iterate through all existing vertices to see if any are identical in properties. However if the vertices were sorted by their properties in a set (i.e. weakly ordered), this would be much faster. > >Do you need to store the explored part of the search tree explicitly? You could instead use a custom graph type with your choice of vertex descriptor, then use associative_property_map to check for multiple visits to the same state. No need to store the explored part. I have exactly zero clue on how to create a custom graph type with a special vertex descriptor. At current I've gotten around it by having a "set" of vertex descriptors which use a custom "less" function which actually checks the vertex bundled properties instead of the descriptor. It's not the perfect solution but it wasn't very ugly either so it'll do. If you have a link to info on how to create custom graph types with special vertex descriptors please do let me know cheers Nick

1 0