- Boost-users - lists.boost.org

Re: [Boost-users] [graph] BFS and dedicated color map
by Dmitry 05 Feb '07

05 Feb '07

"Jens Muller" <jens.mueller(a)ira.uka.de> wrote in message news:<eq58j2$v4m$1(a)sea.gmane.org>... > > Jens, > > I think that you are missing something. As for me, the property_traits class > > is just a way of uniform data manipulation. > > If every pm needed to be a class, there would be no need for the > *_traits template classes. > > http://www.boost.org/libs/graph/doc/leda_conversion.html > > The Adaptor pattern [12] typically requires that the adaptee object be > contained inside a new class that provides the desired interface. This > containment is not required when wrapping a graph for BGL because the > BGL graph interface consists solely of free (global) functions. Instead > of creating a new graph class, you need to overload all the free > functions required by the interface. We call this free function wrapper > approach external adaptation > > ... > > All types associated with a BGL graph class are accessed though the > graph_traits class. We can partially specialize this traits class for > the LEDA GRAPH class in the following way. > > > The same is done here for vectors and the like. > Unfortunately I can't follow this :-( > > Your class has to be a model of > > this abstract concept. (To be a Read Property Map it is enough to have 3 > > typedefs and get() function, see Concept Checking Class in the documentation > > that you referred). > > Yes, it says the get() free function and 3 typedefs in property_traits > need to be defined. > > Anyway, it works now, see attachments. The changes in "bfs_map_test.cpp" are exactly I was thinking of) > One question remains, though: > > template<typename Graph, typename ReadablePropertyMap, typename ColorValue> > ColorValue MapAsColorMap<Graph, ReadablePropertyMap, > ColorValue>::get(key_type key) > { > return (boost::get(pm_, key)==white_) ? > boost::color_traits<ColorValue>::white() > : > boost::color_traits<ColorValue>::black(); > } > > > works, while get(pm_, key) without boost:: doesn't. > > Shouldn't the right get function be found by Koenig lookup? Probably yes, but AFAIK not all compilers have it implemented. > http://www.boost.org/libs/property_map/ReadablePropertyMap.html says, > too, that get is required, not boost::get ... I think this is because ReadablePropertyMapConcept class already defined in boost:: namespace. Regards, --Dmitry.

1 0

Re: [Boost-users] [graph] BFS and dedicated color map
by Dmitry 04 Feb '07

04 Feb '07

"Jens Muller" <jens.mueller(a)ira.uka.de> wrote in message news:<eq4poi$go9$1(a)sea.gmane.org>... > Dmitry schrieb: > > Jens, the ReadablePropertyMap parameter has to be a class with the following > > typedef at least: > > > > typedef value_type some_type; > > > > > Why? > > http://www.boost.org/libs/property_map/ReadablePropertyMap.html says: > > Associated Types > Value Type boost::property_traits<PMap>::value_type The type of the > property. > > That's what these traits classes are for: external adaption. > > You replied to the fixed version where I use property_traits. Jens, I think that you are missing something. As for me, the property_traits class is just a way of uniform data manipulation. Your class has to be a model of this abstract concept. (To be a Read Property Map it is enough to have 3 typedefs and get() function, see Concept Checking Class in the documentation that you referred). --Dmitry

2 1

Re: [Boost-users] [BGL] Max (min) cycle ratio
by Dmitry 04 Feb '07

04 Feb '07

Doug, It's there (in the Algorithm/graph directory). Pleas take a look. WBR --Dmitry > Hello, > > On Fri, 2006-12-08 at 18:33 +0100, Dmitry wrote: > > For a some time I've been using my own implementation for calculating of the > > minimum cycle ratio of the directed multigraph, it based on the approach > > described in the paper > > "Numerical Computation of Spectral Elements in MAX-PLUS algebra" and seems > > has complexity close to linear in the respect of the edges number (both in > > memory and time). > > > > Does current BGL has some solutions for cycle ratio problem? > > We do not have any algorithm implementations for this problem in the > BGL. > > > I would like to > > try to contribute my "perfect" implementation to BGL if it's possible. What > > is need to be done for it? > > Great! The major components of an algorithm submission to the BGL are: > > - The algorithm implementation itself: please be sure to follow the > general coding style of the BGL > - Documentation: Should be written in HTML, with the same format and > style as existing BGL algorithms. > - Tests: Please provide a standalone testcase that builds a few sample > graphs, runs the algorithm, and checks the results. I strongly suggest > using adjacency_list<listS, listS, ...> for the graph type, because that > tends to find many common mistakes in BGL algorithms. > - Examples: Please provide at least one example file that illustrates > how to use your algorithm. This example is typically part of the > documentation. > > When you're ready to submit your algorithm implementation, please upload > it to the Boost file vault at http://www.boost-consulting.com/vault/ and > send a message to the Boost list to tell us that it's there. We'll give > the code an informal review and, once everything's in good shape, > integrate it into Boost CVS for an upcoming Boost release. > > We're looking forward to including your algorithm implementation in the > BGL! > > Cheers, > Doug

1 0

[graph] BFS and dedicated color map
by Jens Müller 04 Feb '07

04 Feb '07

The BGL implementation of breadth-first search uses a dedicated color map. I had the following idea: Some algorithms don't need to distinguish black/gray, but have an unused value in e.g. a distance map, e.g. -1, to which the map can be initialised. So I tried to write a map adapter which can be passed such a map together with the value indicating "white". This adapter will return white whenever the value in the underlying map equals this value, black otherwise. Unfortunately, my C++ seems to be too bad to implement this ... Please see the attached source files ... The errors I'm currently getting: In file included from bfs_map_test.cpp:14: bfs_distmap_as_color_map.hpp:42: error: ISO C++ forbids declaration of `graph_traits' with no type bfs_distmap_as_color_map.hpp:42: error: expected `;' before '<' token bfs_distmap_as_color_map.hpp:47: error: `key_type' has not been declared bfs_distmap_as_color_map.hpp:47: error: ISO C++ forbids declaration of `key' with no type bfs_distmap_as_color_map.hpp:62: error: `ColorValue MapAsColorMap<Graph, ReadablePropertyMap, ColorValue>::get' is not a static member of `class MapAsColorMap<Graph, ReadablePropertyMap, ColorValue>' bfs_distmap_as_color_map.hpp:62: error: template definition of non-template `ColorValue MapAsColorMap<Graph, ReadablePropertyMap, ColorValue>::get' bfs_distmap_as_color_map.hpp:62: error: `key_type' was not declared in this scope bfs_distmap_as_color_map.hpp:63: error: expected `;' before '{' token bfs_distmap_as_color_map.hpp:70: error: `key_type' has not been declared bfs_distmap_as_color_map.hpp:71: error: ISO C++ forbids declaration of `key' with no type bfs_distmap_as_color_map.hpp: In instantiation of `MapAsColorMap<main(int, char**)::Graph, size_t[], int>': bfs_map_test.cpp:58: instantiated from here bfs_distmap_as_color_map.hpp:49: error: `size_t[]' is not a class, struct, or union type bfs_distmap_as_color_map.hpp:58: error: `size_t[]' is not a class, struct, or union type bfs_map_test.cpp: In function `int main(int, char**)': bfs_map_test.cpp:58: error: no matching function for call to `MapAsColorMap<main(int, char**)::Graph, size_t[], int>::MapAsColorMap(size_t[5], int)' bfs_distmap_as_color_map.hpp:40: note: candidates are: MapAsColorMap<main(int, char**)::Graph, size_t[], int>::MapAsColorMap(const MapAsColorMap<main(int, char**)::Graph, size_t[], int>&) bfs_map_test.cpp:71: error: `copy_graph' undeclared (first use this function) bfs_map_test.cpp:71: error: (Each undeclared identifier is reported only once for each function it appears in.) bfs_map_test.cpp:88: error: `print_parent' undeclared (first use this function) bfs_map_test.cpp:88: error: expected primary-expression before '>' token bfs_map_test.cpp:91: error: expected `}' at end of input g++34 -c -o bfs_map_test.o -g -Wall -Wno-deprecated -pipe -O -I. -I/home/jmueller/software-gcc34/boost/include/boost-1_33_1 -I/sw/linux/LEDA/LEDA-5.0.1/include -I/sw/linux/LEDA/LEDA-5.0.1/incl -I/sw/linux/LEDA/LEDA-5.0.1/incl_old bfs_map_test.cpp Could someone point out the most stupid bugs? Thanks a lot in advance ...

2 7

array sink of unknown size
by grahamspam＠earthlink.net 04 Feb '07

04 Feb '07

Hello, I need a filtering_ostream that efficiently yields a char* and it's size (i.e., it allocates the memory it needs). I have no way of knowing or predicting the number of chars resulting from uncompressing the input (?). For efficiency it would be nice to specify an estimate and a "chunking" size, but the filtering_ostream would actually allocate all that is needed. I looked at this: boost::iostreams::stream< boost::iostreams::array_sink > but it seems to need a terminating char* or a size in its ctor. What is recommended? Thanks!

1 0

Re: [Boost-users] [Filesystem] Folders with spaces in the name
by Nat Goodspeed 04 Feb '07

04 Feb '07

________________________________________ From: boost-users-bounces(a)lists.boost.org [mailto:boost-users-bounces@lists.boost.org] On Behalf Of Nathan Pierluissi Sent: Saturday, February 03, 2007 5:53 PM To: boost-users(a)lists.boost.org Subject: [Boost-users] [Filesystem] Folders with spaces in the name I am having trouble using the /= operator to open folders with spaces in the name, ex. "My Documents" or "Program Files". Here is an example code: path full_path("c:\"); string Fname="Program Files"; full_path/=Fname; It works for any Fname (folder name) that doesn't have a space. Let me know if you need more information. Thanks in advance. [Nat] You didn't explain the nature of your 'trouble,' but if you're encountering exceptions, it's probably the default boost::filesystem::path syntax checker. Try explicitly disabling that rather than letting operator/= implicitly convert your string to boost::filesystem::path with the default checker, e.g. (neither compiled nor tested): full_path /= path(Fname, no_check);

2 1

Re: [Boost-users] boost::serialization throws random exceptions
by Nat Goodspeed 03 Feb '07

03 Feb '07

> -----Original Message----- > From: boost-users-bounces(a)lists.boost.org [mailto:boost-users- > bounces(a)lists.boost.org] On Behalf Of Adrian Grigore > Sent: Saturday, February 03, 2007 9:11 AM > To: boost-users(a)lists.boost.org > Subject: Re: [Boost-users] boost::serialization throws random exceptions > > Robert Ramey wrote the following on 2/3/2007 1:30 AM: > > a) catch the archive exceptions and display an error message which > > describes what kind of exception has been thrown. > > I did something similar, but it is still a poor workaround. I save data > incrementally and rotate savefile names to make sure the player does not > lose all data, but just the changes since the last increment. Still, > losing all game progress since the last savefile increment is a major > turnoff for most players. [Nat] I think he was suggesting that you do that as a diagnostic measure to help discover and solve the problem you're encountering. I don't think he meant for you merely to put in the catch code and release the program. > > c) Just a while guess - thrown from load binary might suggest > > either the file isn't being opened binary, or the size of data > > being read isn't the same as what's being saved. > > I doubt that since there is only one save and one load routine in my > application. If I opened the file as text when saving and as binary when > loading this would always fail. But in my case everything is working > fine most of the time. [Nat] But you COULD be having troubles even if you open the file as text both for save and for load. In fact, the magic value 26 is a strong hint that this may be the trouble. A byte containing binary 26 may, in text mode, be interpreted as the character ctrl-Z -- which was the traditional MS-DOS EOF marker. Please try Robert's suggestion: ensure that you're opening the file using the binary flag both for saving and for loading the file.

2 1

[Filesystem] Folders with spaces in the name
by Nathan Pierluissi 03 Feb '07

03 Feb '07

Greetings: I am having trouble using the /= operator to open folders with spaces in the name, ex. "My Documents" or "Program Files". Here is an example code: path full_path("c:\"); string Fname="Program Files"; full_path/=Fname; It works for any Fname (folder name) that doesn't have a space. Let me know if you need more information. Thanks in advance. -N. Pierluissi --------------------------------- Want to start your own business? Learn how on Yahoo! Small Business.

1 0

Boost.MultiIndex iterator types
by Jonathan Wang 03 Feb '07

03 Feb '07

I have two multi_index_containers that are identical except for the ordering of the iterators. For example: struct Foo { long x, y; }; typedef boost::multi_index_container<Foo, indexed_by<ordered_non_unique<composite_key<Foo, member<Foo, long, &Foo::x>, member<Foo, long, &Foo::y> > > > > FooAscending; typedef boost::multi_index_container<Foo, indexed_by<ordered_non_unique<composite_key<Foo, member<Foo, long, &Foo::x>, member<Foo, long, &Foo::y> >, composite_key_compare<std::greater<long>, std::greater<long> > > > > FooDescending; The containers are indexed on composite keys of x and y - one in ascending order of y, the other in descending order. I have code that operates on iterators over these containers. Conveniently, the operation is identical, save for the ordering, so I can reuse the interesting code that works on these iterators. However, I am finding that the iterator types for the two containers are identical. Yet if I just define my overload for one of the iterators, everything works as expected. So my question is, is there a way to specify a generic iterator over a multi_index_container such that code on iterators can be reused in this way? It seems from the symbols gcc spits out that the iterator type depends only on the type held and the number of indices in the container (i.e. a container with a unique key on just Foo::x would also have its iterator type collide with FooAscending::iterator and FooDescending::iterator). Thanks, Jonathan

2 1

Serialization of dynamic data
by Anders Sundman 03 Feb '07

03 Feb '07

Hi! About the boost::serialization library, what is the best way to handle dynamic data in classes? Any idéas, suggestions or caveats? I didn't manage to find anything about this in the docs. Consider the following sample class: struct Dyn { Dyn(int s) : data(0), size(s) { data = new char[size]; } ~Dyn() { delete data; } char* data; int size; private: friend class boost::serialization::access; template< class Archive > void serialize( Archive &ar, unsigned int ver ) { // -> ar & data; What to do here? ar & size; } }; What to do with the data pointer? Is there any way to determine (in the serialize function) if a serialization or "de-serialization" is taking place? And have different behaviours - either allocating a new char[x] or copying data to the archive? Is there any way to store dynamic data in an archive? Best regards, Anders Sundman

4 9