Template syntax problems / Boost

[Guest]

(I also posted this to boost-user)

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 source code down there ...
They can also be found here:
http://www.tessarakt.de/stuff/bfs_map_test.cpp
http://www.tessarakt.de/stuff/bfs_distmap_as_color_map.hpp

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

---------------
bfs_distmap_as_color_map.hpp:



#ifndef BFS_DISTMAP_8737
#define BFS_DISTMAP_8737

/* Use distance map (or anything else which suits the following
requirements) as a color map.

Write operations are just ignored.

Read operations work as follows: When the value in the underlying map
equals a specified value, e.g. -1 in a distance map, or the null pointer
in a predecessor map, the 'White' value is returned, otherwise the
'Black' value is returned.

Note: This only is usable for application where there is no need to
distinguish gray and black non-tree edge targets.

Note: Setting the value in the underlying map so that it no longer
corresponds to a 'White' value will have to be done by the visitor
on the discover_vertex event.
*/

/* Template parameters:
- Graph
- ColorValue (default value: int?)
- ReadablePropertyMap (underlying map)
*/

/* Runtime parameters:
- Graph g
- ReadablePropertyMap pm
- ReadablePropertyMap::value_type white
(must be == comparable)
*/

#include <boost/graph/graph_traits.hpp>
#include <boost/property_map.hpp>

template<typename Graph, typename ReadablePropertyMap, typename ColorValue>
class MapAsColorMap
{
public:
typedef 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);
private:
typename ReadablePropertyMap::value_type white_;
ReadablePropertyMap& pm_;
MapAsColorMap(ReadablePropertyMap& pm,
typename ReadablePropertyMap::value_type white);
};

template<typename Graph, typename ReadablePropertyMap, typename ColorValue>
MapAsColorMap<Graph, ReadablePropertyMap,
ColorValue>::MapAsColorMap(ReadablePropertyMap& pm,
typename ReadablePropertyMap::value_type white)
: white_(white), pm_(pm)
{ }

template<typename Graph, typename ReadablePropertyMap, typename ColorValue>
ColorValue MapAsColorMap<Graph, ReadablePropertyMap,
ColorValue>::get(key_type key)
{
return (get(pm_, key)==white_) ? color_traits<ColorValue>::white()
: color_traits<ColorValue>::black();
}


template<typename Graph, typename ReadablePropertyMap, typename ColorValue>
ColorValue get(MapAsColorMap<Graph, ReadablePropertyMap, ColorValue>
pmap, key_type key)
{
return pmap.get(key);
}


#endif

--------------

//=======================================================================
// Copyright 2001 Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee,
//
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
//=======================================================================

// changed by me

#include <boost/config.hpp>

#include <algorithm>
#include <vector>
#include <utility>
#include <iostream>

#include <boost/graph/visitors.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/property_map.hpp>
#include <boost/graph/graph_utility.hpp>

#include "bfs_distmap_as_color_map.hpp"


int main(int , char* [])
{
typedef boost::adjacency_list<
boost::mapS, boost::vecS, boost::bidirectionalS,
boost:roperty<boost::vertex_color_t, boost::default_color_type,
boost:roperty<boost::vertex_degree_t, int,
boost:roperty<boost::vertex_in_degree_t, int,

> Graph;

Graph G(5);
boost::add_edge(0, 2, G);
boost::add_edge(1, 1, G);
boost::add_edge(1, 3, G);
boost::add_edge(1, 4, G);
boost::add_edge(2, 1, G);
boost::add_edge(2, 3, G);
boost::add_edge(2, 4, G);
boost::add_edge(3, 1, G);
boost::add_edge(3, 4, G);
boost::add_edge(4, 0, G);
boost::add_edge(4, 1, G);

typedef Graph::vertex_descriptor Vertex;

Graph G_copy(5);
// Array to store predecessor (parent) of each vertex. This will be
// used as a Decorator (actually, its iterator will be).
std::vector<Vertex> p(boost::num_vertices(G));
// VC++ version of std::vector has no :ointer, so
// I use ::value_type* instead.
typedef std::vector<Vertex>::value_type* Piter;

// Array to store distances from the source to each vertex . We use
// a built-in array here just for variety. This will also be used as
// a Decorator.
boost::graph_traits<Graph>::vertices_size_type d[5];
std::fill_n(d, 5, -1);

// map
MapAsColorMap<Graph, boost::graph_traits<Graph>::vertices_size_type[],
int>
colormap(d, -1);

// The source vertex
Vertex s = *(boost::vertices(G).first);
d = 0;
p = s;
boost::breadth_first_search
(G, s,
boost::visitor(boost::make_bfs_visitor
(std::make_pair(boost::record_distances(d, boost:n_tree_edge()),
std::make_pair
(boost::record_predecessors(&p[0],
boost:n_tree_edge()),
copy_graph(G_copy, boost:n_examine_edge())))) )
.color_map(colormap)
);

boost:rint_graph(G);
boost:rint_graph(G_copy);

if (boost::num_vertices(G) < 11) {
std::cout << "distances: ";
#ifdef BOOST_OLD_STREAM_ITERATORS
std::copy(d, d + 5, std:stream_iterator<int, char>(std::cout, " "));
#else
std::copy(d, d + 5, std:stream_iterator<int>(std::cout, " "));
#endif
std::cout << std::endl;

std::for_each(boost::vertices(G).first, boost::vertices(G).second,
print_parent<Piter>(&p[0]));
}

return 0;

 

[Guest]

Could someone point out the most stupid bugs?

OK, fixed some stupid bugs, now the hard ones remain ...