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

How to test whether a vertex or edge exists?
by sean yang 08 May '06

08 May '06

I want to add a vertex, which a string as its ID to a graph if a vertex representing such a string does not exist in the graph. Is there a function call to test if a vertex exists in a graph? ----------------------------------------------------------------------- //Here is the simpilfied situation that I want to handle, "IF THERE IS NOT a vertex representing the //string of the current line" is the predicate I want to know typedef adjacency_list<vecS, vecS, directedS, property<vertex_color_t, default_color_type>, property<edge_weight_t, int> > Graph; Graph g(); ifstream infile; infile.open(argv[1]); string line; while( getline(infile, line) ){ if(line.find("Node")!= npos && /*IF THERE IS NOT a vertex representing the string of the current line*/) add_vertex( line, g); } -------------------------------------------------------------------- A related question I want to ask is whether there exist a function call that test whether an edge representing [vertext string("Node1") --> vertext string("Node2") ] exists in a graph. Thanks a lot, Sean _________________________________________________________________ Express yourself instantly with MSN Messenger! Download today - it's FREE! http://messenger.msn.click-url.com/go/onm00200471ave/direct/01/

2 3

A Problem with boost::bind
by Hossein Haeri 07 May '06

07 May '06

Dear all, A fragment of code of mine is like this: template <class Container, size_t i> struct print { ostream& operator () (const Container& c, ostream& out) const { if(out) { typedef typename Container::value_type value_type; typedef print<value_type, i - 1> NewPrint; NewPrint newPrint; for(typename Container::const_iterator j = c.begin(); j != c.end(); ++j) newPrint(*j, out); /*for_each(c.begin(), c.end(), bind(newPrint, _2, out)); //Error!*/ } return out; } }; AFAICS, there should be no harm in replacing that for with the for_each in the comments -- the one is marked with "//Error" I mean, except that "out" which is of type ostream& is not Copy-Constructible, and therefore _2 cannot be used against it. Anybody having a workarounds for that? Doesn't Boost have anything analog to boost::ref which can give me a Copy-Constructible beast? For your reference, you can find the whole program and the compiler error message in the P.S. TIA, --Hossein P.S. #include <iostream> #include <algorithm> #include <iterator> #include <vector> #include <boost/bind.hpp> #include <boost/mem_fn.hpp> using std::ostream; using std::cin; using std::cout; using std::copy; using std::for_each; using std::ostream_iterator; using std::vector; using boost::bind; using boost::mem_fn; template <class Container, size_t i> struct print { ostream& operator () (const Container& c, ostream& out) const { if(out) { typedef typename Container::value_type value_type; typedef print<value_type, i - 1> NewPrint; NewPrint newPrint; /* for(typename Container::const_iterator j = c.begin(); j != c.end(); ++j) newPrint(*j, out); */ for_each(c.begin(), c.end(), bind(newPrint, _2, out)); //Error! } return out; } }; template <class Container> struct print<Container, 1> { ostream& operator () (const Container& c, ostream& out) const { if(out) copy(c.begin(), c.end(), ostream_iterator<typename Container::value_type>(out, " ")); return out; } ostream& DoIt (const Container& c, ostream& out) const { if(out) copy(c.begin(), c.end(), ostream_iterator<typename Container::value_type>(out, " ")); return out; } }; int main() { int a1[] = {1, 2, 3, 4}; const size_t n(sizeof(a1)/sizeof(*a1)); vector<int> v(a1, a1 + n); print<vector<int>, 1> () (v, cout); int a2[n] = {5, 6, 7, 8}; vector<vector<int> > m; m.push_back(v); m.push_back(vector<int>(a2, a2 + n)); print<vector<vector<int> >, 2> () (m, cout); cin.get(); return 0; } Compiler: Default compiler Executing g++.exe... g++.exe "E:\Print.cpp" -o "E:\Print.exe" -I"C:\Dev-Cpp\include\c++" -I"C:\Dev-Cpp\include\c++\mingw32" -I"C:\Dev-Cpp\include\c++\backward" -I"C:\Dev-Cpp\include" -L"C:\Dev-Cpp\lib" C:/Dev-Cpp/include/c++/3.3.1/bits/ios_base.h: In copy constructor ` std::basic_ios<char, std::char_traits<char> >::basic_ios(const std::basic_ios<char, std::char_traits<char> >&)': E:/Print.cpp:33: instantiated from `std::ostream& print<Container, i>::operator()(const Container&, std::ostream&) const [with Container = std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > >, unsigned int i = 2]' E:/Print.cpp:72: instantiated from here C:/Dev-Cpp/include/c++/3.3.1/bits/ios_base.h:668: error: ` std::ios_base::ios_base(const std::ios_base&)' is private E:/Print.cpp:33: error: within this context E:/Print.cpp: In member function `std::ostream& print<Container, i>::operator()(const Container&, std::ostream&) const [with Container = std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > >, unsigned int i = 2]': E:/Print.cpp:72: instantiated from here E:/Print.cpp:33: error: initializing argument 3 of ` boost::_bi::bind_t<boost::_bi::unspecified, F, typename boost::_bi::list_av_2<A1, A2>::type> boost::bind(F, A1, A2) [with F = print<std::vector<int, std::allocator<int> >, 1>, A1 = boost::arg<2>, A2 = std::basic_ostream<char, std::char_traits<char> >]' C:/Dev-Cpp/include/boost/bind.hpp: At global scope: C:/Dev-Cpp/include/boost/bind.hpp: In instantiation of `boost::_bi::result_traits<boost::_bi::unspecified, print<std::vector<int, std::allocator<int> >, 1> >': C:/Dev-Cpp/include/boost/bind/bind_template.hpp:16: instantiated from `boost::_bi::bind_t<boost::_bi::unspecified, print<std::vector<int, std::allocator<int> >, 1>, boost::_bi::list2<boost::arg<2>, boost::_bi::value<std::basic_ostream<char, std::char_traits<char> > > > >' E:/Print.cpp:33: instantiated from `std::ostream& print<Container, i>::operator()(const Container&, std::ostream&) const [with Container = std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > >, unsigned int i = 2]' E:/Print.cpp:72: instantiated from here C:/Dev-Cpp/include/boost/bind.hpp:62: error: no type named `result_type' in ` struct print<std::vector<int, std::allocator<int> >, 1>' C:/Dev-Cpp/include/boost/bind/bind_template.hpp: In instantiation of `boost::_bi::bind_t<boost::_bi::unspecified, print<std::vector<int, std::allocator<int> >, 1>, boost::_bi::list2<boost::arg<2>, boost::_bi::value<std::basic_ostream<char, std::char_traits<char> > > > >': E:/Print.cpp:33: instantiated from `std::ostream& print<Container, i>::operator()(const Container&, std::ostream&) const [with Container = std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > >, unsigned int i = 2]' E:/Print.cpp:72: instantiated from here C:/Dev-Cpp/include/boost/bind/bind_template.hpp:16: error: no type named `type' in `struct boost::_bi::result_traits<boost::_bi::unspecified, print<std::vector<int, std::allocator<int> >, 1> >' C:/Dev-Cpp/include/boost/bind/bind_template.hpp:19: error: no type named `type' in `struct boost::_bi::result_traits<boost::_bi::unspecified, print<std::vector<int, std::allocator<int> >, 1> >' C:/Dev-Cpp/include/boost/bind/bind_template.hpp:25: error: no type named `type' in `struct boost::_bi::result_traits<boost::_bi::unspecified, print<std::vector<int, std::allocator<int> >, 1> >' C:/Dev-Cpp/include/boost/bind/bind_template.hpp:31: error: no type named `type' in `struct boost::_bi::result_traits<boost::_bi::unspecified, print<std::vector<int, std::allocator<int> >, 1> >' C:/Dev-Cpp/include/boost/bind/bind_template.hpp:31: confused by earlier errors, bailing out Execution terminated ___________________________________________________________ Switch an email account to Yahoo! Mail, you could win FIFA World Cup tickets. http://uk.mail.yahoo.com

4 10

Re: [Boost-users] [MULTI_INDEX] intersection algorithm?
by JOAQUIN LOPEZ MU?Z 07 May '06

07 May '06

Guillaume Lazzara ha escrito: > Hello, > > I am currently using multi_index as "set" container > and I wanted to know how to use intersection algorithm. > I tried with the STL interction algorithm but it > crashed. How can I do? Hello Guillaume. In principle, there's nothing preventing multi_index_container's from working with set_intersection. Could you provide a case where the referred to crash shows? Failing that, a little more detailed explanation or some code? Thank you, Joaquín M López Muñoz Telefónica, Investigación y Desarrollo

2 1

[SOC] Applicants -- Please Monitor Google for Comments
by Jeff Garland 07 May '06

07 May '06

Hi All - First let me say that we've had a tremendous response thus far to SOC. Some really excellent applications and ideas. I have high hopes that some very exciting Boost projects will come out of SOC. The reason I'm sending this is that I'm trying to reach out to applicants that may not be aware that proposal feedback is being provided on the SOC website. Please check your proposal for comments. Many of the proposals need additional details. There is no automated email when we add comments to a proposal, so you won't be notified. Goggle is looking into adding this, but it isn't there now. There are enough comments and proposals that it would be impractical for us to ensure that everyone got notified when a comment is added. Thanks, Jeff

1 0

Re: [Boost-users] [shmem] New bugfix version in Boost Vault andsandbox cvs
by JOAQUIN LOPEZ MU?Z 06 May '06

06 May '06

----- Mensaje original ----- De: Ion Gaztañaga <igaztanaga(a)gmail.com> Fecha: Sábado, Mayo 6, 2006 9:51 pm Asunto: Re: [Boost-users] [shmem] New bugfix version in Boost Vault andsandbox cvs > > Or, depending on > > how shmem fits into the picture, should B.MI take the lead in > > supporting shmem functionality internally? Y'all have more > > flexibility in the B.MI case as it isn't part of the standard. > > To be able to support Multi-index in shared memory we would need > to > rewrite it to replace all raw pointers with allocator::pointer > typedefs. > I haven't looked through multiindex code but this can be a big > task. > There is nothing that shmem can do to support multiindex if it > uses raw > pointers. But I think that multiindex and shmem can be a good base > for > in-memory data-bases. > I wholeheartedly agree with you shmem and multi_index should be able to interoperate nicely. My other activities in B.MI, and my rather shallow knowleddge of shmem, prevent me from attacking this task right away, but I'd be happy if some bold Booster could do some analysis/prototype of the changes involved in B.MI for it to work with shmem, so that eventually I can integrate those changes. If someone is up to the task, do count on my support/assitance for matters concerning the inner structure of B.MI. Best regards, Joaquín M López Muñoz Telefónica, Investigación y Desarrollo

1 0

[serialization] problems with using wide-char archives
by Hilal Shaath 06 May '06

06 May '06

Hello All: The serialization library is one of the best libraries I have used. I used to to serialize a number of files with various sizes, and it works like a charm. However, when I am using the wide-char archives, I get a linking error. Here are the problem specifications: When including : #include "boost/archive/binary_woarchive.hpp" #include "boost/archive/binary_wiarchive.hpp" Or #include "boost/archive/text_woarchive.hpp" #include "boost/archive/text_wiarchive.hpp" And attempt to use them (i.e.) std::map<wstring,size_t> htable; wstring root = L"c:"; findDFF(&htable,&root); std::wofstream ofs("someFile",std::wios::binary); boost::archive::binary_woarchive o(ofs); I get the following linking errors: [ DB3 error LNK2019: unresolved external symbol "public: __thiscall boost::archive::basic_binary_oprimitive<class boost::archive::binary_woarchive,class std::basic_ostream<unsigned short,struct std::char_traits<unsigned short> > >::~basic_binary_oprimitive<class boost::archive::binary_woarchive,class std::basic_ostream<unsigned short,struct std::char_traits<unsigned short> > >(void)" (??1?$basic_binary_oprimitive@Vbinary_woarchive@archive@boost@@V?$basic_ostream@GU?$char_traits@G@std@@@std@@@archive@boost@@QAE@XZ) referenced in function "public: __thiscall boost::archive::binary_woarchive_impl<class boost::archive::binary_woarchive>::~binary_woarchive_impl<class boost::archive::binary_woarchive>(void)" (??1?$ ] If I use the regular archives (binary_oarchive) I don't get any errors, and it runs as a charm! The compiler I am using is VC++ version 7.1/ I would be grateful if some could point me to the reason for this error. Thanks for your help Hilal

1 0

[multi_index] const mem_fun serialization bug.
by Julien Pervillé 06 May '06

06 May '06

Hello boost-users. I am writing to report an annoying serialization bug encountered while developing a project with Boost.multi_index, which is a wonderfully useful data structure. Thank you Joaquín! First a fast overview of my project: I am developing a virtual file system for my internship. In this file system, I have to store user paths which I call "entries". "entries" are associated with another "internal entry" which is the path to the physical target inside the file system. "entries" are also contained in a concept of "directory". To ease up things I store entries in a boost::multi_index with at least 3 indexes: - an unique index to look up user entries. - a non-unique index to do reverse look up (by internal targets). - a non-unique index to do directory listings. The latter is the one that interests us. The "entry" class splits the entry into the "dirname" and "file" parts. A getter function returns a const-reference to "dirname", let's call it "entry::dirname()". To do directory listings efficiently, I define an ordered-non-unique index pointinh to the const-reference returned by the entry.dirname() thanks to a wrapper "mem_fun" named getdirname(). Now comes the bug. To test my file system, I import some existing directories into my file system. When I unload it, I expect that the internal boost::multi_index is serialized and restored properly when I reload the file system program. When working on huge batches of small files, like untaring a linux kernel or copying the thousands of files from /usr/share/doc, I noticed that the import works but reloading the serialized mappings fails with a (for now unexplained but reproducable) boost::serialization::other_exception. After hunting through the headers, I located the triggered exception to line 1080 of boost/multi_index/ordered_index.hpp (line number from boost 1.33) Here is the context from the "rearranger" method where the exception is thrown: > 1080 if(position!=x){ > 1081 /* check the rearrangement is consistent */ > 1082 if(!in_place(x->value,position,Category())){ > 1083 throw_exception( > 1084 archive::archive_exception( > 1085 archive::archive_exception::other_exception)); > 1086 } Since my multi_index works perfectly until I save, I checked that my data is properly serialized. Since I saw no obvious errors, I modified the header to swallow the exception and see what happens. > 1080 if(position!=x){ > 1081 /* check the rearrangement is consistent */ > 1082 if(!in_place(x->value,position,Category())){ > 1083 return; throw_exception( > 1084 archive::archive_exception( > 1085 archive::archive_exception::other_exception)); > 1086 } After this small hack, everything "seems" to work fine but if I do a "find" on my file system some entries appear "missing". They are actually not missing but they were attributed to the wrong directory! And in the wrong parent directory, a lookup says "file not found" when find tries to access it. However, I can still access the entries by naming them explicitely (using the main index, not the dirname one). I investigated and found out that the "dirname" ordered_index (const mem_fun) is not restored properly, even through it is saved correctly. The "entry" and the "target" ordered indexes (member) are restored as intended. However look what happens to the mem_fun "dirname" index: its values are restored in positions that are not a valid binary tree. Actually it is "almost" a binary tree, just some values are wrongly restored. Like a dozen out of 1000 entries, but always the same ones. As a consequence even if my entry::operator<() predicate is proved correct, lookups through the "dirname" index give byzantine results. I tracked down the problem and found a small set of "entries" that are not restored properly and wrote a small example file. Please have a look at the attached source "seri-bug.cpp". The example dumps the contents of a 5 entries multi_index, first by entry and then by "dirname". The displaying is done before serializing to disk and after reloading the mappings. The corruption can then be see by checking the different position inside the dirname index for the "/doc/binutils-doc" entry before and after. Sample run: Original structure dump by dirname, pre serialization. > entry `/' with dirname `'. > entry `/doc' with dirname `'. > entry `/doc/binutils-doc' with dirname `/doc'. > entry `/doc/binutils-doc/ld' with dirname `/doc/binutils-doc'. > entry `/doc/binutils-doc/gas' with dirname `/doc/binutils-doc'. Post serialized loading dump. Notice that the "/doc/binutils-doc" entry was not restored at the correct position. Since the dirnames are not properly sorted in memory, doing a find() by dirname obtains byzantine results (doing a find of "/doc" dirname returns the `/doc/binutils-doc/ld' result instead of the expected `/doc/binutils-doc' entry). > entry `/' with dirname `'. > entry `/doc' with dirname `'. > entry `/doc/binutils-doc/ld' with dirname `/doc/binutils-doc'. > entry `/doc/binutils-doc' with dirname `/doc'. > entry `/doc/binutils-doc/gas' with dirname `/doc/binutils-doc'. Even if this sample triggers the restore anomaly, to see a boost::archive::other_exception one needs more data inside the multi_index, like a few thousand entries. I would really love to see a this bug fixed since it stalls my projects. My c++ template metaprogramming skills aren't very sharp but I think that this bug is a good opportunity to learn some about this subject. I am looking forward to test patches and offer my help testing, so that this little quirk gets solved. Sincerely, Julien Perville Intern, Global Core, Amadeus IT Group.

1 0

adjacency_list and UndirectedGraph in BGL
by sean yang 06 May '06

06 May '06

I am a newbie using BGL and only read a couple of example source code. I have a question about class representing a graph. It seems adjacency_list represent a graph, but it seems there is a class hierarchy (as shown in (2) ) to represent a graph. What is their relationship? (1) adjacency_list can represent a graph, e.g., typedef adjacency_list<vecS, vecS, bidirectionalS, no_property, property<edge_weight_t, float> > Graph; (2) And the online manual give a list of Graph representation. I guess it's a hierarchical class representation. i.e., Graph <--Incidence Graph <--Bidirectional Graph. Am I right? But if so, I did not find the constructor of these classes. Furthermore, this class hierarchy has give a full classification of graph, why is there a adjacency_list representation? Chapter 11. The Boost Graph Interface 1. Graph 2. Incidence Graph 3. Bidirectional Graph 4. Adjacency Graph 5. Vertex List Graph 6. Edge List Graph 7. Vertex and Edge List Graph 8. Mutable Graph 9. Property Graph 10. Mutable Property Graph (3) There is an exmple of UndirectedGraph in the book of "User guide and reference manual" { ... V=3; UndirectedGraph undigraph(V); add_edge(0, undigraph); ..... } is there a way not specifying vertice number when defining an object and dynamically adding vertex when according to user input? i.e, something like UndirectedGraph undigraph( ); while (getline(in, line)){ add_edge(line, undigraph); } _________________________________________________________________ Express yourself instantly with MSN Messenger! Download today - it's FREE! http://messenger.msn.click-url.com/go/onm00200471ave/direct/01/

1 0

[MULTI_INDEX] intersection algorithm?
by Guillaume Lazzara 06 May '06

06 May '06

Hello, I am currently using multi_index as "set" container and I wanted to know how to use intersection algorithm. I tried with the STL interction algorithm but it crashed. How can I do? Thanks in advance, -- Guillaume Lazzara Epita Promo 2008 http://guillaume.lazzara.fr

1 0

Re: [Boost-users] boost::multi_index_container different search key type
by JOAQUIN LOPEZ MU?Z 06 May '06

06 May '06

----- Mensaje original ----- De: bert hubert <bert.hubert(a)netherlabs.nl> Fecha: Miércoles, Mayo 3, 2006 8:15 pm Asunto: [Boost-users] boost::multi_index_container different search key type > Joaquin, list, > > In one of the last issues of the C/C++ User's Journal, Andrei > Alexandrescu described the need for something better than std::map > when using expensive > keys: > [...] > > More on http://www.ddj.com/dept/cpp/184402065 - might this be > something boost::multi_index_container could be made to do? > Hello Bert, I'm glad you asked, because multi_index_container already provides this, and I would dare say in a more powerful fashion. Ordered and hashed indices lookup member functions (find, equal_range, etc.) are overloaded to accept *compatible keys*, which can be used to pass alternate representations of keys in exactly the same manner as described in Andrei's article. Compatible keys are introduced at http://tinyurl.com/rouet and formally described at http://tinyurl.com/hp9j4 (ordered indices) http://tinyurl.com/ze5od (hashed indices) But there is more: in the case of ordered indices, compatible keys need not be in a 1-to-1 relation with the original keys, but can be "coarser", in a sense. An example can help clarify this: Suppose we've got an index ordered by a date, with millisecond precision, then the index is certainly ordered by year; compatible key support can be thus used to perform lookup by year if only we provide the appropriate comparison semantics between full dates and years, so that "year" is a compatible key of "date". Although it might not be apparent, composite keys take full advantage of all of this: * When you pass a tuple to lookup on some composite_key- enabled index, the tuple is *not* the index key_type, but merely a more convenient representation. * Compatible key support (in the "coarser key" sense) is used when you do "partial searches" in which only the first tuple values are specified: see http://tinyurl.com/hdf3q. When Andrei's article first came out, I contacted him to discuss these concepts and the similarities between his ÜberContainers and compatible key support as provided by B.MI: IMHO it is not unusual that these sort of ideas come up recurrently. Thanks for your active interest in Boost.MultiIndex! Joaquín M López Muñoz Telefónica, Investigación y Desarrollo

2 1