- Boost-users - lists.boost.org

Could the BGL graph algorithms be improved to automatically work with VertexList = listS graphs?
by Tony Cook 16 Sep '05

16 Sep '05

Hi, If I define a BGL graph of the type typedef boost::adjacency_list <boost::vecS, boost::listS, boost::undirectedS, boost::no_property, boost::no_property, boost::no_property> BadGraphType ; Then many of the standard BGL graph algorithms such as boost::graph_copy will not compile (e.g you get "binary '+' : no operator found which takes a left-hand operand of type <type>" with VC7.1 - this did not help me understand what the problem really was - i.e. a missing vertex_index property!) This "no-compiler" problem is only fixed if either a vertex_index property map is made explicitly present on this graph type via VertexProperties template argument (See #5 on the BGL FAQ page (http://www.boost.org/libs/graphd/oc/faq.html .)) OR the particular graph algorithm is passed an external (or internal - if not of the vertex_index_t type) property map as a named parameter as in: boost::graph_copy (graph_in, graph_out, boost::vertex_index_map (i_map)) ; In either case prior to copying (or whatever) you need to ensure this property map is numbered contiguously from 0 to n - 1, where n is the number of graph vertices. My graph does not support an implicit vertex_index property, nor do I *want* to add an explicit vertex_index compatible property *just* to make these algorithms work. Especially as my graphs are dynamic and I would have to remember to renumber the property values to eliminate gaps after vertices are deleted. The BGL algorithms in this situation are particularly weak as first the "no-compile" messages are remote from the real problem, and when you have solved that then you have to prepare the graph properly prior using the algorithm! (if not you get memory scribbles if the indices are not contiguous and confined to 0 to n-1) These lead me to wonder if this problem can be eliminated and be automated as part of the algorithm itself, i.e. if no vertex_index property was supplied by any means, then the algorithm creates a temporary vertex index map, loads it with vertices mapped to indices 0 to n-1 and runs the algoritm out-of-the-box. It should be possible for the compiler to detect that the internal property map is missing AND the named parameter alternative is missing (in fact the implementations of these BGL algorithms *do* set out to discover that this is the case, but unfortunately a final vertex "descriptor-is-the-index" map (which is only true when VertexList=vecS) is assumed and hence the compilation failure and a lot grief and a steep learning curve is experienced :( ) Now to the point I wanted to make :). There IS a solution that can do this. However I'm not expert enough to merge this into the heart of each BGL graph algorithm algorithm that requires a vertex_index property. I have however developed crude wrappers that do this. Here is an example solution for boost::copy_graph that handles any graph type out of the box /** copy_graph_ex. A wrapper for boost::copy_graph that sets up the required vertex to 0 -> n - 1 index translation map @param g_in the graph to copy @param g_out the graph copy */ template <class G1, class G2> void copy_graph_ex (const G1& g_in, G2& g_out) { // Create a temporary external property map that maps vertex // descriptors to indices that will run 0 to n-1 typedef std::map<typename G1::vertex_descriptor, typename G1::vertices_size_type> i_type ; typedef boost::associative_property_map<i_type> i_map_type ; i_type i ; i_map_type i_map (i) ; // Load the external property map with values 0 to n-1 G1::vertices_size_type n = 0 ; G1::vertex_iterator vi ; G1::vertex_iterator vi_end ; for (boost::tie (vi, vi_end) = boost::vertices (g_in) ; vi != vi_end ; ++vi) { boost::put (i_map, *vi, n++) ; } // Get the BGL graph algorithm to use the constructed index map boost::copy_graph (g_in, g_out, boost::vertex_index_map (i_map)) ; } It would be much nicer if this external setup code was made part of the default handling of BGL graph algorithms that require it. What do to BGL experts/implementers say? Would it not be **saner** to get these algorithms to work automatically no matter what graph type was chosen? TIA Tony Cook (who went insane with this problem for two days)

7 14

[Graph] how to obtain the complement of a graph?
by Tzu-Chien Chiu 16 Sep '05

16 Sep '05

Given a graph G=(V,E) and its complete graph G'=(V,E'), what is the shortest code lines to obtain the complement of G_c=(V,E'-E) ?

2 1

[signal/bind/mem_fn] std::vector< boost::signal<> >
by kartoffelsack 16 Sep '05

16 Sep '05

Hi! I'd like to save any kind of functions/functors with void as parameter and as return-value in a container. I thought to use boost::bind: Let me show you some code: void bar( ) { } struct Foo { void operator(); }foo; typedef boost::signal<void ()> voidFunctionSig; std::vector< voidFunctionSig> voidFunctions; voidFunctionSig signal1; voidFunctionSig signal2; signal1.connect( &bar); signal2.connect( &foo); voidFunctions.push_back( signal1); //error voidFunctions.push_back( signal2); //same error I'm getting a Compiler-errors in the push_back-Lines: 'boost::signal<Signature>::__ctor': no nonexplicit constructor for implicit conversion: with [ Signature=void (void) ] and [ Signature=void (void) ] well, i'm not shure if boost::bind is the right choice at all, because I do not need multiple slots. Perhaps boost::bind/boost::mem_fn was enough but i cannot think how to use it. Can anybody help me to save my void (*)(void)-functions/functors and in a container? I could do it writing a superclass and a virtual op() but I would prefer to use ready-to-use boost-classes for this task. PS: using VC 7.1

2 2

Exception occurred in "boost::thread" cannot be caught by vs.net.
by 蹬三轮的 16 Sep '05

16 Sep '05

When an "access violation" exception occurred and didn't be caught by the program, it would be caught by debugger such like vs.net. 1: int main() 2: { 3: int *i = 0; 4: *i = 1; 5: } If I debug this program in vs.net, program will be broken at line 4 and an exception dialog box will be displayed. So I can know the origin of the exception. The problem is when the exception occurred in the thread started by boost::thread, program cannot be broken at the line from which exception been thrown. 01: void func() 02: { 03: int *i = NULL; 04: *i = 1; 05: } 06: int _tmain(int argc, _TCHAR* argv[]) 07: { 08: thread *t = new thread(func); 10: t->join(); 11: delete t; 12: return 0; 13: } The program should be broken at line 4, but it didn't. This makes the debugging boost::thread more difficult. How can I resolve the problem? thanks.

4 4

[Boost.Python] Infinite recursion attempting to_python conversion
by Nat Goodspeed 16 Sep '05

16 Sep '05

For some purposes we have a special string class derived from std::wstring. Simplified declaration: class cbstring: public std::wstring { public: cbstring(const wchar_t* that): std::wstring(that) {} cbstring(const std::wstring& that): std::wstring(that) {} ... }; I want to return such objects from C++ as Python Unicode strings, e.g.: cbstring produceWString() { return L"This is a test Unicode string"; } If produceWString() returns std::wstring, the conversion happens by magic. But with the cbstring return type, I get: TypeError: No to_python (by-value) converter found for C++ type: class cbstring The corresponding conversion problem (passing u"Foo" from Python to a function accepting const cbstring&) can be handled with the following call in the extension module: implicitly_convertible<std::wstring, cbstring>(); However, implicitly_convertible<cbstring, std::wstring>(); does NOT allow the produceWString() function to succeed: I still get the aforementioned TypeError. So I declared a type converter: struct cbstring_to_python { static PyObject* convert(const cbstring& cbs) { return PyUnicode_FromUnicode(cbs.c_str(), cbs.length()); } }; and registered it with: to_python_converter<cbstring, cbstring_to_python>(); The result is a stack overflow. I'm not clear on exactly why it happens, but something inside the cbstring_to_python converter is apparently recursively invoking cbstring_to_python::convert(). How *should* I go about returning our specialized string type as a Python Unicode string? OS: Microsoft Windows XP Pro, SP1 Compiler: Microsoft VC++ 7.1 with STLport 4.6 Boost version: 1.31

2 1

Re: [Boost-users] [serialization, 1_33_0] Correct usage and implementation for serializable objects without default constructors
by Martin Proulx 16 Sep '05

16 Sep '05

> In this example, we have a class A that doesn't have a default > constructor. > An int is needed by the constructor, which is stored in the i member > variable. load/save_construct_data are used to un/serialize the i member, > while the serialize member is used for all other members. > > Looking at this test, I see a couple of behaviors that puzzle me. > > -) Saving the 'a' instance in the save() function doesn't end up calling > save_construct_data. This leaves a serialized version of A which lacks > the > 'i' member. This makes it impossible to fully restore the 'a' > instance. It > seems problematic to me that save_construct_data isn't called in this > case. > >> I just re-ran test_non_default_ctor. I ran under the VC 7.1 debugger and >> inserted traps inside both save_construct_data and >> load_construct_data. II >> verified that save_construct_data and load_construct_data are being >> invoked >> exactly as they are intended. I see no problem here. > > > In my planned usage, I'd like to fully serialize all members, > regardless if > the objects are serialized directly or through pointers. I cannot see how > to do this without serializing the members needed to reconstruct the > object > in both serialize and save_construct_data, even if some members will > end up > serialized twice when an object is stored through a pointer. > >> If the members are not pointers, the constructor is never called. so the >> parameters set by the constructor are not needed. >> save_load_contruct_data >> is only called when its necessary to create a new object. > > > What's the proper way to serialize all members of a class without a > default > constructor so that it gets fully serialized regardless how the > objects are > managed? > >> Exactly as described in the manual and illustrated by the example >> test_non_default_ctor. > > > -) When restoring the 'a' instance within load(), in order to restore > it, we > first create another 'a' instance (with a different constructor > argument), > then restore the other members within, leaving untouched the 'i' member. > Assuming I'd like to be able to serialize and unserialize completely > objects > that do not have a default constructor, I'm wondering how I can fully > restore an object that doesn't have a default constructor. > >> All you have to do is define save_construct_data and >> load_construct_data for >> all types which don't have a default constructor. The library takes >> care of >> everything else. > > > I've looked for some other mechanism relying on a copy constructor and > something along the lines of load_construct_data, but I haven't found > any. > >> Somehow I'm thinking you're looking for the wrong thing. I wonder if >> you're >> not underestimating what the library does for you. As I said, you, only >> need to define save/load_construct_data for those types which don't >> have a >> default constructor - there is nothing else required to do. >> >> Robert Ramey > > Hello, As this discussion is going, it seems clear that either I'm missing something somewhere or that I'm not being clear enough in exposing my problems... I'll directly include a sample of something similar to what I'd like to achieve that doesn't work. Please take a look at the example, and let me know how you would modify this to make both assert succeed. If you notice that I've missed some concept in the way the library should be used, please enlighten me! Thanks, Martin ------------------------------------------------------------------------ #include <cstdlib> #include <cassert> #include <sstream> #include <boost/archive/text_oarchive.hpp> #include <boost/archive/text_iarchive.hpp> #include <boost/serialization/string.hpp> using namespace std; class Person { public: Person(const string& name) : _name(name), _favoriteFood("none") {} const string& getName() const {return _name;} const string& getFavoriteFood() const {return _favoriteFood;} void setFavoriteFood(const string& favoriteFood) {_favoriteFood = favoriteFood;} private: const string _name; string _favoriteFood; friend class boost::serialization::access; template<class Archive> void serialize(Archive & ar, const unsigned int /* file_version */){ ar & _favoriteFood; } }; namespace boost { namespace serialization { template<class Archive> inline void save_construct_data(Archive & ar, const Person * person, const unsigned int /* file_version */) { ar << person->getName(); } template<class Archive> inline void load_construct_data(Archive & ar, Person * person, const unsigned int /* file_version */) { string name; ar >> name; ::new(person)Person(name); } } // serialization } // namespace boost template<class Archive> void serializePerson(Archive& oa, const Person& someone) { // save_construct_data isn't called when serializing a Person in this fashion. // The person's name will not appear in the archive. oa << someone; } template<class Archive> Person UnserializePerson(Archive& ia) { // I'm constructing a temporary person, with a bogus name, as it's the only workaround I've come up with. // There is no way that unserializing returns an actual object, like I'm needing here. Person someone("bogus name"); // When unserializing in this fashion, load_construct_data isn't called either. ia >> someone; // The initial person's name is then lost. return someone; } void main(void) { Person *const Joe = new Person("Joe"); Person John("John"); stringstream stringStream; boost::archive::text_oarchive oa(stringStream); oa << Joe; serializePerson(oa, John); boost::archive::text_iarchive ia(stringStream); Person* restoredPersonPointer; ia >> restoredPersonPointer; Person restoredPerson(UnserializePerson(ia)); assert(restoredPersonPointer->getName() == Joe->getName()); // works fine. assert(restoredPerson.getName() == John.getName()); // fails. } -- 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.

4 10

Re: [Boost-users] Could the BGL graph algorithms be improvedto automatically work with VertexList = listS graphs?
by Tony Cook 16 Sep '05

16 Sep '05

I retracted this in a subsequent post - it was my problem with a custom vertex property (blush) >From: Daryle Walker <darylew(a)hotmail.com> >Reply-To: boost-users(a)lists.boost.org >To: Boost Users mailing list <boost-users(a)lists.boost.org> >Subject: Re: [Boost-users] Could the BGL graph algorithms be >improvedto automatically work with VertexList = listS graphs? >Date: Thu, 15 Sep 2005 18:05:46 -0400 > >On 9/15/05 7:05 AM, "Tony Cook" <tony__cook(a)hotmail.com> wrote: > > > Can I add that misuse of graph assignment and a graph copy constructor >is > > possible - corruptible shallow copies are the result. These methods >should > > be given private scope to prevent (mis)use or be correctly implemented > > > > G2 = G1 ; // Compiles but NO you must use boost::graph_copy (G1, G2) >instead > >If this is accurate, then it should be fixed. Types with abnormal copying >semantics can't be used in STL containers or similar contexts. > >-- >Daryle Walker >Mac, Internet, and Video Game Junkie >darylew AT hotmail DOT com > >_______________________________________________ >Boost-users mailing list >Boost-users(a)lists.boost.org >http://lists.boost.org/mailman/listinfo.cgi/boost-users

1 0

How can I find all the shortest path in a graph?
by Giulio Veronesi 16 Sep '05

16 Sep '05

Hi all, Please excuse me if I post my question again, but I've spent all the night and the day before looking for a solution of the following problem: How to find *all* the possible shortest paths from a source vertex to a target vertex in a directed graph? I tried using depth_first_search and acting on visitors without any success. Please, could you help me? Thanks a lot in advance, Giulio

1 0

How to extending algorithms with visitors
by Giulio Veronesi 15 Sep '05

15 Sep '05

Hi all, I'm enjoying learning the boost graph library. I'm trying to use the Dijkstra algorithm and try to store the shortest path as explained in the subsection "Extending Algorithms with Visitors" of the section "Quick Tour" of the BGL user guide. When I try to compile my code, I get the following error message: mesh.cpp:38: error: expected constructor, destructor, or type conversion before '<' token mesh.cpp:38: error: expected `;' before '<' token where line 38 is highlighted in the following portion of code. Could you help me to resolve this problem? Thanks in advance, Giulio template <class PredecessorMap> class record_predecessors : public dijkstra_visitor<> { public: record_predecessors(PredecessorMap p) : m_predecessor(p) { } template <class Edge, class Graph> void edge_relaxed(Edge e, Graph& g) { // set the parent of the target(e) to source(e) put(m_predecessor, target(e, g), source(e, g)); } protected: PredecessorMap m_predecessor; }; template <class PredecessorMap> line 38: record_predecessors<PredecessorMap> make_predecessor_recorder(PredecessorMap p) { return record_predecessors<PredecessorMap>(p); } ___________________________________ Yahoo! Mail: gratis 1GB per i messaggi e allegati da 10MB http://mail.yahoo.it

3 4

Matrix of submatricies...
by Edward Grace 15 Sep '05

15 Sep '05

Dear all, [you may need a fixed with font] Consider the following 4x4 matrix which is a 2x2 matrix of submatricies. A B | 0 0 C D | 0 0 ----+---- 0 0 | a b 0 0 | c d Clearly matrix operations such as products do not need to involve the off diagonal (zero) sub matricies. Is there a matrix type that "knows" about this type of matrix so that when prod() is carried out it does not do unnecessary operations with the zero elements? -ed

2 1