February 2006 - Boost-users

[BGL] graph copy after Kruskal's algorithm?
by Alejandro Aragón 10 Mar '06

10 Mar '06

Hi all, After running Kruskal's algorithm I end up with the list of the edges that form the minimum cost. However, no new graph is created. I need the resulting graph for further computations. How do you create a graph from an existing one but only selecting the edges contained in the minimum spanning tree vector? I've seen that there are some functions to accomplish this but I couldn't find any example of how to do it: template <class EdgeIterator, class EdgePropertyIterator> adjacency_list(EdgeIterator first, EdgeIterator last, EdgePropertyIterator ep_iter, vertices_size_type n, vertices_size_type m = 0, const GraphProperty& p = GraphProperty()) The existing graph has properties in edges and vertices that I also need to keep. Can anyone help? Thank you all, A.Aragon

4 6

[graph] [python]
by David E. Konerding 09 Mar '06

09 Mar '06

Hi folks, The bgl-python documentation says that the _graph.Graph.add_vertex() function returns a Vertex object. From my testing, the Vertex object that gets returned doesn't actually seem to be a member of the graph. Is this intentional? I was hoping that the returned Vertex object was valid, since I need access to it immediately. Here's a test program. I woudl expect the values for v1 and v2 to be in the graph, but they are not: =================== import boost.graph as bgl graph = bgl.Graph() v1 = graph.add_vertex() print "new v1=", v1 v2 = graph.add_vertex() print "new v2=", v2 e = graph.add_edge(v1, v2) print "new edge=", e for vertex in graph.vertices: print "vertex: ", vertex for edge in graph.edges: print "edge: ", edge print "edge source:", graph.source(e) ========================= Here's what I see: new v1= <boost.graph._graph.Vertex object at 0x40168a04> new v2= <boost.graph._graph.Vertex object at 0x40168aac> new edge= <boost.graph._graph.Edge object at 0x40164dec> vertex: <boost.graph._graph.Vertex object at 0x40168ae4> vertex: <boost.graph._graph.Vertex object at 0x40168b54> edge: <boost.graph._graph.Edge object at 0x40164d6c> edge source: <boost.graph._graph.Vertex object at 0x40168ae4> As you can see, v1 and v2 return and have different addresses than the Vertex objects that are listed by the vertices iterator. My guess here is that the Vertex objects do point to the same underlying vertex in the C++ implementation of the graph.

4 4

multi_array - problems with resize
by Craig Glasgow 08 Mar '06

08 Mar '06

Hi, I'm trying to write serialization load and save methods for multi-array. For the load method I have a function with the prototype: template<class Archive, class T, std::size_t NumDims> inline void load(Archive& ar, boost::multi_array<T, NumDims>& arr, const unsigned int file_version) This function gets called when the array is serialized and should populate the multi-array arr. However this requires re-sizing arr which apparently can only be done using the extents construct e.g. arr.resize(boost::extents[3][4][2]), but I want to be able to do this for an arbitray number of dims as with reshape. Any idea how this can be done? Regards Craig

2 1

case insensitive less_than string comparison
by Matthias Kaeppler 07 Mar '06

07 Mar '06

Hi, I am aware that string_algo has an if_iequal functor. Is there also an equivalent for a less-than comparison? I have to compare strings ignoring the case but taking locales into account. Right now I'm calling boost::algorithm::to_lower on two copies of the original strings. I'm not so sure if this is very efficient when I'm comparing thousands of strings. Here's the functor as it is now: struct FileLessNameA : std::binary_function<const File&,const File&,bool> { bool operator() (const File& lhs, const File& rhs) const { std::string path1( lhs.get_name().c_str() ); std::string path2( rhs.get_name().c_str() ); boost::algorithm::to_lower( path1 ); boost::algorithm::to_lower( path2 ); return path1 < path2; } }; Any suggestions for improvements appreciated :) Regards, Matthias -- Matthias Kaeppler

7 17

Re: [Boost-users] Getting started with Boost: what did you need to know?
by Merrill Cornish 06 Mar '06

06 Mar '06

David, At the risk of annoying some Boost developers... My single biggest complaint is the Boost documentation-- not so much that the libraries are undocumented, but that it's so hard to find your way through the documentation that is provided. There is the documentation on the Boost site rooted under Libraries | Documentation. Then there is the documentation under doc/html in the Boost source tree. Then there is the documentation under libs/<libraryName>/doc in the source tree. Sometimes, they are the same, sometimes, the libs documentation has extra stuff. Why? A side effect of having HTML documentation is that there is no index--a valuable tool when you are trying find your way through new territory. The Boost documentation standard recommends having a table of contents-like list of topics on the first page of a library's documentation. Sounds good, but since there usually isn't any paragraphing levels shown, what you get is a list of topics, some of which repeat with no indication of which are subtopics of which. The naming of documentation files can be misleading also. The discussion of mutexes (with no specific mention of threads) is called "thread" while the discussion of threading (with no specific mention of mutexes) is call "threads" [note the plural]. Or, maybe it's the other way around. The available documentation takes a scatter gun approach at to the intended audience. Under mutexes (whatever its name), there is a treatise (as I remember) on all possible mutex alternatives. It's only later that the reader discovers none of them are actually implemented. Similarly, the serialization documentation has a long discussion on shared pointers in a file named shared_ptr.html. Another file named shared_ptr2.html starts out by saying that about the stuff you just read in shared_ptr.html "Unfortunately, this way of doing it suffered from some undesirable features." This is a lot like giving someone detailed driving directions only to say, "if you go this far, you've taken a wrong turn." The documentation is written so that in order to do almost anything, you have to read everything, including all of the "here are all the wrong turns I took in developing this library" pages. For example, the documentation for the serialization library seems straightforward, but you'll probably miss the special macro you are supposed to use if you are serializing an abstract class. The Boost documentation is serverly in the need of global editing. Merrill

4 4

[BGL] Why this is not compiled?
by Dmitry Bufistov 06 Mar '06

06 Mar '06

Hi all, I'm trying to compile the following code and have some compiler errors (MSVC 8). // TestBoostGraph1.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include <string> #include <boost/graph/adjacency_list.hpp> #include <boost/graph/adjacency_matrix.hpp> #include <boost/graph/graphviz.hpp> #include <boost/graph/iteration_macros.hpp> #include <boost/graph/graph_utility.hpp> #include <boost/graph/copy.hpp> ///Just for read "work around" ///Two typedefs for modeling both "discrete" & "continues" nets typedef int discret_net_t; typedef double continues_net_t; /// typedef enum {PLACE, TRANSITION} node_type_t; /*! * If you need some more properties, then you should define your property class that derived from * basic_vertex_properties<>; - for nodes, * basic_edge_properties<>; - for edges * Example: struct my_node_prop : basic_vertex_properties<discret_net_t> { typedef double node_delay_t; node_delay_t m_node_delay; }; typedef CPetriNet<adj_list, boost::vecS, boost::listS, boost::bidirectionalS, my_node_prop> petri_net_t * * The types of all property values must be Copy Constructible, Assignable and Default Constructible!! */ template <class T = discret_net_t> struct basic_vertex_properties { typedef std::string node_name_type; typedef int node_index_t; basic_vertex_properties(node_type_t nt = TRANSITION) : m_node_type(nt) { m_token_number = T(0);} T m_token_number; ///Only for place, possible costruct "continues" nets node_name_type m_node_name; node_type_t m_node_type; ///Vertex could be "Place" or "transition" node_index_t m_node_index;///Internal property for convenient vertices lookup }; ///Basic properties for edge template <class T = discret_net_t> struct basic_edge_properties { typedef int edge_index_t; basic_edge_properties(T ew = 0) : m_weight(ew) {} T m_weight; ///possible construct "continues" nets edge_index_t m_edge_index; ///Internal property for convenient vertices lookup; }; using boost::bidirectionalS; using boost::directedS; using boost::no_property; struct my_ver_p : public basic_vertex_properties<discret_net_t> { double m_node_delay; }; struct my_edge_p : public basic_edge_properties<discret_net_t> { double m_edge_delay; }; int _tmain(int argc, _TCHAR* argv[]) { typedef boost::adjacency_list<boost::listS, boost::listS, directedS, my_ver_p> adj_list1_t; adj_list1_t c(10); boost::property_map<adj_list1_t, my_ver_p::node_name_type my_ver_p::* >::type node_name_map1(boost::get(&my_ver_p::m_node_name, c)); boost::print_graph(c, node_name_map1) ; return 0; } 1>------ Build started: Project: TestBoostGraph1, Configuration: Debug Win32 ------ 1>Compiling... 1>TestBoostGraph1.cpp 1>d:\documents and settings\dmitry\my documents\visual studio 2005\projects\testboostgraph1\testboostgraph1\testboostgraph1.cpp(78) : error C2664: 'boost::bundle_property_map<Graph,Descriptor,Bundle,T>::bundle_property_map(const boost::bundle_property_map<Graph,Descriptor,Bundle,T> &)' : cannot convert parameter 1 from 'boost::bundle_property_map<Graph,Descriptor,Bundle,T>' to 'const boost::bundle_property_map<Graph,Descriptor,Bundle,T> &' 1> with 1> [ 1> Graph=adj_list1_t, 1> Descriptor=void *, 1> Bundle=my_ver_p, 1> T=basic_vertex_properties<discret_net_t>::node_name_type 1> ] 1> and 1> [ 1> Graph=boost::adjacency_list<boost::listS,boost::listS,boost::directedS,my_ver_p>, 1> Descriptor=boost::detail::edge_desc_impl<boost::directed_tag,void *>, 1> Bundle=basic_vertex_properties<discret_net_t>, 1> T=basic_vertex_properties<discret_net_t>::node_name_type 1> ] 1> and 1> [ 1> Graph=adj_list1_t, 1> Descriptor=void *, 1> Bundle=my_ver_p, 1> T=basic_vertex_properties<discret_net_t>::node_name_type 1> ] 1> Reason: cannot convert from 'boost::bundle_property_map<Graph,Descriptor,Bundle,T>' to 'const boost::bundle_property_map<Graph,Descriptor,Bundle,T>' 1> with 1> [ 1> Graph=boost::adjacency_list<boost::listS,boost::listS,boost::directedS,my_ver_p>, 1> Descriptor=boost::detail::edge_desc_impl<boost::directed_tag,void *>, 1> Bundle=basic_vertex_properties<discret_net_t>, 1> T=basic_vertex_properties<discret_net_t>::node_name_type 1> ] 1> and 1> [ 1> Graph=adj_list1_t, 1> Descriptor=void *, 1> Bundle=my_ver_p, 1> T=basic_vertex_properties<discret_net_t>::node_name_type 1> ] 1> No user-defined-conversion operator available that can perform this conversion, or the operator cannot be called 1>TestBoostGraph1 - 1 error(s), 0 warning(s) ========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped ========== if change graph representation to following typedef boost::adjacency_list<boost::listS, boost::listS, directedS, basic_vertex_properties<> > adj_list1_t; then this compiles without any error: adj_list1_t c(10); boost::property_map<adj_list1_t, basic_vertex_properties<>::node_name_type basic_vertex_properties<>::* >::type node_name_map1(boost::get(&basic_vertex_properties<>::m_node_name, c)); but with this I again have some error (just change "type" to "const_type" adj_list1_t c(10); boost::property_map<adj_list1_t, basic_vertex_properties<>::node_name_type basic_vertex_properties<>::* >::const_type node_name_map1(boost::get(&basic_vertex_properties<>::m_node_name, c)); 1>------ Build started: Project: TestBoostGraph1, Configuration: Debug Win32 ------ 1>Compiling... 1>TestBoostGraph1.cpp 1>d:\documents and settings\dmitry\my documents\visual studio 2005\projects\testboostgraph1\testboostgraph1\testboostgraph1.cpp(79) : error C2664: 'boost::bundle_property_map<Graph,Descriptor,Bundle,T>::bundle_property_map(const boost::bundle_property_map<Graph,Descriptor,Bundle,T> &)' : cannot convert parameter 1 from 'boost::bundle_property_map<Graph,Descriptor,Bundle,T>' to 'const boost::bundle_property_map<Graph,Descriptor,Bundle,T> &' 1> with 1> [ 1> Graph=const adj_list1_t, 1> Descriptor=void *, 1> Bundle=basic_vertex_properties<discret_net_t>, 1> T=const basic_vertex_properties<discret_net_t>::node_name_type 1> ] 1> and 1> [ 1> Graph=adj_list1_t, 1> Descriptor=void *, 1> Bundle=basic_vertex_properties<discret_net_t>, 1> T=basic_vertex_properties<discret_net_t>::node_name_type 1> ] 1> and 1> [ 1> Graph=const adj_list1_t, 1> Descriptor=void *, 1> Bundle=basic_vertex_properties<discret_net_t>, 1> T=const basic_vertex_properties<discret_net_t>::node_name_type 1> ] 1> Reason: cannot convert from 'boost::bundle_property_map<Graph,Descriptor,Bundle,T>' to 'const boost::bundle_property_map<Graph,Descriptor,Bundle,T>' 1> with 1> [ 1> Graph=adj_list1_t, 1> Descriptor=void *, 1> Bundle=basic_vertex_properties<discret_net_t>, 1> T=basic_vertex_properties<discret_net_t>::node_name_type 1> ] 1> and 1> [ 1> Graph=const adj_list1_t, 1> Descriptor=void *, 1> Bundle=basic_vertex_properties<discret_net_t>, 1> T=const basic_vertex_properties<discret_net_t>::node_name_type 1> ] 1> No user-defined-conversion operator available that can perform this conversion, or the operator cannot be called 1>TestBoostGraph1 - 1 error(s), 0 warning(s) ========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped ========== What is wrong here? Any help would be greatly appreciated, Thanks in advance, --dima // TestBoostGraph1.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include <string> #include <boost/graph/adjacency_list.hpp> #include <boost/graph/adjacency_matrix.hpp> #include <boost/graph/graphviz.hpp> #include <boost/graph/iteration_macros.hpp> #include <boost/graph/graph_utility.hpp> #include <boost/graph/copy.hpp> ///Just for read "work around" ///Two typedefs for modeling both "discrete" & "continues" nets typedef int discret_net_t; typedef double continues_net_t; /// typedef enum {PLACE, TRANSITION} node_type_t; /*! * If you need some more properties, then you should define your property class that derived from * basic_vertex_properties<>; - for nodes, * basic_edge_properties<>; - for edges * Example: struct my_node_prop : basic_vertex_properties<discret_net_t> { typedef double node_delay_t; node_delay_t m_node_delay; }; typedef CPetriNet<adj_list, boost::vecS, boost::listS, boost::bidirectionalS, my_node_prop> petri_net_t * * The types of all property values must be Copy Constructible, Assignable and Default Constructible!! */ template <class T = discret_net_t> struct basic_vertex_properties { //typedef node_type_t my_node_type; typedef std::string node_name_type; typedef int node_index_t; basic_vertex_properties(node_type_t nt = TRANSITION) : m_node_type(nt) { m_token_number = T(0);} T m_token_number; ///Only for place, possible costruct "continues" nets node_name_type m_node_name; node_type_t m_node_type; ///Vertex could be "Place" or "transition" node_index_t m_node_index;///Internal property for convenient vertices lookup }; ///Basic properties for edge template <class T = discret_net_t> struct basic_edge_properties { typedef int edge_index_t; basic_edge_properties(T ew = 0) : m_weight(ew) {} //private: T m_weight; ///possible construct "continues" nets edge_index_t m_edge_index; ///Internal property for convenient vertices lookup; }; using boost::bidirectionalS; using boost::directedS; using boost::no_property; struct my_ver_p : public basic_vertex_properties<discret_net_t> { double m_node_delay; }; struct my_edge_p : public basic_edge_properties<discret_net_t> { double m_edge_delay; }; int _tmain(int argc, _TCHAR* argv[]) { //typedef boost::adjacency_list<boost::listS, boost::listS, directedS, my_ver_p> adj_list1_t; typedef boost::adjacency_list<boost::listS, boost::listS, directedS, basic_vertex_properties<> > adj_list1_t; adj_list1_t c(10); boost::property_map<adj_list1_t, basic_vertex_properties<>::node_name_type basic_vertex_properties<>::* >::const_type node_name_map1(boost::get(&basic_vertex_properties<>::m_node_name, c)); boost::print_graph(c, node_name_map1) ; return 0; }

3 2

BGL connected_components for directed graphs
by Gavin Band 02 Mar '06

02 Mar '06

Dear boosters, I am trying to compile a program which is identical to the example http://www.boost.org/libs/graph/example/connected_components.cpp given in the docs, except that in the graph typedef I changed undirectedS to directedS. However, I get a compilation error: g++ -o test_c++.o -I/usr/include/boost -c test_c++.cpp /usr/include/boost/graph/connected_components.hpp: In function `typename boost::property_traits<IndexMap>::value_type boost::connected_components(const Graph&, ComponentMap) [with Graph = main(int, char**)::Graph, ComponentMap = int*]': test_c++.cpp:45: instantiated from here /usr/include/boost/graph/connected_components.hpp:87: error: incomplete type `boost::STATIC_ASSERTION_FAILURE< false>' used in nested name specifier /usr/include/boost/graph/connected_components.hpp:87: error: size of array has non-integral type `<type error>' Presumably this is some meta-program's way of telling me that my graph isn't undirected. Is there any way to make this work for an directed graph? (I am using gcc 3.4.4 and boost 1.33.0) Thanks, Gavin Band.

2 1

serialization: again a problem, failing to serialize a std::vector of pointers
by RIVASSEAU Jean Noel 02 Mar '06

02 Mar '06

Hello This is my last problem with the BSL but the most important one (because there is no workaround). I am trying to serialize a class (whose name is "ClassSpecification") which has a std::vector of pointers. The code for serializing the class the pointer refer to (MemberVariableSpecification) is written and instantiated correctly. However I cannot correctly serialize the std::vector. It fails with a message complaining about: C:/Boost/include/boost-1_33_1/boost/archive/detail/iserializer.hpp:115: error: incomplete type `boost::serialization::extended_type_info_null<std::vector<MemberVariableSpecification*, std::allocator<MemberVariableSpecification*> > >' used in nested name specifier I do not understand why I need an extended_type_info for this vector. I sure need it for the class the pointers refer to (and I did specify it), but the std::vector itself is serialized as such, not as a pointer. Why do I get this error ??? Can you please check the attached code and help me? Thanks Jean-Noël Ps: using gcc 3.4.2

2 2

newbie question
by Lucio Flores 02 Mar '06

02 Mar '06

Just trying to use mpl::transform on a vector of int's and I can't seem to get it working properly. Can anyone see what's wrong?? I'm trying to perform vector_c<int, 1, 2, 3> + vector_c<int, 1, 1, 1> = vector_c<int, 2, 3 ,4> The is_same function always returns false when I compile and run it. ------------------- typedef mpl::vector_c<int, 1, 2, 3> type_a; typedef mpl::vector_c<int, 1, 1, 1> type_b; struct plus_f { template<class A, class B> struct apply { typedef typename mpl::plus<A, B>::type type; }; }; typedef mpl::transform<type_a, type_b, plus_f >::type result_type; std::cerr << "True " << boost::is_same<result_type, mpl::vector_c<int, 2, 3, 4> >::value << std::endl; __________________________________________________ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com

13 55

[statechart] Template States, Compile Error
by David Greene 01 Mar '06

01 Mar '06

The attached testcase doesn't compile with g++ 4.0.2 or g++ 3.2.3. The compiler generates a series of error messages like this: boost/statechart/simple_state.hpp:189: error: no type named 'inner_context_type' in 'struct Test::NormalMode<int>' I hastily sketched this out based on a larger code. If there are typos or other mistakes, let me know but the main problem I'm trying to solve is the "no type named" problem. I typedef it right in the template definition for NormalMode! This is using the current CVS for statechart, 1.33.1 for mpl. Is it possibly a compiler bug? Thanks! -Dave ---------------- Testcase #include <boost/statechart/state_machine.hpp> #include <boost/statechart/simple_state.hpp> #include <boost/statechart/event.hpp> #include <boost/statechart/custom_reaction.hpp> #include <boost/statechart/state.hpp> #include <boost/statechart/transition.hpp> #include <boost/mpl/list.hpp> #include <iostream> // Switch finite state machine for multiplexor schedule policy namespace Test { namespace sc = boost::statechart; namespace mpl = boost::mpl; // Inner states template <typename Type> struct On; template <typename Type> struct Off; template <typename Type> struct Error; // Outer states template <typename Type> struct NormalMode; template <typename Type> struct ErrorMode; // Events struct End : public sc::event<End> {}; struct UnconsumedEvent : public sc::event<UnconsumedEvent> { std::string st; UnconsumedEvent(const std::string &s) : st(s) {}; const std::string &state(void) const { return(st); }; }; template<typename Derived, typename Type> struct SwitchEvent : public sc::event<Derived> { typedef Type value_type; value_type ev; SwitchEvent(value_type e) : ev(e) {}; value_type value(void) const { return(ev); } }; template<typename Type> struct TurnOn : public SwitchEvent<TurnOn<Type>, Type> { TurnOn(Type value) : SwitchEvent<TurnOn<Type>, Type>(value) {}; }; template<typename Type> struct TurnOff : public SwitchEvent<TurnOff<Type>, Type> { TurnOff(Type value) : SwitchEvent<TurnOff<Type>, Type>(value) {}; }; template<typename Type> struct Switch; namespace detail { template<typename Type> struct typedefs { typedef Type value_type; typedef Switch<value_type> switch_context; typedef TurnOn<value_type> turn_on; typedef TurnOff<value_type> turn_off; typedef On<value_type> on; typedef Off<value_type> off; }; }; // The state machine template<typename Type> struct Switch : public sc::state_machine<Switch<Type>, NormalMode<Type> >, public detail::typedefs<Type> { typedef sc::state_machine<Switch<Type>, NormalMode<Type> > Base; typedef Switch<Type> This; std::string state(void) const { if (this->template state_cast<const typename This::on *>()) { return("ON"); } else if (this->template state_cast<const typename This::off *>()) { return("OFF"); } else { std::cerr << "Unknown state" << std::endl; std::abort(); return("ERROR"); } }; // Abort on unexpected events void unconsumed_event(const sc::event_base &event) { std::cerr << "Unexpected event in state " << state() << std::endl; std::abort(); this->post_event(new UnconsumedEvent(state())); }; }; // Define states // Outer template<typename Type> struct NormalMode : public sc::simple_state<NormalMode<Type>, Switch<Type>, Off<Type> >, public detail::typedefs<Type> { typedef sc::simple_state<NormalMode<Type>, Switch<Type>, Off<Type> > state_base; typedef typename state_base::inner_context_type inner_context_type; }; template<typename Type> struct ErrorMode : public sc::simple_state<ErrorMode<Type>, Switch<Type>, Error<Type> >, public detail::typedefs<Type> { typedef sc::simple_state<ErrorMode<Type>, Switch<Type>, Error<Type> > state_base; typedef typename state_base::inner_context_type inner_context_type; }; // Inner template<typename Type> struct Off : public sc::simple_state<Off<Type>, NormalMode<Type> >, public detail::typedefs<Type> { typedef Off<Type> This; typedef mpl::list< sc::custom_reaction<typename This::on>, sc::custom_reaction<End> > reactions; sc::result react(const typename This::on &) { this->template context<typename This::switch_context>().transit("OFF", "ON"); return(this->template transit<typename This::on>()); }; sc::result react(const End &) { this->terminate(); }; }; template<typename Type> struct On : public sc::simple_state<On<Type>, NormalMode<Type> >, public detail::typedefs<Type> { typedef On<Type> This; typedef mpl::list< sc::custom_reaction<typename This::off>, sc::custom_reaction<End> > reactions; sc::result react(const typename This::off &) { this->template context<typename This::switch_context>().transit("ON", "OFF"); return(this->template transit<typename This::off>()); }; sc::result react(const End &) { this->terminate(); }; }; template<typename Type> struct Error : sc::simple_state<Error<Type>, ErrorMode<Type> >, public detail::typedefs<Type> { }; }; int main(void) { Test::Switch<int> machine; machine.initiate(); machine.process_event( Test::TurnOn<int>(0) ); std::cout << "Now in state " << machine.state() << std::endl; machine.process_event( Test::TurnOff<int>(0) ); std::cout << "Now in state " << machine.state() << std::endl; machine.process_event( Test::TurnOff<int>(0) ); // Should produce error std::cout << "Now in state " << machine.state() << std::endl; machine.process_event( Test::End() ); }

3 8