Boost logo

Boost :

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 >

Here vertex_color_t, vertex_index_t are predefined. You need create

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: Unsubscribe: <mailto:boost-unsubscribe_at_[hidden]>
> Your use of Yahoo! Groups is subject to

Lie-Quan Lee (AKA: Rich Lee)
Research Associate                   
Open Systems Laboratory        Phone:    1-812-855-3608
Computer Science Department    Email:    llee_at_[hidden]
Indiana University             Homepage:

Boost list run by bdawes at, gregod at, cpdaniel at, john at