March 2005 - Boost-users - lists.boost.org

Creating custom depth first search visitor for Boost graph
by Stephen Torri 15 Mar '05

15 Mar '05

I have a need to have a graph visitor algorithm similar to depth first search. The only difference is that if upon running discover_vertex the intended operation to be done on the vertex is not done I want the graph color value for this position to still be white. The reason is that the graph I am using the depth first search is a directed graph with no loops in it. A vertex might have two or more vertices providing information. If all the information is not there I want the visitor to try again. What do I have to do to gain access to the color map inside the visitor when I am in discover_vertex? Stephen

3 6

graph peculiarities
by Arias Brent-P96059 14 Mar '05

14 Mar '05

I've been looking over the graph library, and have found it curiously designed. I was hoping someone could provide a brief comment on the rationale of the design (something I didn't spot in the documentation). For example, consider the adjacency_list: adjacency_list<OutEdgeList, VertexList, Directed, VertexProperties, EdgeProperties, GraphProperties, EdgeList> I would have thought that the "VertexList" would be templated to permit me to add whatever kind of node I'd like, something like this: adjacency_list<listS, vecS<myType>, bidirectionalS> But instead, there is a rather elaborate process of creating a user defined "property" and installing that property. What was the rationale for that "install property" approach, rather than just a templated parameter approach (as I suggested above)? Even with the improvement with the new "bundled properties" approach of 1.32.0, I find myself still asking the same or similar questions. For example, after an adjacency list is created, why do I need to access the properties of the nodes (bundled or not), with vertex_descriptors? I mean, for example, the "std::map<string, int>" type doesn't require that I make a seperate "vertex_descriptor" or "definition_descriptor" to access an entry in the map. Certainly there was some rationale behind this "vertex descriptor" approach - does anyone know what it was? Thanks, -Brent

2 1

C++ Template Metaprogramming - Exercise 3-6
by Bruno Martínez Aguerre 14 Mar '05

14 Mar '05

Hi, I'm stuck at exercise 3-6 of the book. I have to write twice (see below) as a lambda expression. I don't understand why the same transformation that works for quasi fails for twice. Any help, please? #include <boost/type_traits/add_pointer.hpp> #include <boost/type_traits/is_same.hpp> #include <boost/mpl/assert.hpp> #include <boost/mpl/plus.hpp> #include <boost/mpl/int.hpp> #include <boost/mpl/placeholders.hpp> #include <boost/mpl/apply.hpp> #include <boost/mpl/lambda.hpp> #include <boost/mpl/equal_to.hpp> using namespace boost; using namespace boost::mpl; using namespace boost::mpl::placeholders; template <class F, class A> struct twice : apply<F, typename apply<F, A>::type > {}; BOOST_MPL_ASSERT(( is_same<twice<add_pointer<_1>,int>::type, int**> )); template <class F, class A> struct quasi : plus<F, typename plus<F, A>::type > {}; BOOST_MPL_ASSERT(( equal_to<quasi<int_<2>,int_<3> >, int_<7> > )); template <class F, class A> struct quasi2 : apply<plus<_1, plus<_1,_2> >, F, A >::type {}; BOOST_MPL_ASSERT(( equal_to<quasi2<int_<2>,int_<3> >, int_<7> > )); template <class F, class A> struct twice2 : apply<apply<_1, apply<_1,_2> >, F, A >::type {}; BOOST_MPL_ASSERT(( is_same<twice2<add_pointer<_1>,int>::type, int**> )); - Bruno

7 12

Bug in boost/graph/transitive_closure.hpp
by Todd A. Gibson 14 Mar '05

14 Mar '05

Bug: The header file boost/graph/transitive_closure.hpp contains an unscoped call to not1(). This function is defined in both the std namespace and the boost namespace (via boost/functional.hpp). If boost/functional.hpp is included either directly or indirectly (e.g., via boost/multi_array.hpp) Then any attempted use of transitive_closure() will not compile due to the ambiguity. Solution: Scope the call to not1 in boost/graph/transitive_closure.hpp: std::not1 Note: This bug can be easily be reproduced by including boost/functional.hpp (or boost/multi_array.hpp) To the example program transitive_closure.cpp . Thanks, -TAG Todd A. Gibson

3 3

boost::serialization within libraries
by Carsten Tham 14 Mar '05

14 Mar '05

Hi, i've run into a problem with serialization in combination with static-libraries: In my first try i defined BOOST_CLASS_EXPORT in the header-file of my exported classes. It worked for the libraries but gave me linker-errors in my applications (multiple defines). I think the link-problems are due to some static functions, defined by BOOST_CLASS_EXPORT, therefore i moved the macro-instantiations to my application, which fixed my problem. If this is the correct way to handle the issue i would suggest to include this situation in the docs. BTW: I want to thank Robert Ramey for this great library! It serialized my deeply nested object-structure with lots of shared smart-ptr's without any problem in all 3 formats and with very little work on my side. Thanks for such a great contribution to boost! Regards - Carsten -- SMS bei wichtigen e-mails und Ihre Gedanken sind frei ... Alle Infos zur SMS-Benachrichtigung: http://www.gmx.net/de/go/sms

2 1

BGL: EdgeList template parameter specification for undirected graphs
by Anatoly Petkevich 14 Mar '05

14 Mar '05

Hi! I am trying to use the BGL to create sparse undirected graph using boost::setS as template argument for EdgeList parameter: typedef adjacency_list<vecS, vecS, undirectedS, no_property, no_property, no_property, setS> GraphType; Impementation of boost::add_edge() for undirected graphs calls g.m_edges.push_back(e), and we get compilation error here since push_back() is not a member of associative container std::set. There is no such a problem for directed graphs (directedS). According to the BGL documentation there are no restrictions on EdgeList parameter for undirected graphs. Is this an undocumented feature or inconsistent implementation or library misuse? Regards, A.Petkevich

3 3

Re: [Boost-users] Graph Library - bundled properties, internal & external properties
by Elvanör 14 Mar '05

14 Mar '05

Hello again, >> Second, with bundled properties I have troubles with constructors. I >> created a class myClass, that I will use as a struct for the bundled >> properties. This class contains reference members so it needs a >> constructor better than the default constructor without any >> arguments. Creating a graph with these bundled properties doesn't >> allow me to use another constructor than the default myClass() one, >> it seems. I think it would be very good if I could create an array of >> myClass and then point my Graph object to this array to use it as >> bundled properties. Then I could do all the initialization I want >> cleanly. > > I think that when you add an edge or vertex, you can just pass a > myClass instance before the graph argument, e.g,, > > v = add_vertex(myClass(some_reference), g); Ok, so that would solve one of my problems. Thank you. > > >> My last problem is with the depth_first_search() algorithm... and of >> course bundled properties. This algorithm takes a const Graph &; but >> I want to be able to modify (while running the algorithm) the bundled >> properties!! That is the whole point of running this algorithm. I >> don't want to change the structure of the graph (the abstract graph - >> links from vertices to edges, etc), while running the algorithm, of >> course, but I do want to change when I want my bundled properties... >> that is not possible (at least, not without compiler warnings, which >> I don't like :-) due to the fact that depth_first_search expects a >> const graph. > > Yeah, this is an annoying problem. We'd like to be able to take either > a const or a non-const graph, but doing so would require two overloads > of the algorithm, which we really can't do (too much code!). Like someone else pointed out, what do you mean by too much code? It would require too much time? Or would it be considered a problem for more "fundamental" reasons (ie, that could lead to trouble in existing code, etc...)? > I suggest that you put a non-const reference to the graph from within > your visitor and use that instead of the graph that is passed to the > event functions. I am not sure I understand how you would do that... Am I correct in understanding that you would declare a non const reference as a member in your visitor? And then you would have to pass the Graph object when you create the visitor. That means a visitor would be suitable for only one graph (that is not a problem in my case, just a remark) on which you intend to use the visitor on. Another way would be to use pointers to objects as bundled properties, instead of directly the object themselves. I think that should work and that's what I am using right now. Basically it only changes that in your visitor, it's not g[v].some_member = 4; but g[v]->some_member = 4; (if g is the graph). Seems to work fine. Jean-Noël

2 1

Graph Library - bundled properties, internal & external properties
by Elvanör 14 Mar '05

14 Mar '05

Hello everyone, this is my first post to the list so excuse me if I didn't get some concepts right. I have begun to learn the BGL as I was searching for a good graph library; I am a student in Computer Science and my thesis is about graph algorithms. I am impressed, it seems to be a good library. Plus, it has forced me at last to deepen my knowledge of STL, templates and generic programming. Now to my question: as I am a new user, when I read the documentation I decided to use the new bundled properties mechanism rather than the old properties map methods. It was recommended in the documentation (I would, btw, like to humbly point out that the documentation is not very clear on this. The bundled properties explanation page is not accessible from the content page and could confuse quite a lot of people), and anyway I found that a lot simpler. But now I am running into troubles. First, are bundled properties applicable to "external properties"? To be honest, I don't really get the difference between internal and external properties. Or do I have to use property maps (in the old way) for external properties? Second, with bundled properties I have troubles with constructors. I created a class myClass, that I will use as a struct for the bundled properties. This class contains reference members so it needs a constructor better than the default constructor without any arguments. Creating a graph with these bundled properties doesn't allow me to use another constructor than the default myClass() one, it seems. I think it would be very good if I could create an array of myClass and then point my Graph object to this array to use it as bundled properties. Then I could do all the initialization I want cleanly. Right now, it seems to me than the only way to modify these properties (prior to running a grpah algorithm for example), is to do some sort of: G[v].my_first_data_member =5; G[v].my_second_data_member = "test"; etc... with v moving over all the vertexes (or edges). This seems a little bit strange... and impossible to use reference data members with that, for exemple. My last problem is with the depth_first_search() algorithm... and of course bundled properties. This algorithm takes a const Graph &; but I want to be able to modify (while running the algorithm) the bundled properties!! That is the whole point of running this algorithm. I don't want to change the structure of the graph (the abstract graph - links from vertices to edges, etc), while running the algorithm, of course, but I do want to change when I want my bundled properties... that is not possible (at least, not without compiler warnings, which I don't like :-) due to the fact that depth_first_search expects a const graph. I think that will be all... if someone can enlighthen me on these topics I'll be happy!! Regards Jean-Noël

3 3

__stdcall with boost::function
by Olenhouse, Jason 14 Mar '05

14 Mar '05

I'm trying to pass a member function pointer around to the Windows Service Control Manager through Windpws API functions, but I think I'm having troubles with the __stdcall convention. I'm using MSVC 7.1.3088. For brevity I've left out information, but I think this is enough to go on: __ExampleClass.h__ class ExampleClass { protected: void Setup( void ); void __stdcall ServiceMain( DWORD dwArgc, LPSTR *lpszArgv ); LPSERVICE_MAIN_FUNCTION m_fServiceMain; }; __ExampleClass.cpp__ void ExampleClass::Setup( void ) { boost::function<void ( DWORD, LPSTR * )> f2 = boost::bind( boost::mem_fn( &ExampleClass::ServiceMain ), this, _1, _2 ); m_fServiceMain = f2.target<void ( DWORD, LPSTR * )>( ); SERVICE_TABLE_ENTRY dispatchTable[ ] = { { const_cast<char *>( g_sAPP_NAME.c_str( ) ), m_fServiceMain }, { 0, 0 } }; StartServiceCtrlDispatcher( dispatchTable ); } void __stdcall ExampleClass::ServiceMain( DWORD dwArgc, LPSTR *lpszArgv ) { } The error I receive concerns the line m_fServiceMain = f2.target<void ( DWORD, LPSTR * )>( ); error C2440: '=' : cannot convert from 'void (__cdecl *)(DWORD,LPSTR * )' to 'LPSERVICE_MAIN_FUNCTIONA' This conversion requires a reinterpret_cast, a C-style cast or function-style cast LPSERVICE_MAIN_FUNCTIONA is defined in "winsvc.h" and is: typedef VOID (WINAPI *LPSERVICE_MAIN_FUNCTIONA)( DWORD dwNumServicesArgs, LPSTR *lpServiceArgVectors ); Any help or insight would be much appreciated. -Jason

3 2

fruchterman_reingold doesn't like small graphs
by Jamie Wilkinson 14 Mar '05

14 Mar '05

I'm writing an app in which the user incrementally adds vertices to the graph; of course it starts empty, and after each addition the graph is laid out with the fruchterman-reingold function. The algorithm copes well with empty graphs, but once I add a single vertex, the program crashes: the crash is always in the same place, deep in std::list but called from boost/graph/fruchterman_reingold.hpp:116 : buckets[row * columns + column].push_back(*v); The push_back function calls end() to get the last element of the list, and fails. A bit of gdb turned up the following result: columns and rows were both being set to 0 and so buckets was also of size 0. Lines 111:112 also end up setting column and row to 0, and then the next pair of lines were setting them to, on my machine, 4G. The element of buckets being accessed, then, was ridiculously out of bounds. The value width/two_k, once cast to the integral size_t, was always zero. I don't think this is restricted to having a single vertex in the graph, but that case seems to exacerbate the bug. So as a workaround, I've added the following two lines to make sure that the variables columns and rows are at least 1: Index: boost/graph/fruchterman_reingold.hpp =================================================================== RCS file: /cvsroot/boost/boost/boost/graph/fruchterman_reingold.hpp,v retrieving revision 1.5 diff -u -r1.5 fruchterman_reingold.hpp --- boost/graph/fruchterman_reingold.hpp 29 Dec 2004 16:53:05 -0000 1.5 +++ boost/graph/fruchterman_reingold.hpp 13 Jan 2005 13:09:00 -0000 @@ -105,6 +105,8 @@ std::size_t columns = std::size_t(width / two_k); std::size_t rows = std::size_t(height / two_k); + if (columns == 0) columns = 1; + if (rows == 0) rows = 1; buckets_t buckets(rows * columns); vertex_iterator v, v_end; for (tie(v, v_end) = vertices(g); v != v_end; ++v) { If you wish to reproduce this bug, you can do so with the example program libs/graph/example/fr_layout.cpp : g++ -Iboost boost/libs/graph/example/fr_layout.cpp echo "A B" | ./a.out 100 100 My results without the patched function: willow% echo "A B" | ./a.out 100 100 0% 10 20 30 40 50 60 70 80 90 100% |----|----|----|----|----|----|----|----|----|----| *zsh: done echo "A B" | zsh: segmentation fault ./a.out 100 100 and patched: willow% echo "A B" | ./a.out 100 100 0% 10 20 30 40 50 60 70 80 90 100% |----|----|----|----|----|----|----|----|----|----| *************************************************** A -41.0322 -29.471 B 1.16969 27.1354

2 1