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

[BGL] Shared nodes on path
by Sensei 03 Mar '14

03 Mar '14

Dear all, I have a simple question about the most efficient way of finding shared nodes between a path and a graph. Let me be more explicit. I have an oriented graph G, and a very simple graph P, which is actually a simple oriented path (n0 -> n1 -> ... -> nK). I need to find *all* the possible shared paths between P and G with the same length as P. For instance, being P = n1 -> n2 -> n3 -> n4 -> n5 -> n6 we may find that the G and P share only two sub-paths n1 -> n2 -> n3 n5 -> n6 I'd like to find all sub-graphs that connect the two paths, for instance having n1 -> n2 -> n3 -> n10 -> n5 -> n6 n1 -> n2 -> n3 -> n42 -> n5 -> n6 with the constraint that the solution must be a path with the same length as P, therefore a solution as these n1 -> n2 -> n3 -> n9 -> n8 -> n5 -> n6 n1 -> n2 -> n3 -> n5 -> n6 would not be acceptable. I know I can do it manually, but I think a BGL-aware solution is quite better that a manual search :) Thanks & Cheers!

2 4

Error compiling Boost::graph crs_graph
by Andrea Cassioli 28 Feb '14

28 Feb '14

Dear all, I have been using the compressed_sparse_row_graph quite extensively in past. Now, I am working under Linux with Boost 1.55 and I am lost trying to compile the following toy piece of code: #include <vector> #include <boost/graph/compressed_sparse_row_graph.hpp> int main() { typedef boost::compressed_sparse_row_graph<boost::directedS, boost::no_property, int> gtype; std::vector<boost::graph_traits<gtype>::edge_descriptor> edges; std::vector< int > distances; gtype graph(boost::edges_are_unsorted_t(), edges.begin(), edges.end(), distances.begin(), edges.size()); return 0; } Just compile with g++ 4.8.2 and you get In file included from /usr/include/boost/graph/detail/compressed_sparse_row_struct.hpp:33:0, from /usr/include/boost/graph/compressed_sparse_row_graph.hpp:29, from prova_icl.cpp:2: /usr/include/boost/graph/detail/histogram_sort.hpp: In instantiation of ��void boost::graph::detail::split_into_separate_coords(InputIterator, InputIterator, std::vector<Property>&, std::vector<Property>&) [with InputIterator = __gnu_cxx::__normal_iterator<boost::detail::csr_edge_descriptor<long unsigned int, long unsigned int>*, std::vector<boost::detail::csr_edge_descriptor<long unsigned int, long unsigned int> > >; VerticesSize = long unsigned int]��: /usr/include/boost/graph/compressed_sparse_row_graph.hpp:466:46: required from ��boost::compressed_sparse_row_graph<boost::directedS, VertexProperty, EdgeProperty, GraphProperty, Vertex, EdgeIndex>::compressed_sparse_row_graph(boost::edges_are_unsorted_t, InputIterator, InputIterator, EdgePropertyIterator, boost::compressed_sparse_row_graph<boost::directedS, VertexProperty, EdgeProperty, GraphProperty, Vertex, EdgeIndex>::vertices_size_type, const GraphProperty&) [with InputIterator = __gnu_cxx::__normal_iterator<boost::detail::csr_edge_descriptor<long unsigned int, long unsigned int>*, std::vector<boost::detail::csr_edge_descriptor<long unsigned int, long unsigned int> > >; EdgePropertyIterator = __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >; VertexProperty = boost::no_property; EdgeProperty = int; GraphProperty = boost::no_property; Vertex = long unsigned int; EdgeIndex = long unsigned int; boost::compressed_sparse_row_graph<boost::directedS, VertexProperty, EdgeProperty, GraphProperty, Vertex, EdgeIndex>::vertices_size_type = long unsigned int]�� prova_icl.cpp:14:34: required from here /usr/include/boost/graph/detail/histogram_sort.hpp:226:51: error: conversion from ��boost::detail::csr_edge_descriptor<long unsigned int, long unsigned int>�� to non-scalar type ��std::pair<long unsigned int, long unsigned int>�� requested std::pair<VerticesSize, VerticesSize> edge = *begin; What the xxx is happening? In my understanding sounds like there conversion from an edge_descriptor to a pair....Any ideas?? Best, Andrea Cassioli

1 0

boost::optional with BOOST_FUSION_ADAPT_ADT broken?
by Andrew 28 Feb '14

28 Feb '14

There's an issue using get expressions returning optionals with BOOST_FUSION_ADAPT_ADT, demonstrated in the simplest case below. Optional<T> is trying initialize its internal T object using the attribute proxy object returned by fusion, but this can only degrade to optional<T> and not T, so the assignment fails. C++ wizard, K-Ballo, took a quick look at this in #boost and seemed to suggest it's the way op= is SFINAEd up for optional. Does anyone have a work around for this? #include <boost/optional.hpp> #include <boost/fusion/adapted/struct/adapt_struct.hpp> #include <boost/fusion/adapted/adt/adapt_adt.hpp> #include <boost/fusion/algorithm/auxiliary/copy.hpp> struct A { boost::optional<int> x; }; struct B { boost::optional<int> y; }; BOOST_FUSION_ADAPT_STRUCT(B, (boost::optional<int>, y)) BOOST_FUSION_ADAPT_ADT(A, (boost::optional<int>, boost::optional<int>, obj.x, obj.x = val)) int main() { A a; B b; // doesn't work: boost::fusion::copy (a, b); // this works: // boost::fusion::copy (b, a); }

3 4

boost graph, Using Bundled Properties and Internal Properties at the same time
by Paolo Bolzoni 27 Feb '14

27 Feb '14

Dear list, Related to the other email of me I woud like to use the subgraphs class, but the base graph needs two internal properties: vertex_index and edge_index. However in my program I use bundled properties as suggested in this list some time ago. Now I have this problem, is possible to use internal and bundled properties in the same graph? Or can I use subgraph in another way? Your faithfully, Paolo

1 0

Strange problem with boost/graph/subgraph.hpp
by Paolo Bolzoni 27 Feb '14

27 Feb '14

Dear list, I cannot compile a simple example using the subgraph implementation. I enclosed the code in the bottom of this email. It is quite short, but it is the whole code. It does not compile with errors from inside boost/graph/detail/adjacency_list.hpp about the impossiblity of making a reference to void. I read the subgraph documentation but I cannot understand why it does not work. Can anyone enlighten me? Your faithfully, Paolo The code: ------------------ >8 #include <boost/graph/adjacency_list.hpp> #include <boost/graph/subgraph.hpp> typedef boost::adjacency_list < boost::listS, boost::listS, boost::undirectedS > main_graph; typedef boost::subgraph <main_graph> sub_graph; typedef boost::graph_traits<sub_graph>::vertex_descriptor Bvertex; 8< ------------------

1 1

[ASIO] Streambuf not containing full line
by Gonzalo Garramuno 27 Feb '14

27 Feb '14

I am using asio asynchronically. I have: void tcp_session::start_read() { // Set a deadline for the read operation. // input_deadline_.expires_from_now(boost::posix_time::seconds(30)); // input_deadline_.expires_at(boost::posix_time::pos_infin); // Start an asynchronous operation to read a newline-delimited message. boost::asio::async_read_until(socket(), input_buffer_, '\n', boost::bind(&tcp_session::handle_read, shared_from_this(), boost::asio::placeholders::error)); } void tcp_session::handle_read(const boost::system::error_code& ec) { if (stopped()) return; if (!ec) { // Extract the newline-delimited message from the buffer. std::string msg; std::istream is(&input_buffer_); is.exceptions( std::ifstream::failbit | std::ifstream::badbit | std::ifstream::eofbit ); try { while ( std::getline(is, msg) ) { // parse msg here (gets truncated to last 256 chars or so) std::cerr << msg << std::endl; } } catch ( const std::ios_base::failure& e ) { std::cerr << "getline failure " << e.what() << std::endl; } } My problem is that I am seeing messages that are not a full line, but a truncation of the line, as if a buffer gets full with 256 characters. I am unsure what I am doing wrong. I get a getline failure saying basic_ios::clear.

2 1

[fusion] nth runtime element of a sequence
by MM 26 Feb '14

26 Feb '14

Hello, I just wanted to confirm there's no provided method to get the n'th element of say a fusion vector where n is known at runtime, except of handling it explicitkly with a switch case? Thanks MM

4 9

Project link error with Wave on OSX
by Olivier Prat 26 Feb '14

26 Feb '14

I've just updated a project that was working under XCode 4 with boost 1.48 to XCode 5 and boost 1.55 (installed with MacPorts). Now I have a link error with Wave which wasn't the case before. This somehow baffles me as I thought everything was template based. I am also linking with libboost-wave.mt.a but that doesn't solve the problem. The linker errors are, among 6 others: Undefined symbols for architecture x86_64: "boost::wave::cpplexer::new_lexer_gen<__gnu_cxx::__normal_iterator<char*, std::string>, boost::wave::util::file_position<boost::wave::util::flex_string<char, std::char_traits<char>, std::allocator<char>, boost::wave::util::CowString<boost::wave::util::AllocatorStringStorage<char, std::allocator<char> >, char*> > >, boost::wave::cpplexer::lex_token<boost::wave::util::file_position< boost::wave::util::flex_string<char, std::char_traits<char>, std::allocator<char>, boost::wave::util::CowString<boost::wave::util::AllocatorStringStorage<char, std::allocator<char> >, char*> > > > >::new_lexer(__gnu_cxx::__normal_iterator<char*, std::string> const&, __gnu_cxx::__normal_iterator<char*, std::string> const&, boost::wave::util::file_position<boost::wave::util::flex_string<char, std::char_traits<char>, std::allocator<char>, boost::wave::util::CowString<boost::wave::util::AllocatorStringStorage<char, std::allocator<char> >, char*> > > const&, boost::wave::language_support)", referenced from: I've tried forcing std::string as the BOOST_WAVE_STRINGTYPE, but that just changes the signatures of the undefined symbols. I fail to see what has changed and I am completely stuck. I would have understood if I had a compiler error but this is a link error. Is this something to do with the standard C++ library? For my project, C++ dialect is C++98 and the standard library is libstdc++. Thanks in advance, Olivier

2 4

Question on writing HTTP parser
by gomti 25 Feb '14

25 Feb '14

Hello. I'm newbie for boost library. I'm trying to write a HTTP Parser, which handles the HTTP message coming from the proxy server. I don't know much about the boost, so I'm really confused on what to use to write my functionality. When I search on the internet, some say that I need to used Boost.Asio and Some say Boost.Spirit. When I looked over the document for each, I found that Boost.Asio is like network library for C++ and Boost.Spirit is for writing compilers. As I mention above, I want to write a http parser. I think the relevant one is the following: https://github.com/joyent/http-parser Please give me some advice. Since this is my first posting, I don't know the culture in this mailing list so if I'm doing some mistake in here, please let me know. Thanks.

3 3

Parallel Dijkstra with Predecessors
by Florian Meier 25 Feb '14

25 Feb '14

Hi, I am trying to use the parallel Dijkstra implementation with predecessors, but I am not able to compile it. Please have a look at the following diff against boost_1_53_0/libs/graph_parallel/example/dijkstra_shortest_paths.cpp (You can find the modified version attached.) ------------------------------------------- @@ -45,8 +45,10 @@ /* An undirected, weighted graph with distance values stored on the vertices. */ +typedef adjacency_list_traits<vecS, distributedS<mpi_process_group, vecS>, undirectedS>::vertex_descriptor vertex_descriptor; + typedef adjacency_list<vecS, distributedS<mpi_process_group, vecS>, undirectedS, - /*Vertex properties=*/property<vertex_distance_t, float>, + /*Vertex properties=*/property<vertex_distance_t, float, property<vertex_predecessor_t, vertex_descriptor> >, /*Edge properties=*/property<edge_weight_t, float> > Graph; @@ -71,7 +73,7 @@ // Compute shortest paths from vertex 0 dijkstra_shortest_paths(g, start, - distance_map(get(vertex_distance, g))); + distance_map(get(vertex_distance, g)).predecessor_map(get(vertex_predecessor, g))); // Output a Graphviz DOT file std::string outfile = filename; ------------------------------------------- This (actually get(vertex_predecessor, g)) gives me ------------------------------------------- In file included from /usr/include/boost/property_map/parallel/distributed_property_map.hpp:706:0, from /usr/include/boost/property_map/property_map.hpp:645, from /usr/include/boost/graph/properties.hpp:19, from /usr/include/boost/mpi/graph_communicator.hpp:30, from /usr/include/boost/mpi.hpp:27, from /usr/include/boost/graph/distributed/mpi_process_group.hpp:30, from dijkstra_shortest_paths.cpp:16: /usr/include/boost/property_map/parallel/impl/distributed_property_map.ipp: In instantiation of ‘void boost::parallel::distributed_property_map<ProcessGroup, GlobalMap, StorageMap>::handle_message<Reduce>::handle_multiput(int, int, const std::vector<boost::unsafe_pair<typename boost::property_traits<StorageMap>::key_type, typename boost::property_traits<StorageMap>::value_type> >&, boost::graph::parallel::trigger_receive_context) [with Reduce = boost::property_reduce<boost::vertex_predecessor_t>::apply<boost::detail::parallel::global_descriptor<long unsigned int> >; ProcessGroup = boost::graph::distributed::mpi_process_group; GlobalMap = boost::detail::parallel::global_descriptor_property_map<long unsigned int>; StorageMap = boost::vec_adj_list_vertex_property_map<boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, boost::property<boost::vertex_distance_t, float, boost::property<boost::vertex_predecessor_t, boost::detail::parallel::global_descriptor<long unsigned int> > >, boost::property<boost::edge_locally_owned_t, bool, boost::property<boost::edge_target_processor_id_t, short int, boost::property<boost::edge_weight_t, float> > >, boost::no_property, boost::listS>, boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, boost::property<boost::vertex_distance_t, float, boost::property<boost::vertex_predecessor_t, boost::detail::parallel::global_descriptor<long unsigned int> > >, boost::property<boost::edge_locally_owned_t, bool, boost::property<boost::edge_target_processor_id_t, short int, boost::property<boost::edge_weight_t, float> > >, boost::no_property, boost::listS>*, boost::detail::parallel::global_descriptor<long unsigned int>, boost::detail::parallel::global_descriptor<long unsigned int>&, boost::vertex_predecessor_t>; typename boost::property_traits<StorageMap>::value_type = boost::detail::parallel::global_descriptor<long unsigned int>; typename boost::property_traits<StorageMap>::key_type = long unsigned int]’: /usr/include/boost/property_map/parallel/impl/distributed_property_map.ipp:255:18: required from ‘void boost::parallel::distributed_property_map<ProcessGroup, GlobalMap, StorageMap>::handle_message<Reduce>::setup_triggers(boost::parallel::distributed_property_map<ProcessGroup, GlobalMap, StorageMap>::process_group_type&) [with Reduce = boost::property_reduce<boost::vertex_predecessor_t>::apply<boost::detail::parallel::global_descriptor<long unsigned int> >; ProcessGroup = boost::graph::distributed::mpi_process_group; GlobalMap = boost::detail::parallel::global_descriptor_property_map<long unsigned int>; StorageMap = boost::vec_adj_list_vertex_property_map<boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, boost::property<boost::vertex_distance_t, float, boost::property<boost::vertex_predecessor_t, boost::detail::parallel::global_descriptor<long unsigned int> > >, boost::property<boost::edge_locally_owned_t, bool, boost::property<boost::edge_target_processor_id_t, shor t int, boost::property<boost::edge_weight_t, float> > >, boost::no_property, boost::listS>, boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, boost::property<boost::vertex_distance_t, float, boost::property<boost::vertex_predecessor_t, boost::detail::parallel::global_descriptor<long unsigned int> > >, boost::property<boost::edge_locally_owned_t, bool, boost::property<boost::edge_target_processor_id_t, short int, boost::property<boost::edge_weight_t, float> > >, boost::no_property, boost::listS>*, boost::detail::parallel::global_descriptor<long unsigned int>, boost::detail::parallel::global_descriptor<long unsigned int>&, boost::vertex_predecessor_t>; boost::parallel::distributed_property_map<ProcessGroup, GlobalMap, StorageMap>::process_group_type = boost::graph::distributed::mpi_process_group]’ /usr/include/boost/property_map/parallel/impl/distributed_property_map.ipp:35:3: required from ‘boost::parallel::distributed_property_map<ProcessGroup, GlobalMap, StorageMap>::distributed_property_map(const ProcessGroup&, const GlobalMap&, const StorageMap&, const Reduce&) [with Reduce = boost::property_reduce<boost::vertex_predecessor_t>::apply<boost::detail::parallel::global_descriptor<long unsigned int> >; ProcessGroup = boost::graph::distributed::mpi_process_group; GlobalMap = boost::detail::parallel::global_descriptor_property_map<long unsigned int>; StorageMap = boost::vec_adj_list_vertex_property_map<boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, boost::property<boost::vertex_distance_t, float, boost::property<boost::vertex_predecessor_t, boost::detail::parallel::global_descriptor<long unsigned int> > >, boost::property<boost::edge_locally_owned_t, bool, boost::property<boost::edge_target_processor_id_t, short int, boost::property<boost::edge_weight_t, floa t> > >, boost::no_property, boost::listS>, boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, boost::property<boost::vertex_distance_t, float, boost::property<boost::vertex_predecessor_t, boost::detail::parallel::global_descriptor<long unsigned int> > >, boost::property<boost::edge_locally_owned_t, bool, boost::property<boost::edge_target_processor_id_t, short int, boost::property<boost::edge_weight_t, float> > >, boost::no_property, boost::listS>*, boost::detail::parallel::global_descriptor<long unsigned int>, boost::detail::parallel::global_descriptor<long unsigned int>&, boost::vertex_predecessor_t>]’ /usr/include/boost/graph/distributed/adjacency_list.hpp:3468:50: required from ‘typename boost::property_map<boost::adjacency_list<OutEdgeListS, boost::distributedS<ProcessGroup, InVertexListS, InDistribution>, DirectedS, VertexProperty, EdgeProperty, GraphProperty, EdgeListS>, Property>::type boost::get(Property, boost::adjacency_list<OutEdgeListS, boost::distributedS<ProcessGroup, InVertexListS, InDistribution>, DirectedS, VertexProperty, EdgeProperty, GraphProperty, EdgeListS>&) [with Property = boost::vertex_predecessor_t; OutEdgeListS = boost::vecS; ProcessGroup = boost::graph::distributed::mpi_process_group; InVertexListS = boost::vecS; InDistribution = boost::defaultS; DirectedS = boost::undirectedS; VertexProperty = boost::property<boost::vertex_distance_t, float, boost::property<boost::vertex_predecessor_t, boost::detail::parallel::global_descriptor<long unsigned int> > >; EdgeProperty = boost::property<boost::edge_weight_t, float>; GraphProperty = boost::no_property; EdgeL istS = boost::listS; typename boost::property_map<boost::adjacency_list<OutEdgeListS, boost::distributedS<ProcessGroup, InVertexListS, InDistribution>, DirectedS, VertexProperty, EdgeProperty, GraphProperty, EdgeListS>, Property>::type = boost::parallel::distributed_property_map<boost::graph::distributed::mpi_process_group, boost::detail::parallel::global_descriptor_property_map<long unsigned int>, boost::vec_adj_list_vertex_property_map<boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, boost::property<boost::vertex_distance_t, float, boost::property<boost::vertex_predecessor_t, boost::detail::parallel::global_descriptor<long unsigned int> > >, boost::property<boost::edge_locally_owned_t, bool, boost::property<boost::edge_target_processor_id_t, short int, boost::property<boost::edge_weight_t, float> > >, boost::no_property, boost::listS>, boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, boost::property<boost::vertex_distance_t, float, boost::property<b oost::vertex_predecessor_t, boost::detail::parallel::global_descriptor<long unsigned int> > >, boost::property<boost::edge_locally_owned_t, bool, boost::property<boost::edge_target_processor_id_t, short int, boost::property<boost::edge_weight_t, float> > >, boost::no_property, boost::listS>*, boost::detail::parallel::global_descriptor<long unsigned int>, boost::detail::parallel::global_descriptor<long unsigned int>&, boost::vertex_predecessor_t> >]’ dijkstra_shortest_paths.cpp:77:106: required from here /usr/include/boost/property_map/parallel/impl/distributed_property_map.ipp:236:47: error: no match for call to ‘(boost::property_reduce<boost::vertex_predecessor_t>::apply<boost::detail::parallel::global_descriptor<long unsigned int> >) (const long unsigned int&, boost::parallel::distributed_property_map<boost::graph::distributed::mpi_process_group, boost::detail::parallel::global_descriptor_property_map<long unsigned int>, boost::vec_adj_list_vertex_property_map<boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, boost::property<boost::vertex_distance_t, float, boost::property<boost::vertex_predecessor_t, boost::detail::parallel::global_descriptor<long unsigned int> > >, boost::property<boost::edge_locally_owned_t, bool, boost::property<boost::edge_target_processor_id_t, short int, boost::property<boost::edge_weight_t, float> > >, boost::no_property, boost::listS>, boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, boost::property<boost::vertex_distance_t , float, boost::property<boost::vertex_predecessor_t, boost::detail::parallel::global_descriptor<long unsigned int> > >, boost::property<boost::edge_locally_owned_t, bool, boost::property<boost::edge_target_processor_id_t, short int, boost::property<boost::edge_weight_t, float> > >, boost::no_property, boost::listS>*, boost::detail::parallel::global_descriptor<long unsigned int>, boost::detail::parallel::global_descriptor<long unsigned int>&, boost::vertex_predecessor_t> >::value_type&, const boost::detail::parallel::global_descriptor<long unsigned int>&)’ values[i].second)); ^ In file included from /usr/include/boost/graph/distributed/breadth_first_search.hpp:23:0, from /usr/include/boost/graph/breadth_first_search.hpp:404, from /usr/include/boost/graph/dijkstra_shortest_paths.hpp:21, from dijkstra_shortest_paths.cpp:19: /usr/include/boost/graph/parallel/properties.hpp:90:11: note: candidates are: class apply ^ /usr/include/boost/graph/parallel/properties.hpp:95:9: note: T boost::property_reduce<boost::vertex_predecessor_t>::apply<T>::operator()(T) const [with T = boost::detail::parallel::global_descriptor<long unsigned int>] T operator()(T key) const { return key; } ^ /usr/include/boost/graph/parallel/properties.hpp:95:9: note: candidate expects 1 argument, 3 provided /usr/include/boost/graph/parallel/properties.hpp:96:9: note: T boost::property_reduce<boost::vertex_predecessor_t>::apply<T>::operator()(T, T, T) const [with T = boost::detail::parallel::global_descriptor<long unsigned int>] T operator()(T key, T, T y) const { return y; } ^ /usr/include/boost/graph/parallel/properties.hpp:96:9: note: no known conversion for argument 1 from ‘const long unsigned int’ to ‘boost::detail::parallel::global_descriptor<long unsigned int>’ ------------------------------------------- What is wrong here? Greetings, Florian

2 1