[Boost-users] [graph] BFS and dedicated color map

From: Jens Müller (jens.mueller_at_[hidden])
Date: 2007-02-03 21:21:12

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 ...