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

BGL: A* search & implicit graph
by Damien Maupu 01 Mar '10

01 Mar '10

Hi, Some weeks ago, I wrote on this mailing list, that I succeed achieving an A* search using an implicit graph. A Boost user emailed me to send him an example of my implementation. As the web is lacking of such example, I think the best place to send such example would be here as it might help others in the future. My example might not be the best, the most optimized or most well-coded. I am open to suggestions, corrections and comments. Let me know if something unclear. The code comes below. Few words to quickly explain the code: The goal is to A* search a graph (named m_SearchGraph) that grows (i.e. m_SearchGraph is implicit) based on another graph (named MyGraph). The search starts from 2D point (_startX, _startZ) and must get enough close (less than error "_epsilon") to 2D point (_goalX, _goalZ). The example is dumb and simply increment current position whatever the node in MyGraph (i.e. currX++, currZ++, currWeight += sqrt(2)). User need to adapt this dummy behavior depending on its needs (search for "//to change"). Most adaptations have to be done in "examine_vertex" (and also by providing ref/ptr to needed objects to the visitor constructor) PS: The implementation assumes both graphs are adjacency_list with "vecs" for both edges and vertices (in which a vertex/edge descriptor is equivalent to an "int", for my understanding) PS2: Id == descriptor (e.g. edgeId == edge_descriptor) ==================================================================================== ==================================================================================== astarSearch.h ==================================================================================== #ifndef ASTARSEARCH_H #define ASTARSEARCH_H #include <boost/graph/astar_search.hpp> #include "myGraph.h" class AStarSearch { public: AStarSearch(MyGraph * _myGraph); virtual ~AStarSearch(); bool findPath(MyGraph::VertexId _startMyGraphVertextId, double _startX, double _startZ, double _goalX, double _goalZ, double _epsilon); private: //search graph struct m_Vertex { m_Vertex() { currX = 0.0; currZ = 0.0; refMyGraphVertexId = -1; prevVertexId = -1; double inf = numeric_limits<double>::max BOOST_PREVENT_MACRO_SUBSTITUTION (); distance = inf; cost = inf; color = white_color; } //properties for heuristic / visitor double currX; double currZ; int refMyGraphVertexId; //reference to correspondant vertex in myGraph //properties required by astar_search_no_init(...) int prevVertexId; // == predecessor double distance; double cost; default_color_type color; }; struct m_Edge { m_Edge() { weight = 0.0; } double weight; }; //graph property = save the vertex id when goal is reached //saving goal vertex could be also saved by a reference to an int passed to the visitor class typedef property<graph_name_t, int> m_GraphProperty; typedef adjacency_list<vecS, vecS, directedS, m_Vertex, m_Edge, m_GraphProperty> m_SearchGraph; typedef graph_traits<m_SearchGraph>::vertex_descriptor m_VertexId; typedef graph_traits<m_SearchGraph>::edge_descriptor m_EdgeId; typedef graph_traits<m_SearchGraph>::vertex_iterator m_VertexIt; typedef graph_traits<m_SearchGraph>::adjacency_iterator m_AdjacencyIt; typedef graph_traits<m_SearchGraph>::edge_iterator m_EdgeIt; typedef graph_traits<m_SearchGraph>::out_edge_iterator m_OutEdgeIt; //heuristic class m_Heuristic : public astar_heuristic<m_SearchGraph, double> { public: m_Heuristic(m_SearchGraph & _searchGraph, double _goalX, double _goalZ); virtual ~m_Heuristic(); double operator()(m_VertexId _currVertexId); private: m_SearchGraph & m_searchGraph; double m_goalX; double m_goalZ; }; //exception to end search struct m_endSearch{}; //visitor class m_Visitor : public default_astar_visitor { public: m_Visitor(MyGraph * _myGraph, m_SearchGraph & _searchGraph, double _goalX, double _goalZ, double _epsilon); virtual ~m_Visitor(); void examine_vertex(m_VertexId _currVertexId, const m_SearchGraph & _graph); private: MyGraph * m_myGraph; m_SearchGraph & m_searchGraph; double m_goalX; double m_goalZ; double m_epsilon; }; void m_printSearchGraph(m_SearchGraph & _searchGraph); list<int> m_getPath(m_SearchGraph & _searchGraph, m_VertexId _vertexId); vector< list<int> > m_getAllPaths(m_SearchGraph & _searchGraph); void m_printPath(list<int> _path); void m_printShortestPath(m_SearchGraph & _searchGraph); void m_printAllPaths(m_SearchGraph & _searchGraph); MyGraph * m_myGraph; }; #endif ==================================================================================== ==================================================================================== ==================================================================================== aStarSearch.cpp ==================================================================================== ==================================================================================== #include "aStarSearch.h" AStarSearch::AStarSearch(MyGraph * _myGraph): m_myGraph(_myGraph) { } AStarSearch::~AStarSearch() { } bool AStarSearch::findPath(MyGraph::VertexId _startMyGraphVertextId, double _startX, double _startZ, double _goalX, double _goalZ, double _epsilon) { m_SearchGraph searchGraph; m_Heuristic heuristic(searchGraph, _goalX, _goalZ); m_Visitor visitor(m_myGraph, searchGraph, _goalX, _goalZ, _epsilon); //typedef property maps typedef property_map<m_SearchGraph, vertex_index_t>::type IndexMap; typedef property_map<m_SearchGraph, double m_Edge::*>::type WeightMap; typedef property_map<m_SearchGraph, int m_Vertex::*>::type PredecessorMap; typedef property_map<m_SearchGraph, double m_Vertex::*>::type DistanceMap; typedef property_map<m_SearchGraph, double m_Vertex::*>::type CostMap; typedef property_map<m_SearchGraph, default_color_type m_Vertex::*>::type ColorMap; //create property maps IndexMap indexMap = get(vertex_index, searchGraph); WeightMap weightMap = get(&m_Edge::weight, searchGraph); PredecessorMap predecessorMap = get(&m_Vertex::prevVertexId, searchGraph); DistanceMap distanceMap = get(&m_Vertex::distance, searchGraph); CostMap costMap = get(&m_Vertex::cost, searchGraph); ColorMap colorMap = get(&m_Vertex::color, searchGraph); double inf = numeric_limits<double>::max BOOST_PREVENT_MACRO_SUBSTITUTION (); double zero = double(); //add & init first vertex m_VertexId startVertexId = add_vertex(searchGraph); m_Vertex & startVertex = searchGraph[startVertexId]; startVertex.currX = _startX; startVertex.currZ = _startZ; startVertex.refMyGraphVertexId = _startMyGraphVertextId; startVertex.prevVertexId = startVertexId; startVertex.distance = zero; startVertex.cost = heuristic(startVertexId); try { astar_search_no_init(searchGraph, startVertexId, heuristic, visitor, predecessorMap, costMap, distanceMap, weightMap, colorMap, indexMap, std::less<double>(), std::plus<double>(), inf, zero); } catch(m_endSearch end) { m_printSearchGraph(searchGraph); m_printShortestPath(searchGraph); m_printAllPaths(searchGraph); return true; } return false; } AStarSearch::m_Heuristic::m_Heuristic(m_SearchGraph & _searchGraph, double _goalX, double _goalZ): m_searchGraph(_searchGraph), m_goalX(_goalX), m_goalZ(_goalZ) { } AStarSearch::m_Heuristic::~m_Heuristic() { } double AStarSearch::m_Heuristic::operator()(m_VertexId _currVertexId) { m_Vertex currVertex = m_searchGraph[_currVertexId]; return sqrt(pow(m_goalX - currVertex.currX, 2) + pow(m_goalZ - currVertex.currZ, 2)); //for A* search //return 0; //for BFS search } AStarSearch::m_Visitor::m_Visitor(MyGraph * _myGraph, m_SearchGraph & _searchGraph, double _goalX, double _goalZ, double _epsilon): m_myGraph(_myGraph), m_searchGraph(_searchGraph), m_goalX(_goalX), m_goalZ(_goalZ), m_epsilon(_epsilon) { } AStarSearch::m_Visitor::~m_Visitor() { } void AStarSearch::m_Visitor::examine_vertex(m_VertexId _currVertexId, const m_SearchGraph & _graph) { //get currVertex / currX / currZ m_Vertex currVertex = m_searchGraph[_currVertexId]; double currX = currVertex.currX; double currZ = currVertex.currZ; //check if goal is reached if(sqrt(pow(m_goalX - currX, 2) + pow(m_goalZ - currZ, 2)) < m_epsilon) { set_property(m_searchGraph, graph_name, _currVertexId); //_currVertexId == goal vertex id throw m_endSearch(); } //declare currMyGraphVertexId / nextMyGraphVertexId / currMyGraphEdgeId / currMyGraphEdge MyGraph::VertexId currMyGraphVertexId = currVertex.refMyGraphVertexId; MyGraph::VertexId nextMyGraphVertexId; MyGraph::EdgeId currMyGraphEdgeId; bool currMyGraphEdgeExists; MyGraph::Edge currMyGraphEdge; //declare newVertexId / newEdgeId / newEdge m_VertexId newVertexId; m_EdgeId newEdgeId; bool newEdgeCreated; //generate neighbors to currVertex MyGraph::OutEdgeIt outMyGraph_i, outMyGraph_end; for(tie(outMyGraph_i, outMyGraph_end) = out_edges(currMyGraphVertexId, *m_myGraph); outMyGraph_i != outMyGraph_end ; ++outMyGraph_i) { //get nexMyGraphVertexId / currMyGraphEdgeId / currMyGraphEdge nextMyGraphVertexId = target(*outMyGraph_i, *m_myGraph); tie(currMyGraphEdgeId, currMyGraphEdgeExists) = edge(currMyGraphVertexId, nextMyGraphVertexId, *m_myGraph); if(currMyGraphEdgeExists) currMyGraphEdge = (*m_myGraph)[currMyGraphEdgeId]; else exit(1); //add/set newVertex newVertexId = add_vertex(m_searchGraph); m_Vertex & newVertex = m_searchGraph[newVertexId]; newVertex.currX = currX + 1; //to change newVertex.currZ = currZ + 1; //to change newVertex.refMyGraphVertexId = nextMyGraphVertexId; newVertex.prevVertexId = newVertexId; //add/set newEdge tie(newEdgeId, newEdgeCreated) = add_edge(_currVertexId, newVertexId, m_searchGraph); if(newEdgeCreated) { m_Edge & newEdge = m_searchGraph[newEdgeId]; newEdge.weight = sqrt(2); //to change } else exit(1); } } void AStarSearch::m_printSearchGraph(m_SearchGraph & _searchGraph) { m_Vertex currVertex; m_VertexIt v_i, v_end; printf("id\t"); printf("id prev\t"); printf("id ref\t"); printf("dist\t"); printf("cost\t\t"); printf("color\t"); printf("\n"); for(tie(v_i, v_end) = vertices(_searchGraph); v_i != v_end; ++v_i) { currVertex = _searchGraph[*v_i]; printf("%i\t", *v_i); printf("%i\t", currVertex.prevVertexId); printf("%i\t", currVertex.refMyGraphVertexId); printf("%f\t", currVertex.distance); printf("%f\t", currVertex.cost); printf("%i\t", currVertex.color); printf("\n"); } printf("\n"); } list<int> AStarSearch::m_getPath(m_SearchGraph & _searchGraph, m_VertexId _vertexId) { list<int> path; for(m_VertexId currVertexId = _vertexId; ; //cf if()... break; below for stopping condition currVertexId = _searchGraph[currVertexId].prevVertexId) { path.push_front(currVertexId); if(_searchGraph[currVertexId].prevVertexId == int(currVertexId)) break; } return path; } vector< list<int> > AStarSearch::m_getAllPaths(m_SearchGraph & _searchGraph) { m_VertexIt v_i, v_begin, v_end; for(tie(v_i, v_end) = vertices(_searchGraph); v_i != v_end; ++v_i) { _searchGraph[*v_i].color = white_color; } vector< list<int> > allPaths; tie(v_begin, v_i) = vertices(_searchGraph); for(--v_i;; --v_i) { //printf("curr vertex %i\tcolor:%i\n", *v_i, _searchGraph[*v_i].color); if(_searchGraph[*v_i].color == white_color) { list<int> newPath = m_getPath(_searchGraph, *v_i); list<int>::iterator currVertex; for(currVertex = newPath.begin(); currVertex != newPath.end(); ++currVertex) { _searchGraph[*currVertex].color = black_color; } allPaths.push_back(newPath); } if(v_i == v_begin) break; } return allPaths; } void AStarSearch::m_printPath(list<int> _path) { list<int>::iterator pathIt; for(pathIt = _path.begin(); pathIt != _path.end(); ++pathIt) { printf("%i\t", *pathIt); } printf("\n"); } void AStarSearch::m_printShortestPath(m_SearchGraph & _searchGraph) { printf("shortest path:\n"); m_printPath(m_getPath(_searchGraph, get_property(_searchGraph, graph_name))); } void AStarSearch::m_printAllPaths(m_SearchGraph & _searchGraph) { vector< list<int> > allPaths = m_getAllPaths(_searchGraph); printf("all paths:\n"); vector< list<int> >::iterator currPath; for(currPath = allPaths.begin(); currPath != allPaths.end(); ++currPath) { m_printPath(*currPath); } } ==================================================================================== Cheers, Damien

2 1

Re: [Boost-users] multinomial tree-like container
by Hicham Mouline 01 Mar '10

01 Mar '10

-----Original Message----- From: "Hicham Mouline" [hicham(a)mouline.org] Date: 01/03/2010 10:53 AM To: boost-users(a)lists.boost.org Subject: Re: multinomial tree-like container Hello, Is there a library that provides a public container that has the structure of a tree where there are top nodes, and each node can have 0 to N children? regards, ----------------------------------------------------------------------------- I just found in the boost vault the tree-soc2006 container that seems exactly what I need. Has there been any changes since 2006 in that library? regards,

1 0

boost::asio::deadline_timer precision issues
by Warren Seine 01 Mar '10

01 Mar '10

Hi, I'm writing a timer class which calls a function every n ms. I'm using Boost.Asio to achieve that. Please tell me if there is a better solution. The usual pattern with boost::asio::deadline_timer is to call `expires_from_now()' and `async_wait()' every time the timer expires. The solution works, however the timer seems to have (important) precision issues, as described in the sample code below. A simple counter is incremented every 20 ms, and is displayed (and reset) every 1000 ms. The value displayed should therefore be close to 50. In practice, it's closer to 40, which in unexplainable with such a simple piece of code. $ cat test.cc #include <boost/asio/io_service.hpp> #include <boost/asio/deadline_timer.hpp> #include <boost/function.hpp> #include <boost/bind.hpp> #include <boost/date_time/posix_time/posix_time.hpp> #include <iostream> static boost::asio::io_service* s_service = 0; static unsigned int s_counter = 0; struct timer { timer(unsigned int delay, boost::function< void () > callback) : m_timer(*s_service), m_callback(callback), m_delay(delay) { } void start() { m_timer.expires_from_now(boost::posix_time::millisec(m_delay)); m_timer.async_wait(boost::bind(&timer::handle_wait, this, _1)); } void handle_wait(const boost::system::error_code& e) { start(); m_callback(); } boost::asio::deadline_timer m_timer; boost::function< void () > m_callback; unsigned int m_delay; }; void increment() { s_counter++; } void display() { std::cout << s_counter << std::endl; s_counter = 0; } int main() { boost::asio::io_service service; s_service = &service; // Display the counter every 1000ms. timer t1(1000, display); // Increment the counter every 20ms. timer t2(20, increment); t1.start(); t2.start(); service.run(); } $ g++ test.cc -o test -lboost_system $ ./test 41 42 43 40 42 43 42 ^C My environment is GNU/Linux within a VM. My compiler is GCC 4.4 and I'm linking with Boost 1.42. Please ask me any detail that might be relevant. If that's an expected behavior, is there any way I can "trust" the timer? I couldn't find any documentation discussing the issue. Thanks, -- Warren Seine

2 3

multi index container descending order, without reverse iterator
by Andrew Kokkalis 01 Mar '10

01 Mar '10

Hello, I'm using a multi_index container, non uniquely ordered by a float. I want to access it by descending order, but when i'm using reverse iterator, i cannot use erase. Is there an way to delete the last element? it--; is not defined. erase(data_set.end()) does not work , end indicates after the last element. Thank you very much, i'm in great hurry, and i don't have time to look the tutorials right now. Thank you in advance, Andrew Kokkalis

2 1

[fusion] clarification on stateful unary function objects
by Matthias Vallentin 01 Mar '10

01 Mar '10

Hi there, While trying to use a stateful unary function objects, I stumbled over and old discussion from 2007 [1]. From the current Fusion documentation, I understand that the functor passed to the for_each algorithm must satisfy the Regular Callable Object concept. I presume that regularity, which I understand as replacing inputs with equal objects results in equal outputs, here implies that operator()(T& x) must be const. In other words, mutable function objects are not supported. As pointed out in [1], it is of course possible to bypass this restriction by defining the state that needs to changed as mutable. I was wondering if this is still the correct way to deal with mutable function objects, as illustrated in the small example below: #include <iostream> #include <string> #include <boost/bind.hpp> #include <boost/fusion/include/algorithm.hpp> #include <boost/fusion/include/container.hpp> struct container { struct printer { template <typename T> void operator()(T& x) const { std::cout << ++i << ": " << x << std::endl; } mutable unsigned i; }; template <typename T> void write(const T& row) { boost::fusion::for_each(row, printer()); } }; int main() { int i = 42; unsigned j = 7; std::string s = "foo"; container c; c.write(boost::fusion::vector_tie(i, j, s)); return 0; } Matthias [1] http://lists.boost.org/boost-users/2007/03/26338.php -- Matthias Vallentin vallentin(a)icsi.berkeley.edu http://www.icir.org/matthias

2 2

Re: [Boost-users] [GIL new_io] range of gil floating point images
by Robert Lupton the Good 01 Mar '10

01 Mar '10

> Float and double are perfectly valid GIL channels, but their scope is ?inf to inf, so you cannot linearly interpolate from a float to an uint8, for example. Thus they are not as useful as bits32f This has been a nuisance for us too --- we use gil to represent data from a telescope, where the scaling is a real pain as the floating point numbers represent the data read from the detectors. It'd be nice if gil came with the needed typedefs for pure floating (32 and 64 bit) images/views (as well as the ones that scale in [0,1] which are presumably what others want). It's too late to call the unscaled types 32f, but isn't 32F still available? R

1 0

[ptr_container] view_clone_allocator with associative containers
by Matthias Vallentin 01 Mar '10

01 Mar '10

I cannot get the view_clone_allocator to work with associative containers, as in the example below: boost::ptr_vector<int> vec; boost::ptr__map<std::string, int, boost::view_clone_allocator> map; int* i = new int(42); vec.push_back(i); std::string k("foo"); map.insert(k, i); >From the error message, it seems that the CloneAllocator is still of type boost::heap_clone_allocator. Why is this failing? It seems intuitive to specify the allocator as third parameter, similar to the example with ptr_vector where the allocator is the second argument. Matthias -- Matthias Vallentin vallentin(a)icsi.berkeley.edu http://www.icir.org/matthias

2 2

array definition
by Damien MATTEI 01 Mar '10

01 Mar '10

hello, i have this definition that works: array_2D_double psf_cartesian_centered(boost::extents[range_ext(indiceBegin,indiceEnd+1)][range_ext(indiceBegin,indiceEnd+1)]); but i want to use this writing to improve reading of my code in a more natural way: array_2D_double psf_cartesian_centered2[ boost::indices[indiceBegin <= array_2D_double::index_range() < indiceEnd][indiceBegin <= array_2D_double::index_range() < indiceEnd] ]; unfornunately this does not work , i read one hundred times the boost tutorial and documention qhere it is written something like this should ... what is my error? regards, damien

1 0

Have Boost random Library contained the function for generating Gaussian noise ? Can any one with kindness help me?
by fmingu 01 Mar '10

01 Mar '10

I am a new comer and using Boost library for math works. I want to know whether Boost Random Library contained the function for generating Gaussian noise. Or Gaussian noise can be easily generated by the functions in Boost Random Library? Or any other library compatible with the Boost Random Library? Can any one with kindness help me?

2 1

best boost cc-mode style
by Russell L. Carter 01 Mar '10

01 Mar '10

Hi folks, I'm starting to get heavy into templates and it seems my ancient cc-mode customizations are a disaster when trying to format complicated template code. I'm now using emacs23 with cc-mode version 5.31.7. What's the best out-of-the-box cc-mode style for boost style template formatting? (Some googling revealed that Dave A. a long time ago made some mods to cc-mode, what style did they end up in?) tnks, Russell

1 0