[graph] BFS and dedicated color map
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 ...
Jens Müller schrieb:
Unfortunately, my C++ seems to be too bad to implement this ...
Please see the attached source files ...
The errors I'm currently getting:
OK, fixed some missing boost::, and used size_t* instead of size_t[] as the template parameter for the pmap type. Still get errors: bfs_map_test.cpp: In function `int main(int, char**)': bfs_map_test.cpp:69: 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_distmap_as_color_map.hpp:48: note: MapAsColorMap<Graph, ReadablePropertyMap, ColorValue>::MapAsColorMap(ReadablePropertyMap&, typename boost::property_traits<IndexMap>::value_type) [with Graph = main(int, char**)::Graph, ReadablePropertyMap = size_t*, ColorValue = int] Can someone please help me?
Jens Müller schrieb:
Jens Müller schrieb:
Unfortunately, my C++ seems to be too bad to implement this ...
Please see the attached source files ...
The errors I'm currently getting:
OK, fixed some missing boost::, and used size_t* instead of size_t[] as the template parameter for the pmap type.
Still get errors:
bfs_map_test.cpp: In function `int main(int, char**)': bfs_map_test.cpp:69: 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_distmap_as_color_map.hpp:48: note: MapAsColorMap<Graph, ReadablePropertyMap, ColorValue>::MapAsColorMap(ReadablePropertyMap&, typename boost::property_traits<IndexMap>::value_type) [with Graph = main(int, char**)::Graph, ReadablePropertyMap = size_t*, ColorValue = int]
Can someone please help me?
This works: template<typename Graph, typename ReadablePropertyMap, typename ColorValue> class MapAsColorMap { public: typedef typename boost::graph_traits<Graph>::vertex_descriptor key_type; typedef ColorValue value_type; typedef ColorValue reference_type; typedef boost::read_write_property_map_tag category; ColorValue get(key_type key); MapAsColorMap(ReadablePropertyMap& pm, // typename boost::property_traits<ReadablePropertyMap>::value_type white): size_t white): white_(white), pm_(pm) {}; private: typename boost::property_traits<ReadablePropertyMap>::value_type white_; ReadablePropertyMap& pm_; }; , with ReadablePropertyMap=size_t* Why isn't typename boost::property_traits<ReadablePropertyMap>::value_type=size_t? Or if it is, why doesn't it work? Cheers, Jens
Jens, the ReadablePropertyMap parameter has to be a class with the following typedef at least: typedef value_type some_type; -----Original Message----- Can someone please help me?
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.
Hi, Jens, I was able to reduce the number of compilation errors from 32 to 27 by adding namespace boost everywhere (BGL is described in the namespace boost) and some other minor changes. Now the compilation error is in the test file due to incorrect ussage of your adaptor (I guess): 1>d:\documents and settings\dmitry\my documents\visual studio 2005\projects\bgl_users_help\bgl_users_help\bfs_distmap_as_color_map.hpp(50) : error C2825: 'ReadablePropertyMap': must be a class or namespace when followed by '::' 1> d:\documents and settings\dmitry\my documents\visual studio 2005\projects\bgl_users_help\bgl_users_help\bfs_map_test.cpp(68) : see reference to class template instantiation 'boost::MapAsColorMap<Graph,ReadablePropertyMap,ColorValue>' being compiled 1> with 1> [ 1> Graph=Graph, 1> ReadablePropertyMap=__w64 unsigned int [], 1> ColorValue=int 1> ] WBR, --Dmitry -----Original Message----- From: Jens Muller [mailto:jens.mueller@ira.uka.de] Sent: Sunday, February 04, 2007 3:21 AM To: boost-users@lists.boost.org Subject: [Boost-users] [graph] BFS and dedicated color map 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 ... Could someone point out the most stupid bugs? Thanks a lot in advance ...
Dmitry schrieb:
Hi, Jens, I was able to reduce the number of compilation errors from 32 to 27 by adding namespace boost everywhere (BGL is described in the namespace boost) and some other minor changes. Now the compilation error is in the test file due to incorrect ussage of your adaptor (I guess): 1>d:\documents and settings\dmitry\my documents\visual studio 2005\projects\bgl_users_help\bgl_users_help\bfs_distmap_as_color_map.hpp(50) : error C2825: 'ReadablePropertyMap': must be a class or namespace when followed by '::'
Well, I forgot to use property_traits there - but I still have problems, see the other posts ...
participants (2)
-
Dmitry
-
Jens Müller