Re: [Boost-Users] Large graph: how to use internal property maps in connected_components?

From: Douglas Gregor (gregod_at_[hidden])
Date: 2003-03-23 12:59:20

On Friday 21 March 2003 08:49 am, Martin Okrslar wrote:
>   typedef typename boost::adjacency_list<
>     boost::listS, //edges
>     boost::listS, //nodes
>     boost::undirectedS,
>     //vertex properties
>     boost::property<boost::vertex_name_t, std::string, //the name of the
> protein
>     boost::property<boost::vertex_component_t, int >
>
>     // no edge properties
>
>     > Graph;
[snip]
> /project/algorithmics/include/boost/property_map.hpp:344: no match for
> `const
>    __gnu_cxx::__normal_iterator<boost::default_color_type*,
>    std::vector<boost::default_color_type,
>    std::allocator<boost::default_color_type> > >& + const
>    boost::detail::error_property_not_found&' operator
>
> What is going wrong? Do I have to use a color_type_t (Why? How?)?

The connected components algorithm uses a color map for internal storage. If 
you don't supply a color map, it tries to build a default color map using the 
vertex index property. That's where this is failing: when the vertex list 
type is listS, there is no default vertex_index property, so the code fails. 
There are a few fixes to this:

1) [the easy way]. Use a vector for the vertices, with a Graph definition like 
this:

   typedef typename boost::adjacency_list<
     boost::listS, //edges
     boost::vecS, //nodes
     boost::undirectedS,
     //vertex properties
     boost::property<boost::vertex_name_t, std::string, 
     boost::property<boost::vertex_component_t, int >
     // no edge properties
     > Graph;

2) [the slightly harder way]. Add a vertex_index property for vertices, and 
keep that updated. So the Graph definition would look like this:
   typedef typename boost::adjacency_list<
     boost::listS, //edges
     boost::listS, //nodes
     boost::undirectedS,
     //vertex properties
     boost::property<boost::vertex_name_t, std::string,
     boost::property<boost::vertex_component_t, int,
     boost::property<boost::vertex_index_t, int> > >
     // no edge properties
     > Graph;

  But you'll have to manually assign the vertex indices:
    Graph::vertex_iterator v,ve_end;
    int i = 0;
    for(boost::tie(v, v_end) = vertices(g); v != v_end; ++v, ++i) {
      put(boost::vertex_index, g, *v, i);
    }

3) [slightly harder yet way]. Create your own color map, where the key type is 
a Graph::vertex_descriptor and the value_type is boost::default_color_type. 

        Doug