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

[BGL] filtered_graph and null_vertex()
by Tiago de Paula Peixoto 06 Sep '05

06 Sep '05

Hello. Is the function graph_traits<G>::null_vertex() defined for G = filtered_graph? When I try to compile the following simple program: -------------------------------------------------------------- #include <boost/graph/adjacency_list.hpp> #include <boost/graph/filtered_graph.hpp> using namespace boost; int main() { typedef adjacency_list<vecS> graph_t; typedef filtered_graph<graph_t,keep_all> f_graph_t; graph_traits<f_graph_t>::vertex_descriptor v = graph_traits<f_graph_t>::null_vertex(); return 0; } -------------------------------------------------------------- I get the following error with GCC 4.0.1 and boost 1.33.0: /usr/include/boost/graph/graph_traits.hpp: In static member function ‘static typename boost::graph_traits<G>::vertex_descriptor boost::graph_traits<G>::null_vertex() [with G = main()::f_graph_t]’: filtered_test.cc:10: instantiated from here /usr/include/boost/graph/graph_traits.hpp:49: error: ‘null_vertex’ is not a member of ‘main()::f_graph_t’ Shouldn't null_vertex() just be defined to return the null_vertex() for the underlying graph, since the vertex descriptors are the same? Do I miss something? -- Tiago de Paula Peixoto <tiago(a)forked.de>

3 3

Multipartite or layered graph
by Nicola Vitacolonna 06 Sep '05

06 Sep '05

Hi, I need to implement a graph whose set of vertices is partitioned into a certain number of ordered subsets (called layers). Edges join vertices from a layer to the next one(s). A critical operation is the iteration over the nodes of a given layer. I think this can be implemented by adding a vertex property to each vertex, that specifies the layer each vertex belongs to. But this does not seem to me the most (time and space) efficient solution: in particular, how can I iterate over the nodes of a given layer without checking every node? I was wondering whether there is a better way to do the job: maybe, using a custom VertexList implemented using a vector for each layer (in this case, should I write my own functions to add/remove vertices? And should I write my own iterators?). Any other idea, or pointer to existing code (I am new to Boost)? Best regards Nicola Vitacolonna

2 1

[serialization, 1_33_0] Correct usage and implementation for serializable objects without default constructors.
by Martin Proulx 06 Sep '05

06 Sep '05

Hello, While using the latest release of boost, I've encountered a few questions concerning the usage of the serialization library with objects without default constructors. Here they are: 1-) How can we construct an instance of a serialized object that doesn't have a default constructor? The only option I've figured out is to normally construct an object with bogus values, then unserialize the real values while reading from the archive. Example: X(0) val; // 0 being some bogus value. inputStream >> val; // Overwrites all values within val; Is this the correct way to do things? 2-) How should we split the serialization between the class' serialize member versus load/save_construct_data? My observations show that when un/serializing objects directly like shown above, load/save_construct_data aren't needed, so the serialize member has to handle everything. When serializing a vector<X>, load/save_construct_data does get called, so we have to un/serialize some members in those functions as well. At first glance, it seems some members will have to be un/serialized for the second time within load/save_construct_data. Is that correct? For a class to be correctly un/serializable for all cases, load/save_construct_data must un/serialize members that are already taken care of in the serialize member? Thanks! Martin -- Tel: (450) 681-1681, #271 ------------------------------------------------------------------------ OKIOK Enterprise and e-business security solutions Solutions de sécurité d'entreprise et d'affaires électronique Tel. : (450) 681.1681 http://www.okiok.com This e-mail message (including attachments, if any) is intended for the use of the individual or entity to which it is addressed and may contain information that is privileged, proprietary, confidential and exempt from disclosure. If you are not the intended recipient, you are notified that any dissemination, distribution or copying of this communication is strictly prohibited. If you have received this communication in error, please notify the sender and erase this e-mail message immediately. Le présent message électronique (y compris les pièces qui y sont annexées, le cas échéant) s'adresse au destinataire indiqué et peut contenir des renseignements de caractère privé ou confidentiel. Si vous n'êtes pas le destinataire de ce document, nous vous signalons qu'il est strictement interdit de le diffuser, de le distribuer ou de le reproduire. Si ce message vous a été transmis par erreur, veuillez en informer l'expéditeur et le supprimer immédiatement.

2 1

[BGL] using biconnected_components with an exterior property map
by Greg Landrum 06 Sep '05

06 Sep '05

Hi, I'm trying to use the biconnected_components algorithm from v1.33 of the BGL in some code and I've encountered a problem that I just can't seem to get past. The algorithm requires a property map argument that's used to output which component each edge maps to; this is the argument that's giving me fits. I started with a simple-ish case derived from an example in the BGL docs: //------------------------------------------------------------------ namespace boost { struct edge_component_t { enum { num = 555 }; typedef edge_property_tag kind; } edge_component; typedef property< edge_component_t, std::size_t > edge_prop_t; } int main() { using namespace boost; typedef adjacency_list < vecS, vecS, undirectedS, no_property, edge_prop_t >graph_t; typedef graph_traits < graph_t >::vertex_descriptor vertex_t; graph_t g(5); add_edge(0, 1, edge_prop_t(3), g); add_edge(1, 2, edge_prop_t(3), g); add_edge(0, 2, edge_prop_t(3), g); add_edge(2, 3, edge_prop_t(1), g); add_edge(3, 5, edge_prop_t(1), g); typedef property_map < graph_t, edge_component_t >::type edge_map_t; edge_map_t edge_map = get(edge_component, g); graph_traits<graph_t>::edge_iterator edge,endEdges; for(tie(edge,endEdges)=boost::edges(g); edge!=endEdges;++edge){ std::cout << " >Edge1: " << source(*edge,g) << "-" << target(*edge,g) << " <- " << edge_map[*edge] << std::endl; } edge_map_t components = get(edge_component, g); std::size_t num_comps = biconnected_components(g, components); for(tie(edge,endEdges)=boost::edges(g); edge!=endEdges;++edge){ std::cout << " >Edge2: " << source(*edge,g) << "-" << target(*edge,g) << " <- " << edge_map[*edge] << std::endl; } return 0; } //------------------------------------------------------------------ When I run this, I get reasonable results for the connected components, but here's what prints: >Edge1: 0-1 <- 3 >Edge1: 1-2 <- 3 >Edge1: 0-2 <- 3 >Edge1: 2-3 <- 1 >Edge1: 3-5 <- 1 >Edge2: 0-1 <- 2 >Edge2: 1-2 <- 2 >Edge2: 0-2 <- 2 >Edge2: 2-3 <- 1 >Edge2: 3-5 <- 0 Note that the graph's property map values for the edges have changed (Edge2 values vs Edge1 values). So calling biconnected_components() has modified the graph, even though the graph argument is const. This made me sad, but I figured that I should be able to work around it using an exterior property map. According to the docs: "The ComponentMap type must be a model of Writable Property Map. The value type shouch be an integer type, preferably the same as the edges_size_type of the graph. The key type must be the graph's edge descriptor type." So as my next experiment, I decided to attempt to use an associative property map matching these requirements. I tried to define components like this: //------------ typedef std::map< graph_traits<graph_t>::edge_descriptor, int > map_t; map_t base_map; associative_property_map< map_t > components(base_map); //------------ That doesn't compile, the definition of base_map generates an error whose explanation begins with: //---------------- C:\Program Files\Microsoft Visual Studio .NET 2003\Vc7\include\functional(139) : error C2784: 'bool std::operator <(const std::stack<_Ty,_Container> &,const std::stack<_Ty,_Container> &)' : could not deduce template argument for 'const std::stack<_Ty,_Container> &' from 'const boost::graph_traits<G>::edge_descriptor' with [ G=graph_t ] //---------------- My apologies for the horrible interaction between this message and gmail's line wrapping. If it's useful, I can send the entire error message as an attachment. I next tried to create some other kind of exterior property map, but the documentation for how to do this seems to be out of date. There's an explanation of this in the boost wiki at URL: http://www.crystalclearsoftware.com/cgi-bin/boost_wiki/wiki.pl?Documentatio… search for "random_access_iterator_property_map" So my question is: how can I make a call to biconnected_components in a manner that doesn't modify my graph (or any of its associated property maps)? In the event that it matters, I'm building these tests under win2k using visual c++ 7.1 and boost v1.33. -greg

4 7

[graph] cuthill-mckee ordering broken?
by Marco Morandini 06 Sep '05

06 Sep '05

After building the example file cuthill_mckee_ordering.cpp I get ------------------------------ 8 3 0 9 2 5 1 4 7 6 bandwidth: 4 Reverse Cuthill-McKee ordering starting at: 0 9 1 4 6 7 2 8 5 3 0 bandwidth: 4 Reverse Cuthill-McKee ordering: 9 1 4 6 7 2 8 5 3 0 bandwidth: 4 ------------------------------- instead of the expected ------------------------------- Reverse Cuthill-McKee ordering starting at: 6 8 3 0 9 2 5 1 4 7 6 bandwidth: 4 Reverse Cuthill-McKee ordering starting at: 0 9 1 4 6 7 2 8 5 3 0 bandwidth: 4 Reverse Cuthill-McKee ordering: 0 8 5 7 3 6 4 2 1 9 bandwidth: 4 ------------------------------- (the last ordering is different. Even worst, if I comment out the first two code blocks that wraps the call to cuthill_mckee_ordering, and leave only the third, I get ------------------------------- Reverse Cuthill-McKee ordering: 0 0 0 0 0 0 0 0 0 0 bandwidth: 9 Is this correct? Thanks in advance, Marco Morandini boost version: 1.33.0 compiler: marco@mbdyn-mm:~> gcc -v Reading specs from /home/marco/local/gcc-3.4.4/lib/gcc/i686-pc-linux-gnu/3.4.4/specs Configured with: ../configure --enable-languages=c,c++,f77 --prefix=/home/marco/local/gcc-3.4.4 --enable-__cxa_atexit --enable-threads=posix Thread model: posix gcc version 3.4.4 Operating system: Linux, SuSE 9.3

2 1

A error when using long option description, program_options library
by 沈慧峰 06 Sep '05

06 Sep '05

This runtime error only occurs when debug version, the release version has no such problem. The long option description can not be printed. My platform is vc7.1+stlport 4.62+boost 1.33, I also define the macro _STLP_DEBUG and BOOST_LIB_DIAGNOSTIC. Some extraction of my code: operatoins.add_options() ("difference,d", "Get all the word of mine, origin file, my file, output file") ("replace,r", "Replace the wrong pinyin with the right(delete maybe wrong chongma)" ", right file, origin file, new file") ("remove", po::value<string>(), "delete the word specified by regex expression") ("merge,m", "merge the files specified") ("regex", "match regex") ("files,f", po::value< vector<string> >(), "input file"); when print "Get all the word of mine, origin file, my file, output ", a runtime error occurs, the program terminates. Although I can give the debug version a short description and the release version a long description, it is boring. The error occur in the code call format_one()/format_description/format_paragraph The error code is line 361, options_description.cpp: if (line_begin + (line_length - indent) > par_end) { line_end = par_end; } else { line_end = line_begin + (line_length - indent); }

3 2

Re: [Boost-users] bgl - add_vertex during breadth first
by Abebaw Wubshet 06 Sep '05

06 Sep '05

Hi Jeremy, Many thanks for the response. I was hoping I could add vertices inside the algorithm visitor based on some conditions and these same conditions will be applied when the newly added vertices are visited by calling the algorithm only once (a kind of recursive effect). Now it seems that I have to call the algorithm many times and introduce some sort of my own implementation of colour or add a property to each vertex which flags whether it is already expanded or not. Is there any better idea? Cheers, Abebaw > Message: 5 > Date: Mon, 5 Sep 2005 17:19:21 -0500 > From: Jeremy Siek <jeremy.siek(a)gmail.com> > Subject: Re: [Boost-users] bgl - add_vertex during breadth first > search > To: boost-users(a)lists.boost.org > Message-ID: <BE018FBF-735B-4948-8B2A-66793695F214(a)gmail.com> > Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed > > Hi Abebaw, > > Adding vertices and edges is a dangerous thing to do inside an > algorithm visitor. This is because doing that invalidates > iterators that the algorithm is using. Also, the algorithm > creates a mapping from vertices to colors (to mark > which vertices have been processed), and adding vertices > will mess up that mapping. Can you just record that > you want to add vertices and do it after the BFS? > > Cheers, > Jeremy > > On Sep 4, 2005, at 7:43 AM, Abebaw Wubshet wrote: > > Hi all, > > > > I have started using the boost graph library recently. I want to > > add vertices > > and edges to a graph through an algorithm visitor. I chose the > > 'discover_vertex' > > event and added some code to add a vertex/edge. But the compiler > > could not > > determine the apporpriate the matching add_vertex/add_edge > > function. I tried > > fully specifiying the template arguments with no success. (I am > > using gcc 3.3.1 > > on SuSE Linux.) > > > > I tried another alternative which does not work either. I created a > > pointer to a > > graph object which points to my graph insided the > > 'discover_vertex'. But then I > > ended up having a run time error after the vertex is added. > > > > Many thanks, > > Abebaw Wubshet > > > > > > Here is a sample code > > / > > ********************************************************************** > > **/ > > #include <boost/config.hpp> > > #include <iostream> > > #include <boost/graph/adjacency_list.hpp> > > #include <boost/graph/breadth_first_search.hpp> > > #include <boost/shared_ptr.hpp> > > > > using namespace boost; > > > > class VertexProperties > > { > > public: > > std::string _name; > > VertexProperties () {} > > VertexProperties (std::string name) : _name(name) {} > > }; > > > > //OPTION ONE > > class bfs_extend_graph1 : public default_bfs_visitor > > { > > public: > > template<typename Vertex, typename Graph> > > void discover_vertex (Vertex v, Graph& g) > > { > > std::cout<<"\ndiscover"; > > Vertex v_new; > > //the compile gets confused here !!!!! > > v_new = add_vertex(VertexProperties("C"),g); > > add_edge(v,v_new,g); > > } > > }; > > > > //OPTION TWO > > class bfs_extend_graph2 : public default_bfs_visitor > > { > > public: > > template<typename Vertex, typename Graph> > > void discover_vertex (Vertex v, Graph& g) > > { > > std::cout<<"\ndiscover"; > > Vertex v_new; > > typedef adjacency_list< vecS, vecS, directedS, > > VertexProperties> > > graph_t; > > //a pointer to > > shared_ptr<graph_t> ptr_g; > > *ptr_g = g; //reference to the actual graph > > v_new = add_vertex(VertexProperties("C"),*ptr_g); > > add_edge(v,v_new,*ptr_g); > > } > > }; > > > > > > int main() > > { > > typedef adjacency_list< vecS, vecS, directedS, > > VertexProperties> graph_t; > > typedef graph_traits<graph_t>::vertex_descriptor Vertex; > > typedef graph_traits<graph_t>::vertex_iterator vertex_iterator; > > typedef property_map<graph_t,std::string > > VertexProperties::*>::type VP_map_t; > > > > graph_t g; > > Vertex v1,v2; > > > > v1 = add_vertex(VertexProperties("A"),g); > > v2 = add_vertex(VertexProperties("B"),g); > > add_edge(v1,v2,g); > > > > //get the VP map > > VP_map_t VP_map = get(&VertexProperties::_name,g); > > > > bfs_extend_graph1 bfs_e1; > > breadth_first_search(g,v1,visitor(bfs_e1)); > > > > bfs_extend_graph2 bfs_e2; > > breadth_first_search(g,v1,visitor(bfs_e2)); > > > > //check if everything is okay > > std::pair<vertex_iterator, vertex_iterator> vp; > > std::cout<<std::endl<<"vertices : "; > > for ( vp = vertices(g); vp.first != vp.second; ++vp.first) > > { > > VertexProperties vp1 = get(VP_map,*vp.first); > > std::cout<<"\t"<<vp1._name; > > } > > > > return 0; > > } > > > > / > > ********************************************************************** > > **/

1 0

[program_options] VC6 compile error 'illegal pure syntax, must be "=0"'
by Gottenbos, Hennie 06 Sep '05

06 Sep '05

Hi All, I am having problems using the [program_options] library from Boost 1.33. Using this simple program: #include <boost/program_options.hpp> int main(int argc, char* argv[]) { return 0; } I get compile errors like: options_description.hpp(156) : error C2258: illegal pure syntax, must be '= 0' options_description.hpp(156) : error C2252: 'm_default_line_length' : pure specifier can only be specified for functions options_description.hpp(159) : error C2065: 'm_default_line_length' : undeclared identifier This is the first time I'm using Boost. I have successfully developed a program that uses boost::filesystem but I have funny feeling this is a compiler limitation which means I can not use [program_options] on VC6. Can anyone confirm this so I can forget about program_options? Thanks! Hennie.

3 2

Passing template class name without type arguments
by Ovanes Markarian 06 Sep '05

06 Sep '05

Hello, I have a problem. I would like to use standart C++ <functional> function wrappers, but have a problem. At least in MS VC 7.0 a binary_function derivate (like plus) is defined: template<class Type> struct plus : public binary_function <Type, Type, Type> { Type operator()( const Type& _Left, const Type& _Right ) const; }; So if I am goint to add int and double value I will get int back. How can find a work around? First I was thinking about smth like: template<class _Arg1, class _Arg2> struct _ResultType { //some general implementation like typedef typename _Arg1 result_type; }; //specializations like: template<> struct _ResultType<long, double> { typedef double result_type; }; template<class _BinaryFct, class _ResultType> struct Expression { typedef typename _ResultType::result_type result_t; typedef typename _BinaryFct<result_t> binary_fct; //other definitions etc... }; somewhere in the code: #include <functional> Expression<std::plus, _ResultType<long, double> > myExpr; A C++ compiler awaits a real type which causes an error. How else can I change the type of plus<long> to plus<double>. Probably I could write smth like this: typedef std::plus<_ResultType<long, double> > myBinaryFunction; Expression<myBinaryFunction> myExpr; But somehow I don't like it, since the _ResultType class will contain more information as simple result_type. And I will need to pass it twice like: typedef std::plus<_ResultType<long, double> > myBinaryFunction; Expression<myBinaryFunction, _ResultType<long, double> > myExpr; This make the code not very readable... Is there any way using boost to overcome this? With Kind Regards, Ovanes Markarian

1 0

Cannot find a symbol in boost_thread-mt.dll
by Anatoli Sakhnik 06 Sep '05

06 Sep '05

Hi, boost users! I've just tried to execute the simplest boost::thread program, compiled by vc7_1 under multi threaded dll environment. It failed to resolve a symbol in the boost_thead-mt.dll (see the attach). Why? Is it possible to use linked dynamically boost::thread library now? Info: boost version is latest CVS, compiled with --layout=system. No error occurs after gcc-3.4. The program's source: #define BOOST_ALL_NO_LIB #include <boost/thread.hpp> void f() {} int main(int argc, char* argv[]) { boost::thread(f).join(); return 0; } -- Anatoli Sakhnik

2 2