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

[Graph] A* with heterogeneous heuristics
by Sensei 13 Nov '14

13 Nov '14

Dear all, I haven't given up in trying to implement an A* algorithm with BGL. My problem is theoretically simple, as in some previous posts. Given a graph of letters, and a word, find the path in the graph that minimizes the distance between the letters of the word and the nodes in the graph. It's best to show an example: /* * B H * / \ / * A---D---F---G---I * \ /\ * C E * * input: A E I O U * … [View More]result: A D F G I */ With that graph, my heuristic should take into account not just the letter in the graph per se, but the *corresponding* one in the input word. So, starting with "AEIOU" the search will: - expand A (A in **A**EIOU) - find B, C, D - expand D (closest to E in A**E**IOU) - find D, F - expand F (closest to I in AE**I**OU) - find G - expand G (only one, closest to O in AEI**O**U) - find H, I - expand U (closest to U in AEIO**U**) This settings could also be more complicated, adding weights to edges, but for now I am happy with this problem. What I've done now? Implementing my own A* algorithm, by hand. Of course this might work, but I'd prefer using BGL's facilities. I must say that I am quite confused about BGL's data structures, as for instance in the A* cities example (1), we need to create a weight map, so what if I don't need weights? Moreover, predecessors and distances are instantiated with a std::vector, but what happens if I need to operate on a very large graph, for instance 200M nodes? Moreover, what will happen when I will distribute the graph over a cluster with Boost Parallel Graph? ... Ok maybe this is too ahead of the time! :) Basically, I'd need to replicate my A* ugly by-hand implementation with custom visitors and custom heuristics. Below you may find my failed attempt. I need some help with this, because I find the documentation a little bit hard to understand, especially when some newbie like me approaches Boost :) Failures in my code: I can't get to define a non-weighted graph, and the call to the A* search is cryptic: I don't have weights. Should I define fake ones for instance all equal to 1? I really hope you guys can help me in this, my code works, but using BGL would be best! Thanks! (1) http://www.boost.org/doc/libs/1_57_0/libs/graph/example/astar-cities.cpp #include <iostream> #include <unordered_map> #include <vector> #include <string> #include <utility> #include <boost/graph/adjacency_list.hpp> #include <boost/graph/breadth_first_search.hpp> #include <boost/graph/depth_first_search.hpp> #include <boost/graph/astar_search.hpp> typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS > graph; typedef boost::graph_traits<graph>::edge_iterator edge_iterator; // Custom A* heuristic template <class Graph, class CostType> class bestmatch_heuristic : public boost::astar_heuristic<Graph, CostType> { public: typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex; bestmatch_heuristic() { }; CostType operator()(Vertex u) { std::cout << ">>>> h(" << u << ") = " << 1 << std::endl; return 1; } private: }; // Used to end the A* search algorithm struct end_astar { }; // Custom A* visitor template <class Vertex> class bestmatch_visitor : public boost::default_astar_visitor { public: bestmatch_visitor(Vertex goal) : destination_(goal) { }; template<class Graph> void discover_vertex(Vertex u, const Graph &g) { std::cout << "discover " << u << std::endl; } template <class Graph> void examine_vertex(Vertex u, Graph& g) { std::cout << "examine " << u << std::endl; if (u == destination_) throw end_astar(); } private: Vertex destination_; }; int main() { /* * B H * / \ / * A---D---F---G---I * \ /\ * C E * * input: A E I O U * result: A D F G I */ std::unordered_map<char, std::size_t> letters; auto getletter = [](std::size_t i) -> char { return 'A' + i; }; for (int i = 'A'; i <= 'I'; i++) letters[i] = i - 'A'; graph g; boost::add_edge(letters['A'], letters['B'], g); boost::add_edge(letters['A'], letters['C'], g); boost::add_edge(letters['A'], letters['D'], g); boost::add_edge(letters['B'], letters['D'], g); boost::add_edge(letters['C'], letters['D'], g); boost::add_edge(letters['D'], letters['E'], g); boost::add_edge(letters['D'], letters['F'], g); boost::add_edge(letters['F'], letters['G'], g); boost::add_edge(letters['G'], letters['H'], g); boost::add_edge(letters['G'], letters['I'], g); edge_iterator ei, ee; for (boost::tie(ei, ee) = boost::edges(g); ei != ee; ei++) { std::cout << getletter(boost::source(*ei, g)) << " -> " << getletter(boost::target(*ei, g)) << std::endl; } // Heuristics bestmatch_heuristic<graph, int> h; // Predecessors std::vector<graph::vertex_descriptor> p(boost::num_vertices(g)); try { #if 0 boost::astar_search_tree(// Graph g, // Start node letters['A'], // Heuristics bestmatch_heuristic<graph, int>(), // Predecessor map boost::predecessor_map(boost::make_iterator_property_map(p.begin(), boost::get(boost::vertex_index, g)))); #endif } catch (end_astar e) { } } [View Less]

1 0

[Mutli-Index, InterProcess] Multi-index stability issue with interprocess?
by vibhor aggarwal 13 Nov '14

13 Nov '14

I am creating a multi-index on three members of a class (two int32_t and one std::pair<int32_t, int32_t> and storing that in a managed memory mapped file (boos::interprocess). I am using GCC 4.8.2 for compilation and boost version 1.56.beta1All the data is first inserted into the multi-index once and then it is read from the muti-index with a query on the first two int32_t values (There is no concurrency and insertion and query is being done within the same process). The mutliindex is … [View More]

2 1

1.57.0 link errors (missing ctor/dtor for boost::archive::detail::shared_ptr_helper)
by David Abdurachmanov 13 Nov '14

13 Nov '14

Hi, I am moving to Boost 1.57.0 and having issues with some code related to serialization. https://github.com/cms-sw/cmssw/blob/CMSSW_7_3_X/CondFormats/Serialization/… https://github.com/cms-sw/cmssw/blob/CMSSW_7_3_X/CondFormats/Serialization/… In both cases the problem is here: #if BOOST_VERSION >= 103500 #include <boost/archive/shared_ptr_helper.hpp> #endif [snip] #if BOOST_VERSION >= 103500 // mix-in helper class for serializing shared_ptr , public boost::archive::detail::… [View More]

1 0

[serialization] Treatment of corrupt archives - assert vs. exception throw
by Gabriel Redner 12 Nov '14

12 Nov '14

Hi folks, I'm dealing with binary archives which may have been corrupted enroute to my code. My naive expectation was that the serialization library should throw an exception when it encounters something in the input stream it doesn't understand (in which case my code can react gracefully). But, I've found that: 1. There exist cases where serialization will just assert and bring down the process 2. The documentation suggests that an exception should be thrown, but I didn't find any strong … [View More]

3 3

BGL - shortest widest path
by Mark Fanara 12 Nov '14

12 Nov '14

I am trying to find the "shortest-widest path" between a single source and target node in an undirected graph (less than 25 nodes). (In my case, a shortest widest path is the maximum bandwidth path. If there are several such paths, it is the one with the least number of hops.) See W i k i p e d i a entry on "Widest path problem" I have successfully used dijkstra_shortest_paths() with a custom combine() function to find the maximum bandwidth path, however this does not take into account the … [View More]

1 0

[Test] failure linking tests dynamically
by Latimerius 11 Nov '14

11 Nov '14

Hello, I'm evaluating Boost.Test. I did the initial evaluation using the header-only variant and now I'd like to move to dynamic linking the Test library for a larger-scale deployment. However, all attempts so far failed due to Undefined symbols for architecture x86_64: "_main", referenced from: implicit entry/start for main executable ld: symbol(s) not found for architecture x86_64 I'd put it down to my lack of experience with Test, or Boost in general, however I noticed that … [View More]

2 4

boost.container.vector::operator==() bug?
by niXman 10 Nov '14

10 Nov '14

Hi, https://github.com/boostorg/container/blob/master/include/boost/container/v… Explained: if ( !(1 != 1) ) Another question is, why 'memcmp()' not used for vectors of fundamental types? -- Regards, niXman ___________________________________________________ Dual-target(32 & 64-bit) MinGW-W64 compilers for 32 and 64-bit Windows: http://sourceforge.net/projects/mingw-w64/ ___________________________________________________ Another online IDE: http://liveworkspace.org/

4 10

lockfree::spsc_queue & move semantics
by Thomas Danckaert 10 Nov '14

10 Nov '14

I'd like to use a spsc_queue of unique_ptr's to bigger objects, to transfer ownership between threads. That way, I can create/allocate an object in a non-realtime thread, then transfer ownership to a realtime thread using a lockfree queue, and, using another queue, pass on the unique_ptr to another thread that takes care of cleanup when the realtime thread no longer needs the it. For example: boost::lockfree::spsc_queue<unique_ptr<string>, boost::… [View More]

2 1

[scope_exit] 1.57 MSVC C4003 warning
by Filip Konvička 10 Nov '14

10 Nov '14

Hi, Any use of BOOST_SCOPE_EXIT in 1.57 seems to emit warning C4003 on MSVC 2012 and 2013: warning C4003: not enough actual parameters for macro 'BOOST_PP_EXPAND_I' Uncomment either line to suppress the warning. Is BOOST_PP_VARIADICS enabled by mistake for MSVC (especially 2013)? Should I explicitly set BOOST_PP_VARIADICS=0 for MSVC? Despite the warning, the code appears to work fine (i.e., the block of code gets properly called). Thanks, Filip #include <boost/version.hpp> #… [View More]

3 5

boost property tree for recursive structures
by Maurizio Vitale 10 Nov '14

10 Nov '14

Hello everybody, I'm trying to use the boost property tree library to represent recursive data structures, but although I can get the dumped json to look reasonable, I cannot traverse the ptree in any ways I've tried. The code below, compiles and run, except for the call to Dump in DumpAssign. Is there a way to traverse arbitrary trees where values can be themselves ptrees? I'm about to throw the towel and go with boost::seriaization, but I did like the traversal mechanisms property trees … [View More]offer. Any suggestion? Thanks, Maurizio #include <boost/any.hpp> #include <boost/assign/list_of.hpp> #include <boost/foreach.hpp> #include <boost/property_tree/json_parser.hpp> #include <boost/property_tree/ptree.hpp> #include <boost/property_tree/xml_parser.hpp> #include <iostream> #include <string> #include <vector> #include <map> using boost::property_tree::ptree; using boost::assign::list_of; using boost::assign::map_list_of; using namespace std; ptree Op(string type, ptree a1, ptree a2) { ptree pt; // pt.put_value(type); pt.put("type", type); ptree args; args.push_back(make_pair("", a1)); args.push_back(make_pair("", a2)); pt.add_child("args", args); return pt; } ptree Net(string name) { ptree pt; pt.put("type", "net"); pt.put("name", name); return pt; } ptree Assign(ptree lhs, ptree rhs) { ptree pt; pt.put("type", "assign"); pt.add_child("lhs", lhs); pt.add_child("rhs", rhs); return pt; } string Dump(ptree::value_type e); string DumpConcat(ptree::value_type e) { string result = "{"; bool first = true; BOOST_FOREACH(const ptree::value_type& child, e.second.get_child("args")) { if (not first) { result += ", "; first = false; } result += Dump(child); } return result + "}"; } string DumpNet(ptree::value_type e) { return e.second.get<std::string>("name"); } string DumpAssign(ptree::value_type e) { string result = "assign "; // HOW TO HAVE A RECURSIVE CALL TO Dump(lhs) HERE? result += Dump(?); return result; } string DumpNop(ptree::value_type) {return "NOP";} string Dump(ptree::value_type e) { static std::map<string, string(*)(ptree::value_type)> dump = map_list_of ("net", DumpNet) ("concat", DumpConcat) ("assign", DumpAssign) ("nop", DumpNop) ; string type = e.second.get<string>("type", "nop"); return dump[type](e); } int main(int, char**) { ptree pt; ptree a1; a1.push_back(make_pair("", Assign( Op("concat", Op("concat", Net("a1"), Net("a1")), Net("w")), Net("a2")))); pt.add_child("operators", a1); cout << "=============\n"; write_json(std::cout, pt); cout << "=============\n"; BOOST_FOREACH(const ptree::value_type& e, pt.get_child("operators")) { cout << "> " << Dump(e); } } [View Less]

1 0