Re: [boost] [BGL] connected_components() 2nd arg type?

From: llee (llee1_at_[hidden])
Date: 2001-11-06 10:47:21

On Tue, 2001-11-06 at 04:48, Petr Ovchenkov wrote:
> I have a couple questions related to BGL.
> 
> Basic container other then vector require some additional definitions,
> isn't it?
> 
> The code
> 
>    typedef adjacency_list<vecS, vecS, undirectedS> Graph;
> 
>    Graph g;
>         
>    boost::add_edge( 1, 2, g );
>    size_t nv = boost::num_vertices( g );
> 
> 
> compile and work fine, but if I replace Graph definition by
> 
>    typedef adjacency_list<listS, listS, undirectedS> Graph;
> 
> compilation fail. (The first example work only for vecS). I need write
> 
>    boost::add_edge( vertex( 1, g ), vertex( 2, g ), g );

The second template parameter in adjacency_list class is to specify the
backbone of the two dimensional structure to store graph data. vecS is
to choose std::vector while listS is to use std::list. std::vector is
random access container. So we use integer to represent vertex. The
latter where vertex is a complex object.  In both case the vertex type
is accessed by graph_traits<Graph>::vertex_descriptor.

> But I still not understand what type I should define for 2nd argument
> of call 
> 
>    size_t num = boost::connected_components( g, component );

In the former case, component can be a random access iterator whose
value type is integer type. 

However, if graph is std::list as backbone, to be able to call
connected_components, you have to define component color and index as
internal vertex properties. So the real grapg type would be:

typedef property<vertex_component_t, size_t, 
                 property<vertex_color_t, default_color_type,
                 property<vertex_index_t, size_t> > >

typedef adjacency_list <listS, listS, undirectedS, VertexProperties >
Graph;

Here vertex_color_t, vertex_index_t are predefined. You need create 
vertex_component_t:

namespace boost {
  enum vertex_component_t        { vertex_component        = 1001 };
  BOOST_INSTALL_PROPERTY(vertex, component);
}

Now, the type of component is ,
 property_map<Graph, vertex_component_t>::type 
      component = get(vertex_component, G);
Then you call connected_components:
  int num = connected_components(G, component);
 
Using list as graph backbone complicates a lot. But the benefit you get
is fast remove vertex. 

> Another question is: how I should define Graph, if I want to save
> memory as much as possible, and vertex key and value are the same?

You had better to use adjacent_list<vecS, vecS> if you do not want
dynamicaly add and remove vertices. 

> How I should define 2nd argument of connected_components()?
> 
> Thanks in advance,
> 
>    - Petr
> 
> 
> 
> Info: http://www.boost.org  Unsubscribe: <mailto:boost-unsubscribe_at_[hidden]> 
> 
> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/ 
> 
> 
-- 
Lie-Quan Lee (AKA: Rich Lee)
Research Associate                   
Open Systems Laboratory        Phone:    [phone]
Computer Science Department    Email:    llee_at_[hidden]
Indiana University             Homepage: http://www.osl.iu.edu/~llee