- Boost-users - lists.boost.org

Combining static and dynamic policies
by Jens Müller 23 Nov '06

23 Nov '06

Hi, I have the following task: There is an algorithm where you can set different behaviors for creating a BFS tree. Currently this is done by setting a policy object (dynamic), a function of which is called to perform the search. I'd like to use static policies here (as is done in generic Boost algorithms), but still keep the possibility of setting the behavior manually. The reason for this is: You can set the behavior using a command line parameter, and it would be impractical to instantiate all templates and then use a huge switch (think of combinations of several policies) to choose the appropriate instantiation. Here a wrapper (dynamic polymorphism) would be needed anyway, or any code using the algorithm would need to be duplicated as well. So my idea is as follows: There is a template parameter for a policy class. Static policy exist for each possible behavior, as well for a dynamic behavior. The "dynamic" policy class has virtual member functions and there exists an inheriting dynamic class for each behavior.[1] The algorithm then has a named param for the policy class. Default value if to default-construct an object of the policy class. (If useful, the template might have a default value for the policy template parameter as well, so the user needn't do anything). Has someone already taken this or a similiar approach? If so, could you point me to a reference? What do you think of the approach? Greeting, Jens [1] Hmmm ... Could this inheriting class be used as template parameter without overhead? Other solution would be: class dyn_behavior{ public: virtual void perform_search(something ...) = 0; } class specific_dyn_behavior<class T> : dyn_behavior { T behavior; public: void perform_search(something ...){ behavior.perform_search(something ...); } }

1 0

shared_ptr. circular references
by bringiton bringiton 23 Nov '06

23 Nov '06

Can anyone offer advice on detecting circular references with shared_ptrs. I have a large app, 50+ classes, and most objects are managed with shared_ptrs. No consideration has gone into avoid circular references, so I'm sure there will be a few in there. I thinking that looking though all the classes and their attributes will take a while. Any suggestions/advice in finding circular references (so i can use weak_ptrs)? I was thinking of maybe getting a tool that draws the class diagram. Or having a base class for all my classes that reference count to a global variable to detect the number of leaks. It seems the shared_ptr is a good idea for memory management, but it opens up the original problem of memory leaks...

4 3

[serialization] linking
by Deane Yang 23 Nov '06

23 Nov '06

I am using bjam with Boost Build v2 to compile and link an executable that calls the boost serialization library using MSVC++ 8.0. For some reason, it tries to link to a library named "libboost..." but the actual library is called "boost...." (no "lib" prefix). Why is this happening and how do I fix it? It doesn't happen when I compile the same executable in Linux.

5 11

[BGL] working file_dependencies.cpp
by Alexander Holler 22 Nov '06

22 Nov '06

Hello, I've already though some time that something does not work as expected using the way the various file_dependencies.cpp examples have done for calculating what files could be compiled in parallel. Because I've now got to a point where I really need something working, I've just done it myself. ;) My solution is pretty simple, and it basically works like it is described in the documentation for the example, walk through the tree and calculate the maximum distance. To achieve that, I'm just using the result from topological_sort and calculating the maximum through a walk through the in_edges of the vertices. Because a diff is almost as large as the resulting example, I've just attached the modified example. It might not look as nice as the original example, but it works as expected. ;) Kind regards, Alexander Holler //======================================================================= // Copyright 1997, 1998, 1999, 2000 University of Notre Dame. // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek // // Distributed under the Boost Software License, Version 1.0. (See // accompanying file LICENSE_1_0.txt or copy at // http://www.boost.org/LICENSE_1_0.txt) //======================================================================= // Some small modifications are done by Alexander Holler /* Paul Moore's request: As an example of a practical problem which is not restricted to graph "experts", consider file dependencies. It's basically graph construction, plus topological sort, but it might make a nice "tutorial" example. Build a dependency graph of files, then use the algorithms to do things like 1. Produce a full recompilation order (topological sort, by modified date) 2. Produce a "parallel" recompilation order (same as above, but group files which can be built in parallel) 3. Change analysis (if I change file x, which others need recompiling) 4. Dependency changes (if I add a dependency between file x and file y, what are the effects) */ #include <boost/config.hpp> // put this first to suppress some VC++ warnings #include <iostream> #include <iterator> #include <algorithm> #include <time.h> #include <boost/utility.hpp> #include <boost/graph/adjacency_list.hpp> #include <boost/graph/topological_sort.hpp> #include <boost/graph/depth_first_search.hpp> #include <boost/graph/dijkstra_shortest_paths.hpp> #include <boost/graph/visitors.hpp> using namespace std; using namespace boost; enum files_e { dax_h, yow_h, boz_h, zow_h, foo_cpp, foo_o, bar_cpp, bar_o, libfoobar_a, zig_cpp, zig_o, zag_cpp, zag_o, libzigzag_a, killerapp, N }; const char* name[] = { "dax.h", "yow.h", "boz.h", "zow.h", "foo.cpp", "foo.o", "bar.cpp", "bar.o", "libfoobar.a", "zig.cpp", "zig.o", "zag.cpp", "zag.o", "libzigzag.a", "killerapp" }; struct print_visitor : public bfs_visitor<> { template <class Vertex, class Graph> void discover_vertex(Vertex v, Graph&) { cout << name[v] << " "; } }; struct cycle_detector : public dfs_visitor<> { cycle_detector(bool& has_cycle) : m_has_cycle(has_cycle) { } template <class Edge, class Graph> void back_edge(Edge, Graph&) { m_has_cycle = true; } protected: bool& m_has_cycle; }; int main(int,char*[]) { typedef pair<int,int> Edge; Edge used_by[] = { Edge(dax_h, foo_cpp), Edge(dax_h, bar_cpp), Edge(dax_h, yow_h), Edge(yow_h, bar_cpp), Edge(yow_h, zag_cpp), Edge(boz_h, bar_cpp), Edge(boz_h, zig_cpp), Edge(boz_h, zag_cpp), Edge(zow_h, foo_cpp), Edge(foo_cpp, foo_o), Edge(foo_o, libfoobar_a), Edge(bar_cpp, bar_o), Edge(bar_o, libfoobar_a), Edge(libfoobar_a, libzigzag_a), Edge(zig_cpp, zig_o), Edge(zig_o, libzigzag_a), Edge(zag_cpp, zag_o), Edge(zag_o, libzigzag_a), Edge(libzigzag_a, killerapp) }; const std::size_t nedges = sizeof(used_by)/sizeof(Edge); typedef adjacency_list<vecS, vecS, bidirectionalS, property<vertex_distance_t, int> > Graph; #if defined(BOOST_MSVC) && BOOST_MSVC <= 1300 // VC++ can't handle the iterator constructor Graph g(N); for (std::size_t j = 0; j < nedges; ++j) { graph_traits<Graph>::edge_descriptor e; bool inserted; tie(e, inserted) = add_edge(used_by[j].first, used_by[j].second, g); } #else Graph g(used_by, used_by + nedges, N); #endif typedef graph_traits<Graph>::vertex_descriptor Vertex; // Determine ordering for a full recompilation // and the order with files that can be compiled in parallel { typedef list<Vertex> MakeOrder; MakeOrder make_order; property_map<Graph, vertex_distance_t>::type distance = get(vertex_distance, g); topological_sort(g, std::front_inserter(make_order)); cout << "make ordering: "; for (MakeOrder::iterator i = make_order.begin(); i != make_order.end(); ++i) { cout << name[*i] << " "; // Walk through the in_edges an calculate the maximum distance. Graph::in_edge_iterator j, j_end; tie(j, j_end) = in_edges(*i, g); if(j==j_end) distance[*i]=0; else { int maxdist=0; // Through the order from topological sort, we are sure that every // distance we are using here is already initialized. for (; j != j_end; ++j) maxdist=std::max(distance[source(*j, g)], maxdist); distance[*i]=maxdist+1; } } cout << endl << endl; cout << "parallel make ordering, " << endl << "vertices with same group number can be made in parallel" << endl; graph_traits<Graph>::vertex_iterator i, iend; for (tie(i,iend) = vertices(g); i != iend; ++i) cout << "time_slot[" << name[*i] << "] = " << distance[*i] << endl; } cout << endl; // if I change yow.h what files need to be re-made? { cout << "A change to yow.h will cause what to be re-made?" << endl; print_visitor vis; breadth_first_search(g, vertex(yow_h, g), visitor(vis)); cout << endl; } cout << endl; // are there any cycles in the graph? { bool has_cycle = false; cycle_detector vis(has_cycle); depth_first_search(g, visitor(vis)); cout << "The graph has a cycle? " << has_cycle << endl; } cout << endl; // add a dependency going from bar.cpp to dax.h { cout << "adding edge bar_cpp -> dax_h" << endl; add_edge(bar_cpp, dax_h, g); } cout << endl; // are there any cycles in the graph? { bool has_cycle = false; cycle_detector vis(has_cycle); depth_first_search(g, visitor(vis)); cout << "The graph has a cycle now? " << has_cycle << endl; } return 0; }

2 2

[enable_if] Compiler workaround for constructor overloads
by Michael Marcin 22 Nov '06

22 Nov '06

Hello I'm working with a Codewarrior compiler (Nokia Codewarrior C/C++ Compiler for Windows/x86 version 3.2.3 build 451). The following test code finds the proper overload for MSVC 2005 and doesn't for the Codewarrior compiler but only with the = syntax. Does anyone have any idea how to make "c" find its overload as well? It would make the client code a lot cleaner to read/write. #include <boost/type_traits/is_integral.hpp> #include <boost/utility/enable_if.hpp> struct tester { int value; tester( float f ) : value((int)f) { } tester( double d ) : value((int)d) { } template< typename T > tester( T val, typename boost::enable_if< boost::is_integral<T> >::type* = 0 ) : value(val) { zzz } }; void main() { tester a = 1.f; // works (chooses float overload) tester b(1); // works (i.e. error on zzz) tester c = 1; // works on vc2005 (i.e. error on zzz) // fails on cw (ambiguous overload looking at float and double) }

1 0

wave - can line markers be suppressed?
by Grant, Joan 22 Nov '06

22 Nov '06

Using the wave library is there any way to suppress line markers (#line...) in a manner similar to the '-P' option of the gcc compiler's preprocessor? Thanks, Joan The information contained in or attached to this email may be subject to the Export Administration Regulations (EAR), administered by the U.S. Department of Commerce, or the International Traffic in Arms Regulations (ITAR), administered by the U.S. Department of State, and may require an export license from the Commerce or State Department prior to its export. An export can include a release or disclosure to a foreign national inside or outside the United States. Include this notice with any reproduced portion of this information.

2 2

Another generic program that won't compile with pointee, bind, and array
by Terry G 22 Nov '06

22 Nov '06

Here's another (simplified) program I can't get to work. I'm trying to write a generic routine that finds the largest element of a sequence. It is assumed that element->size() is defined, as it is for boost::array and std::string. For some reason, the Largest template function works okay for std::strings, but not for boost::arrays. Can you tell me what is wrong? Will you please offer some improvements for error detection and debugging techniques that would have helped here? Perhaps I need a "typename" or "template" somewhere. Take it as given that I have a String class that needs to be a fixed-size array. Here's the code: #include <boost/operators.hpp> #include <boost/static_assert.hpp> #include <boost/function.hpp> #include <boost/tuple/tuple.hpp> #include <boost/iterator/iterator_traits.hpp> #include <boost/bind.hpp> #include <boost/array.hpp> #include <boost/pointee.hpp> #include <cstddef> #include <iterator> #include <algorithm> #include <functional> #include <string> #include <vector> #include <iostream> #include <iomanip> template <class InIter> InIter Largest(InIter first, InIter last) { typedef typename boost::pointee<InIter>::type ObjType; InIter largest = std::max_element(first, last, boost::bind(std::less<std::size_t>(), boost::bind(&ObjType::size, _1), boost::bind(&ObjType::size, _2)) ); return largest; } // Largest template <std::size_t N> class String: public boost::array<char, N> { public: std::string str() const { if (this->back() == '\0') return std::string(this->data()); return std::string(this->data(), this->size()); } // str String() { this->assign('\0'); } String(const std::string& str_) { if (str_.size() > this->size()) throw std::runtime_error("String::ctor: str_ too big"); int copied = str_.copy(this->c_array(), this->size()); std::fill_n(this->begin() + copied, this->size() - copied, '\0'); } // ctor operator std::string() const { return str(); } }; // String using namespace std; int main(int argc, const char* argv[]) { // typedef String<64> ArgStr; // <-- This won't compile. typedef string ArgStr; // <-- This compiles/runs ok. vector<ArgStr> args; while (--argc) args.push_back(string(*++argv)); if (args.empty()) { cout << "no args!" << endl; return EXIT_FAILURE; } cout << "args="; copy(args.begin(), args.end(), ostream_iterator<string>(cout, " ")); cout << endl; vector<ArgStr>::iterator iter = Largest(args.begin(), args.end()); cout << "Largest arg is '" << string(*iter) << "'." << endl; return EXIT_SUCCESS; } // main

2 1

'configure' does not recognise '--without-python'
by MikeW 22 Nov '06

22 Nov '06

During Boost build, a line pops up saying "to avoid seeing this message again, use option --without-python". However, if you specify this as a "./configure" option, configure halts saying --without-python is unrecognised. I can live without it/work around it, but it should presumably be fixed ... Regards, Mike

2 4

[BGL] how to actually search with DFS/BFS?
by martin f krafft 22 Nov '06

22 Nov '06

This may seem like a silly question, but how does one actually search with DFS or BFS? Say I want to find the first node for which a predicate returns true in a BFS traversal starting at node N... The function signatures don't have a parameter for "criteria" or "predicate", so I guess it's up for a Visitor to implement such a check. What is not clear to me is how the visitor functions can break out of the search once a condition is true. Thanks, -- martin; (greetings from the heart of the sun.) \____ echo mailto: !#^."<*>"|tr "<*> mailto:" net@madduck invalid/expired pgp subkeys? use subkeys.pgp.net as keyserver! spamtraps: madduck.bogus(a)madduck.net "information superhighway" is just an anagram for "i'm on a huge wispy rhino fart".

9 12

[BGL] Constantness bug in kruskal_minimum_spanning_tree
by Fernando Cacciola 22 Nov '06

22 Nov '06

Hi I have a graph-like data structure which supports both const and non-const vertex and edge iterators and handles, and I want to interface it to the BGL. FWIW. the iterators and handles are class types, and the const versions are different classes than the non-const ones, so removing const qualification is not the way to bind a const type to its non-const version. AFAICT, the proper way to address both types of iterator/handles is by specializing both graph_traits<MyGraph> and graph_traits<MyGraph const>. It all works fine with my own BGL-like algorithms, but now I want to call kruskal_minimum_spanning_tree and I can't. The problem is that the kruskal function takes a "const Graph&" argument but it declares the internal types like this: typedef typename graph_traits<Graph>::edge_descriptor Edge ; (and so for the vertex_descriptor, etc) but then, lines like this: tie(vb,ve) = vertices(G) or this source(e, G) fails to compile with my graph because it attempts to bind a const iterator/handle to a non-const iterator/handle, which my data structure intentionally forbids. Unless I am missing something obvious (and I hope I am), this is a bug in the kruskal function: it should declare the working types like this: typedef typename graph_traits<Graph const>::edge_descriptor Edge ; Am I right? If yes, what can I do?? Is there any "constant correct" BGL algorithm? I'm calling kruskal just as an example showing how the data structure can be interfaced to the BGL. TIA Fernando Cacciola

2 1