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: 1-812-855-3608 Computer Science Department Email: llee_at_[hidden] Indiana University Homepage: http://www.osl.iu.edu/~llee