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

Graph: Generic access to vertex/edge properties
by Tarjei Knapstad 09 Aug '02

09 Aug '02

Hi. I'm currently trying to implement a generic pattern matching (aka subgraph isomorphism) algorithm for use with the Boost Graph Library. My first-attempt function signature looks like this (comments included for further description of what I'm attempting) //! Seeks to find matches of the graph \a g2 in the graph \a g1. /*! This is called "graph pattern matching", or "subgraph homomorphism/isomorphism". The results are returned in a std::list of std::maps where the maps' key is the node_descriptor in \a g2 and the values are the corresponding node_descriptors in \a g1. The size of the returned list represents the number of matches. If \a properties is true it means that all vertex and edge properties must be equal in both structures for a match to be found. Otherwise, only the graph structure itself will be checked. \sa positioned_pattern_match */ template <class Graph> std::list< std::map<typename graph_traits<Graph>::vertex_descriptor, typename graph_traits<Graph>::vertex_descriptor> > pattern_match(const Graph& g1, const Graph& g2, bool properties = true); For the case where the 'properties' switch is false I have everything I need, but if 'properties' is true I'm a bit unsure on how to proceed. The problem, as I see it, is to do a generic consecutive access of all the properties of the current vertex/edge being checked and see if they're equal in both 'g1' and 'g2'. Could anyone provide me a solution/clue on how to solve this problem in a generic way so that the algorithm can be used for any graph? Regards, -- Tarjei Knapstad

3 2

VC7 build error without #define BOOST_DISABLE_WIN32
by Martin Schuerch 08 Aug '02

08 Aug '02

Hi I have an application with MFC / ATL and also some files compiled with the /clr option. Throuout the application boost is used a lot. All builds well as long as #define BOOST_DISABLE_WIN32 is set in the user.hpp file. Without this option a) the build hangs during registration after linking or b) link error due to differently defined custom attributes (in a file using /clr option) Did anybody had similar problems already? Regards Martin

1 0

iterator_adaptor and operator-> for input iterators
by Beman Dawes 07 Aug '02

07 Aug '02

I wrote an iterator to do recursive directory iteration. The heart of it is: template< typename Predicate > class recursive_directory_iterator : public boost::iterator_adaptor< boost::shared_ptr< detail::rdi_imp< Predicate > >, detail::rdi_policies, const boost::filesystem::path, const boost::filesystem::path &, const boost::filesystem::path *, std::input_iterator_tag, std::ptrdiff_t > { ... }; Works fine as long as you stay away from operator->. For example, fs::recursive_directory_iterator<pred_type> rdi( dir , dummy ); fs::recursive_directory_iterator<pred_type> rdi_end; for ( ; rdi != rdi_end; ++rdi ) { // std::cout << rdi->generic_path() << std::endl; std::cout << (*rdi).generic_path() << std::endl; } works as expected. But if you uncomment the commented line, the program fails in the call to operator->. What "fails" means depends on the execution environment; whatever is happening seems to confuse the debugger, stepping doesn't shed much light on the problem. Same symptoms with both VC++7 and Intel 6.0. I suppose I'm doing something stupid, but don't have a clue as to what. I notice in iterator_adaptor_test.cpp that operator-> is not actually exercised. Is it possible there is a bug in it for input iterators? I've not had similar problems with iterator_adaptor for bidirectional iterators. Any help appreciated, --Beman

1 0

Newbie and his template for comments.
by Kamil Burzynski 07 Aug '02

07 Aug '02

Hello. I'm a C++ developer, who is learning STL recently, and loving it :) I've encountered Boost library, which seems to extending STL funcationality a lot :) I've also created a sampel template for usage in my company, and I would like to get comments about it: is this code ok, exception safe, somebody did it better things like that. In my projects I'm often using structures like map<T1, T2 *>, e.g. map<int, Point *> or map<string, Person*> or something like this. So, often I want to do something like that: map<int, Point *> my_map; map<int, Point *>::iterator it; /* .. */ for( it=my_map.begin();it!=my_map.end();++it ) { it->second->Reset(); //sets x,y to 0,0 } example may be stupid, but shows what I'm trying to explain. To improve it I've created a template (given below), so I ca use it like that: for_each( my_map.begin(), my_map.end(), map_fun( &Point::Reset ) ); Which i think is much better. My template is as follows (style is kept from GCC includes, so it may be not as readable as it could be :) template <class _Ret, class _Tp> class map_fun_t : public unary_function<_Tp*,_Ret> { public: explicit map_fun_t(_Ret (_Tp::*__pf)()) : _M_f(__pf) {} template< class _Mp> _Ret operator()(_Mp &__p) const { return ((__p.second)->*_M_f)(); } private: _Ret (_Tp::*_M_f)(); }; template <class _Ret, class _Tp> inline map_fun_t<_Ret,_Tp> map_fun(_Ret (_Tp::*__f)()) { return map_fun_t<_Ret,_Tp>(__f); } What do you think about it? Has it any flaws? Somebody done it already? Is it usable for anyone except me? :) Thanks in advance. -- Best regards from Kamil Burzynski Senior Design Engineer Advanced Digital Broadcast Poland, LTD. - - "Yes, I'm criminal. My crime is that of curiosity."

4 6

Regex++ link problem with VC6 when building with _UNICODE defined
by Edward Diener 07 Aug '02

07 Aug '02

If I build boost 1.28 regex with _UNICODE defined and then attempt to link the static mssd.lib version with a _UNICODE application using the library, I get: boost_regex_vc6_mssd.lib(w32_regex_traits.obj) : error LNK2005: _iswspace already defined in libcmtd.lib(_wctype.obj) boost_regex_vc6_mssd.lib(c_regex_traits.obj) : error LNK2005: _iswalpha already defined in libcmtd.lib(_wctype.obj) boost_regex_vc6_mssd.lib(c_regex_traits.obj) : error LNK2005: _iswupper already defined in libcmtd.lib(_wctype.obj) boost_regex_vc6_mssd.lib(c_regex_traits.obj) : error LNK2005: _iswlower already defined in libcmtd.lib(_wctype.obj) boost_regex_vc6_mssd.lib(c_regex_traits.obj) : error LNK2005: _iswdigit already defined in libcmtd.lib(_wctype.obj) boost_regex_vc6_mssd.lib(c_regex_traits.obj) : error LNK2005: _iswxdigit already defined in libcmtd.lib(_wctype.obj) boost_regex_vc6_mssd.lib(c_regex_traits.obj) : error LNK2005: _iswspace already defined in libcmtd.lib(_wctype.obj) boost_regex_vc6_mssd.lib(c_regex_traits.obj) : error LNK2005: _iswpunct already defined in libcmtd.lib(_wctype.obj) boost_regex_vc6_mssd.lib(c_regex_traits.obj) : error LNK2005: _iswcntrl already defined in libcmtd.lib(_wctype.obj) Debug/TestRegularExpressionGUIStatic.exe : fatal error LNK1169: one or more multiply defined symbols found Error executing link.exe. This only occurs in the debug multi-threaded static library version. Has anyone else seen this or know why it might occur ? If I change the build options for this library from /Od /Gz to /O2, everything works fine and no linker errors occur.

2 1

[BGL] Common children for vertices in DAG
by Erik Arner 07 Aug '02

07 Aug '02

Is there a fast way, with or without preprocessing of the graph, for checking if two non-adjacent vertices in a DAG have one or more common children? Any pointers to components of the BGL that implement, or can be used to implement, this task would be much appreciated. Thanks, Erik

2 4

Tuple from cons list
by j1k1cki 07 Aug '02

07 Aug '02

Hi, Is there a simple way of obtaining a tuple type out of cons list? It also seems natural to build tuple type from two MPL iterators. Is such code available anywhere already? Best regards

1 0

BGL: Problem with parallel edges and filtered_graph
by Michael Kettner 06 Aug '02

06 Aug '02

-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Hi Jeremy, I think I discovered a problem concerning filtered_graphs and parallel edges: Assume I have a graph containing two edges E1 and E2 connecting node A and node B. Now I crate a boost::filtered_graph (myFilteredGraph) with a filter that returns true for only E1. When I now try to get E1 by calling edge = boost::edge( A, B, myFilteredGraph ).first; the result is undefined. Looking at the code (filtered_graph.hpp) I found out that the edge is return by: edge(typename filtered_graph<G, EP, VP>::vertex_descriptor u, typename filtered_graph<G, EP, VP>::vertex_descriptor v, const filtered_graph<G, EP, VP>& g) { typename G::edge_descriptor e; bool exists; tie(e, exists) = edge(u, v, g.m_g); return std::make_pair(e, exists && g.m_edge_pred(e)); } Here, the line tie(e, exists) = edge(u, v, g.m_g); returns _some_ edge, but not necessarily the _right_ one. The call edge(...) is not called for the filtered graph and g.m_edge_pred(e) is called _after_ getting the wrong edge (resulting in a return value FALSE). One solution would be to call boost::edge_range(A, B, myFilteredGraph) on my filtered_graph to get all visible edges, but this function is not provided. Any ideas how to solve my problem? Michael - -- http://www.ive.uni-hannover.de # kettner(a)ive.uni-hannover.de -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.0.6 (GNU/Linux) Comment: For info see http://www.gnupg.org iD8DBQE9TqUAkCdGnb0kVFMRAlsLAJwKJJ2NSLRu2HUv/H4sAhr4W5WdkACdHXZ6 3kz8fBDvysWKc1vxd5rf/CE= =l+NV -----END PGP SIGNATURE-----

2 3

BGL: dijkstra_shortest_paths and parallel edges
by Michael Kettner 06 Aug '02

06 Aug '02

-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Hi, my former posting leads me to another question: How does the dijkstra_shortest_paths behave if applied to a multigraph? And how does the dijkstra_shortest_paths behave if applied to a filtered_(multi)graph containing parallel edges, but with only _one_ of the parallel edges visible respectively? Michael - -- http://www.ive.uni-hannover.de # kettner(a)ive.uni-hannover.de -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.0.6 (GNU/Linux) Comment: For info see http://www.gnupg.org iD8DBQE9TqprkCdGnb0kVFMRApGUAJ9nzr3Y4ijbrNnWENzxYIwcdLy8iQCfX2fx dl0M/IUt2bWFL0H9ovwajm4= =+FTJ -----END PGP SIGNATURE-----

2 1

BGL example boost_web_graph.expected
by Arjun Bijanki 06 Aug '02

06 Aug '02

When I compile and run Boost_1_28_0/libs/graph/example/boost_web_graph.cpp my output differs from the expected output: 1c1 < The diameter of the boost web-site graph is 2 --- > The diameter of the boost web-site graph is 3 Is the expected file current? Thanks, Arjun Bijanki Microsoft VC++ [Non-text portions of this message have been removed]

2 1