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

dijkstra_shortest_paths with a graph with bundled edge properties
by David Doria 27 Oct '11

27 Oct '11

This example works fine: http://programmingexamples.net/index.php?title=CPP/Boost/BGL/DijkstraUndire… However, if I change typedef boost::property<boost::edge_weight_t, float> EdgeWeightProperty; to struct EdgeWeightProperty{float weight;}; (and of course remove the lines adding the weights as properties: boost::add_edge(v1, v2, weight1, g); ) I get crazy template errors: /usr/include/boost/graph/dijkstra_shortest_paths.hpp: In member function ‘void boost::detail::dijkstra_bfs_visitor<UniformCostVisitor, UpdatableQueue, WeightMap, PredecessorMap, DistanceMap, BinaryFunction, BinaryPredicate>::examine_edge(Edge, Graph&) [with Edge = boost::detail::edge_desc_impl<boost::undirected_tag, unsigned int>, Graph = const boost::adjacency_list<boost::listS, boost::vecS, boost::undirectedS, boost::no_property, EdgeWeightProperty>, UniformCostVisitor = boost::dijkstra_visitor<>, UpdatableQueue = boost::d_ary_heap_indirect<unsigned int, 4u, boost::iterator_property_map<unsigned int*, boost::vec_adj_list_vertex_id_map<boost::no_property, unsigned int>, unsigned int, unsigned int&>, int*, std::less<int>, std::vector<unsigned int> >, WeightMap = boost::adj_list_edge_property_map<boost::undirected_tag, boost::detail::error_property_not_found, const boost::detail::error_property_not_found&, unsigned int, const boost::property<boost::edge_bundle_t, EdgeWeightProperty, boost::no_property>, boost::edge_weight_t>, PredecessorMap = unsigned int*, DistanceMap = int*, BinaryFunction = boost::closed_plus<int>, BinaryPredicate = std::less<int>]’: /usr/include/boost/graph/breadth_first_search.hpp:77:47: instantiated from ‘void boost::breadth_first_visit(const IncidenceGraph&, typename boost::graph_traits<IncidenceGraph>::vertex_descriptor, Buffer&, BFSVisitor, ColorMap) [with IncidenceGraph = boost::adjacency_list<boost::listS, boost::vecS, boost::undirectedS, boost::no_property, EdgeWeightProperty>, Buffer = boost::d_ary_heap_indirect<unsigned int, 4u, boost::iterator_property_map<unsigned int*, boost::vec_adj_list_vertex_id_map<boost::no_property, unsigned int>, unsigned int, unsigned int&>, int*, std::less<int>, std::vector<unsigned int> >, BFSVisitor = boost::detail::dijkstra_bfs_visitor<boost::dijkstra_visitor<>, boost::d_ary_heap_indirect<unsigned int, 4u, boost::iterator_property_map<unsigned int*, boost::vec_adj_list_vertex_id_map<boost::no_property, unsigned int>, unsigned int, unsigned int&>, int*, std::less<int>, std::vector<unsigned int> >, boost::adj_list_edge_property_map<boost::undirected_tag, boost::detail::error_property_not_found, const boost::detail::error_property_not_found&, unsigned int, const boost::property<boost::edge_bundle_t, EdgeWeightProperty, boost::no_property>, boost::edge_weight_t>, unsigned int*, int*, boost::closed_plus<int>, std::less<int> >, ColorMap = boost::two_bit_color_map<boost::vec_adj_list_vertex_id_map<boost::no_property, unsigned int> >, typename boost::graph_traits<IncidenceGraph>::vertex_descriptor = unsigned int]’ /usr/include/boost/graph/dijkstra_shortest_paths.hpp:332:5: instantiated from ‘void boost::dijkstra_shortest_paths_no_init(const Graph&, typename boost::graph_traits<Graph>::vertex_descriptor, PredecessorMap, DistanceMap, WeightMap, IndexMap, Compare, Combine, DistZero, DijkstraVisitor, ColorMap) [with Graph = boost::adjacency_list<boost::listS, boost::vecS, boost::undirectedS, boost::no_property, EdgeWeightProperty>, DijkstraVisitor = boost::dijkstra_visitor<>, PredecessorMap = unsigned int*, DistanceMap = int*, WeightMap = boost::adj_list_edge_property_map<boost::undirected_tag, boost::detail::error_property_not_found, const boost::detail::error_property_not_found&, unsigned int, const boost::property<boost::edge_bundle_t, EdgeWeightProperty, boost::no_property>, boost::edge_weight_t>, IndexMap = boost::vec_adj_list_vertex_id_map<boost::no_property, unsigned int>, Compare = std::less<int>, Combine = boost::closed_plus<int>, DistZero = int, ColorMap = boost::two_bit_color_map<boost::vec_adj_list_vertex_id_map<boost::no_property, unsigned int> >, typename boost::graph_traits<Graph>::vertex_descriptor = unsigned int]’ /usr/include/boost/graph/dijkstra_shortest_paths.hpp:383:5: instantiated from ‘void boost::dijkstra_shortest_paths(const VertexListGraph&, typename boost::graph_traits<VertexListGraph>::vertex_descriptor, PredecessorMap, DistanceMap, WeightMap, IndexMap, Compare, Combine, DistInf, DistZero, DijkstraVisitor, ColorMap) [with VertexListGraph = boost::adjacency_list<boost::listS, boost::vecS, boost::undirectedS, boost::no_property, EdgeWeightProperty>, DijkstraVisitor = boost::dijkstra_visitor<>, PredecessorMap = unsigned int*, DistanceMap = int*, WeightMap = boost::adj_list_edge_property_map<boost::undirected_tag, boost::detail::error_property_not_found, const boost::detail::error_property_not_found&, unsigned int, const boost::property<boost::edge_bundle_t, EdgeWeightProperty, boost::no_property>, boost::edge_weight_t>, IndexMap = boost::vec_adj_list_vertex_id_map<boost::no_property, unsigned int>, Compare = std::less<int>, Combine = boost::closed_plus<int>, DistInf = int, DistZero = int, ColorMap = boost::two_bit_color_map<boost::vec_adj_list_vertex_id_map<boost::no_property, unsigned int> >, typename boost::graph_traits<VertexListGraph>::vertex_descriptor = unsigned int]’ /usr/include/boost/graph/dijkstra_shortest_paths.hpp:353:5: instantiated from ‘void boost::dijkstra_shortest_paths(const VertexListGraph&, typename boost::graph_traits<VertexListGraph>::vertex_descriptor, PredecessorMap, DistanceMap, WeightMap, IndexMap, Compare, Combine, DistInf, DistZero, DijkstraVisitor, const boost::bgl_named_params<T, Tag, Base>&, typename boost::enable_if_c<boost::is_base_and_derived<boost::vertex_list_graph_tag, typename boost::graph_traits<VertexListGraph>::traversal_category>::value, boost::graph::detail::no_parameter>::type) [with VertexListGraph = boost::adjacency_list<boost::listS, boost::vecS, boost::undirectedS, boost::no_property, EdgeWeightProperty>, DijkstraVisitor = boost::dijkstra_visitor<>, PredecessorMap = unsigned int*, DistanceMap = int*, WeightMap = boost::adj_list_edge_property_map<boost::undirected_tag, boost::detail::error_property_not_found, const boost::detail::error_property_not_found&, unsigned int, const boost::property<boost::edge_bundle_t, EdgeWeightProperty, boost::no_property>, boost::edge_weight_t>, IndexMap = boost::vec_adj_list_vertex_id_map<boost::no_property, unsigned int>, Compare = std::less<int>, Combine = boost::closed_plus<int>, DistInf = int, DistZero = int, T = int*, Tag = boost::vertex_distance_t, Base = boost::bgl_named_params<unsigned int*, boost::vertex_predecessor_t, boost::no_property>, typename boost::graph_traits<VertexListGraph>::vertex_descriptor = unsigned int, typename boost::enable_if_c<boost::is_base_and_derived<boost::vertex_list_graph_tag, typename boost::graph_traits<VertexListGraph>::traversal_category>::value, boost::graph::detail::no_parameter>::type = boost::graph::detail::no_parameter]’ /usr/include/boost/graph/dijkstra_shortest_paths.hpp:423:7: instantiated from ‘void boost::detail::dijkstra_dispatch2(const VertexListGraph&, typename boost::graph_traits<VertexListGraph>::vertex_descriptor, DistanceMap, WeightMap, IndexMap, const Params&) [with VertexListGraph = boost::adjacency_list<boost::listS, boost::vecS, boost::undirectedS, boost::no_property, EdgeWeightProperty>, DistanceMap = int*, WeightMap = boost::adj_list_edge_property_map<boost::undirected_tag, boost::detail::error_property_not_found, const boost::detail::error_property_not_found&, unsigned int, const boost::property<boost::edge_bundle_t, EdgeWeightProperty, boost::no_property>, boost::edge_weight_t>, IndexMap = boost::vec_adj_list_vertex_id_map<boost::no_property, unsigned int>, Params = boost::bgl_named_params<int*, boost::vertex_distance_t, boost::bgl_named_params<unsigned int*, boost::vertex_predecessor_t, boost::no_property> >, typename boost::graph_traits<VertexListGraph>::vertex_descriptor = unsigned int]’ /usr/include/boost/graph/dijkstra_shortest_paths.hpp:455:7: instantiated from ‘void boost::detail::dijkstra_dispatch1(const VertexListGraph&, typename boost::graph_traits<VertexListGraph>::vertex_descriptor, DistanceMap, WeightMap, IndexMap, const Params&) [with VertexListGraph = boost::adjacency_list<boost::listS, boost::vecS, boost::undirectedS, boost::no_property, EdgeWeightProperty>, DistanceMap = int*, WeightMap = boost::adj_list_edge_property_map<boost::undirected_tag, boost::detail::error_property_not_found, const boost::detail::error_property_not_found&, unsigned int, const boost::property<boost::edge_bundle_t, EdgeWeightProperty, boost::no_property>, boost::edge_weight_t>, IndexMap = boost::vec_adj_list_vertex_id_map<boost::no_property, unsigned int>, Params = boost::bgl_named_params<int*, boost::vertex_distance_t, boost::bgl_named_params<unsigned int*, boost::vertex_predecessor_t, boost::no_property> >, typename boost::graph_traits<VertexListGraph>::vertex_descriptor = unsigned int]’ /usr/include/boost/graph/dijkstra_shortest_paths.hpp:473:5: instantiated from ‘void boost::dijkstra_shortest_paths(const VertexListGraph&, typename boost::graph_traits<IncidenceGraph>::vertex_descriptor, const boost::bgl_named_params<P, T, R>&) [with VertexListGraph = boost::adjacency_list<boost::listS, boost::vecS, boost::undirectedS, boost::no_property, EdgeWeightProperty>, Param = int*, Tag = boost::vertex_distance_t, Rest = boost::bgl_named_params<unsigned int*, boost::vertex_predecessor_t, boost::no_property>, typename boost::graph_traits<IncidenceGraph>::vertex_descriptor = unsigned int]’ Any chance anyone can interpret these? Thanks, David

2 2

"Cannot Open Shared Object File" only present when run as cron
by Russ Jones 27 Oct '11

27 Oct '11

Hey folks, I'm currently using Boost to hold a statistical model in memory but am running into a problem. When run directly from the command line (as root), there are no issues, but when the same is run as a cron job, the following error is present... "/root/pylda/src/infer: error while loading shared libraries: libboost_program_options.so.1.46.1: cannot open shared object file: No such file or directory" Not quite sure what would change between running the same script as root user vs cron (I believe the cron is running as root, anyway). Have any of you experienced a similar problem? Thanks in advance, Russ Jones

2 1

[1.48.0] Beta 1 is now available from SourceForge
by Beman Dawes 27 Oct '11

27 Oct '11

Boost release 1.48.0 beta 1 is now available from SourceForge See http://sourceforge.net/projects/boost/files/boost/1.48.0.beta.1/ This release includes 3 new libraries (Container, Locale and Move), an extension to TypeTraits to support operator detection as well as updates to many existing libraries. For partial details of what's in the release, see http://beta.boost.org/users/history/version_1_48_0.html. This page is still in process of being updated, and there are some known issues with links. Please download the beta, give it a try, and report any problems you encounter. Thanks, -- The Boost Release Team Beman Dawes Daniel James Eric Niebler Rene Rivera Vladimir Prus

1 0

Cross Compiling Boost.serialisation
by David.Allen＠generaldynamics.uk.com 27 Oct '11

27 Oct '11

Hello, Has anyone experienced the multiple link errors when trying to cross compile boost serialisation to the ARM platform ? The version of boost I am trying to build is 1.38. A copy of the output is attached. I am using the arm-angstrom compiler and linker. I believe I have captured all the correct compiler and linker flags and settings from inspection of other boost builds for Ubuntu. Any help gratefully received. Regards, Dave This email and any files attached are intended for the addressee and may contain information of a confidential nature. If you are not the intended recipient, be aware that this email was sent to you in error and you should not disclose, distribute, print, copy or make other use of this email or its attachments. Such actions, in fact, may be unlawful. In compliance with the various Regulations and Acts, General Dynamics United Kingdom Limited reserves the right to monitor (and examine for viruses) all emails and email attachments, both inbound and outbound. Email communications and their attachments may not be secure or error- or virus-free and the company does not accept liability or responsibility for such matters or the consequences thereof. General Dynamics United Kingdom Limited, Registered Office: 21 Holborn Viaduct, London EC1A 2DY. Registered in England and Wales No: 1911653.

1 0

[graph] std::priority_queue of vertex_descriptors with extended comparison object will not initialize
by Christoph 27 Oct '11

27 Oct '11

Hi List, as the Subject states. I would like to initialize a std::priority_queue with vertex_descriptors and a comparison object as a template parameter but the compiler tells me: ... /usr/include/c++/4.5/bits/stl_heap.h:303:4: error: invalid conversion from ‘unsigned int’ to ‘void*’ /usr/include/c++/4.5/bits/stl_heap.h:303:4: error: initializing argument 1 of ‘bool degree_compare::operator()(void* const&, void* const&)’ ... if i try to initialize the queue and i just don't know why 'bool degree_compare::operator()(void* const&, void* const&)' comes up. Could you please help me to initialize my priority_queue? best regards Christoph // begin code #include <iostream> #include <map> #include <queue> #include <boost/graph/adjacency_list.hpp> #include <boost/smart_ptr.hpp> typedef boost::adjacency_list_traits<boost::listS, boost::vecS, boost::bidirectionalS> link_adjacency_list_traits; struct vertex_properties; struct edge_properties; struct graph_properties; struct vertex_properties { std::map <int, link_adjacency_list_traits::edge_descriptor > used_colors; // this one works fine, i can use a traits::edge_descriptor }; struct edge_properties { int color; }; struct degree_compare; typedef std::priority_queue < link_adjacency_list_traits::vertex_descriptor, std::vector <link_adjacency_list_traits::vertex_descriptor>, degree_compare> VERTEX_DEGREE_PQ; struct graph_properties { int delta; boost::shared_ptr <VERTEX_DEGREE_PQ> pq; }; typedef boost::adjacency_list < boost::listS, boost::listS, boost::bidirectionalS, vertex_properties, edge_properties, graph_properties> link_graph; class degree_compare { private: link_graph g; public: degree_compare(const link_graph &g): g(g) {std::cout << "Num Vertices: " << num_vertices(g) << std::endl;} bool operator()(const boost::graph_traits<link_graph>::vertex_descriptor &a, const boost::graph_traits<link_graph>::vertex_descriptor &b) { return out_degree(a, g) < out_degree(b, g); } }; int main () { link_graph g; boost::graph_traits<link_graph>::vertex_descriptor a = add_vertex (g); degree_compare dc(g); // init the comparison object VERTEX_DEGREE_PQ pq(dc);// init the p_queue with comparison // object fails //pq.push(a); //pq.top(); } // end code

1 1

[Preprocessor] documentation link broken
by Belcourt, K. Noel 27 Oct '11

27 Oct '11

Hi, There's a web page misdirect for the MPL library. If you go here: http://www.boost.org/doc/libs/1_47_0/libs/preprocessor/doc/index.html and click Introduction, it will attempt to go here: http://boost-consulting.com/tmpbook/preprocessor.html and be redirected here: http://www.boostpro.com/tmpbook/preprocessor.html where you get an Internal Server Error message. The other links seem okay, it's only the Introduction link that's broken. -- Noel

4 5

[Graph] redefinition of hash<void*> clashes with boost/functional/hash.hpp
by Ioannis Papadopoulos 27 Oct '11

27 Oct '11

Hi, In graph/detail/adjacency_list.hpp:2766 there is a specialization of struct hash for void*. Isn't the generic pointer specialization in functional/hash/extensions.hpp:172 enough? The problem I am facing is the following (which I couldn't reproduce in a trivial example): 1. I include <boost/functional/hash.hpp> and <boost/tr1/unordered_map.hpp> 2. I create an std::tr1::unordered_map<void*, int> and typedef std::tr1::unordered_map<void*, int>::iterator iterator_type; 3. In some test file that includes <boost/graph/adjacency_list.hpp> and uses it, I get the following error (gcc 4.4.5/4.6.1): /usr/local/include/boost/graph/detail/adjacency_list.hpp:2766: error: specialization of ‘boost::hash<void*>’ after instantiation /usr/local/include/boost/graph/detail/adjacency_list.hpp:2766: error: redefinition of ‘struct boost::hash<void*>’ /usr/local/usr/include/boost/functional/hash/extensions.hpp:172: error: previous definition of ‘struct boost::hash<void*>’ I can resolve it by providing my own hash functor to the unordered_map (which causes hash<void*> not to be instantiated). I will keep trying to provide a trivial example. Thanks

2 2

[graph] Graph type needed in Graph Proptery, cyclic definition problem
by Christoph 26 Oct '11

26 Oct '11

Hi List, id like to use a std::priority_queue as a property of my graph. In the priority queue i store some vertices by the vertex degree. I have to Problems i think: First i have to define the priority_queue in a struct graph_properties. Within this priority_queue definition i use a comparison object as the 3rd template parameter. Now the problem is, that the class vertex_degree_compare needs to know the graph type, because of the use of out_degree(u, g) but the graph type depends on the graph_struct and this depends on the priority_queue definition. For the edge descriptors and vertex descriptors i used the traits_class http://www.boost.org/doc/libs/1_47_0/libs/graph/doc/adjacency_list_traits.h… but for the graph itself i don't know how to proceed. Any help is highly appreciated. // begin code #include <iostream> #include <queue> #include <boost/graph/adjacency_list.hpp> #include <boost/graph/graph_utility.hpp> typedef boost::adjacency_list_traits<boost::listS, boost::vecS, boost::bidirectionalS> link_adjacency_list_traits; struct vertex_properties { vertex_properties () : color (-1) {} unsigned int vertex_index; unsigned int vertex_index_t; int color; std::list <int> free_colors; std::map <int, link_adjacency_list_traits::edge_descriptor > used_colors; }; struct edge_properties { edge_properties () : color (-1) {} int color; }; struct graph_properties { int delta; std::priority_queue < link_adjacency_list_traits::vertex_descriptor, vertex_degree_compare> A; std::priority_queue < link_adjacency_list_traits::vertex_descriptor, vertex_degree_compare> B; }; typedef boost::adjacency_list < boost::listS, boost::listS, boost::bidirectionalS, vertex_properties, edge_properties, graph_properties> link_graph; typedef boost::graph_traits <link_graph> lgt; class vertex_degree_compare { private: link_graph g; public: vertex_degree_compare (const link_graph &g) : g(g) {} bool operator() (link_adjacency_list_traits::vertex_descriptor& u, link_adjacency_list_traits::vertex_descriptor& v) const { return out_degree (u, g) < out_degree (v, g); } }; int main(int argc, char** argv) { return 0; } // end code best regards Christoph

2 6

Accessing the edge through edge descriptor with bundled properties
by giridhar 26 Oct '11

26 Oct '11

Hello All, I have to access an edge in a vector called border_edge through an edge descriptor. For example for( vector<Edge>::iterator j=border_edge.begin();j!=border_edge.end();++j) { Edge e = t1[*j]; // I am getting error saying that No suitable conversion for Edge to Edgep exits } *Details*: border_edge is of type std::vector<Edge> border_edge(10); Graph as: typedef subgraph< adjacency_list<vecS, vecS, undirectedS, Vertexp, property< edge_index_t, unsigned int, Edgep > > > Graph; typedef Graph::edge_descriptor Edge; I have exterior Edge property defined as struct Edgep { int edge_index; int edge_w; std::string edge_name; int capacity; int residual_capcity; int bandwidth_used; }; Whenever I am adding edges into graph I am updating this border_edge vector. Say I am adding an edge from vertex 0 to 4 then I am doing this border_edge[i] = (add_edge(0,4,t)).first; //i is an example index. It is actually running in the loop. Can anyone please give some suggestions regarding this. How to access this edge which is inside vector? or what descriptor type should I use? -- Regards, Giridhar

3 4

[graph] VertexList type boost::vecS and boost::listS
by Christoph 26 Oct '11

26 Oct '11

Hi, I have some Questions concerning the Boost Graph Library graph template selector VertexList type. In the docs at http://www.boost.org/doc/libs/1_47_0/libs/graph/doc/using_adjacency_list.ht… I just found the two types documented. 1. How do i use the printed_graph (...) with a graph type that uses boost::listS instead of boost::vecS? I read that by using boost::vecS there is automatically an internal property for each Vertex created, which is the index of the vertex. I assume this is the reason why 'add_edge (1,2,g);' and 'print_graph (g,get(boost::vertex_index, g));' work for a graph g with a boost::vecS VertexList. However i cannot simply do 'add_edge (1,2,g);' or 'print_graph (g,get(boost::vertex_index, g));' vor a graph g with a VertexList type listS. How do i specify a vertex_index property for VertexList listS graph type, so that i can somehow use print_graph (g,something);? How are vertices internally identified when using listS? Are there any documentations about the function 'vertex()'? I think it is missing in Table 1: Summary of boost graph concepts in http://www.boost.org/doc/libs/1_47_0/libs/graph/doc/graph_concepts.html Look at the difference in using add_edge for the two different graph types and what happens if i try to insert an edge with one vertex not yet being part of the vertex set. Here is an example: //begin code #include <iostream> #include <boost/graph/adjacency_list.hpp> #include <boost/graph/graph_utility.hpp> typedef boost::adjacency_list < boost::listS, boost::vecS, boost::bidirectionalS> link_graph_vertex_vec; typedef boost::adjacency_list < boost::listS, boost::listS, boost::bidirectionalS> link_graph_vertex_list; int main(int argc, char** argv) { link_graph_vertex_vec g1(3); std::cout << "Number of vertices in g1: " << num_vertices (g1) << std::endl; add_edge (0,1,g1); std::cout << "Number of vertices in g1: " << num_vertices (g1) << std::endl; add_edge (1,2,g1); std::cout << "Number of vertices in g1: " << num_vertices (g1) << std::endl; add_edge (2,10,g1); std::cout << "Number of vertices in g1: " << num_vertices (g1) << std::endl; print_graph (g1, get(boost::vertex_index, g1)); link_graph_vertex_list g2(3); std::cout << "Number of vertices in g2: " << num_vertices (g2) << std::endl; add_edge (vertex(0,g2), vertex(1,g2), g2);//add_edge (0,1,g2); std::cout << "Number of vertices in g2: " << num_vertices (g2) << std::endl; add_edge (vertex(1,g2), vertex(2,g2), g2);//add_edge (1,2,g2); std::cout << "Number of vertices in g2: " << num_vertices (g2) << std::endl; //add_edge (vertex(2,g2), vertex(3,g2), g2);//add_edge (2,3,g2); //vertex(3,g2) // what is the return type, why does the program exit? std::cout << "Number of vertices in g2: " << num_vertices (g2) << std::endl; return 0; } //end code I have to decide whether to use boost::listS or boost::vecS for the VertexList type. The 'interface' of the vecS type graph operations are much easier for me to understand and to use. But on the other hand the listS type has the faster remove and insert operations. best regards Christoph

1 1