Re: [Boost-users] BGL new graph type implementation trouble

Subject: Re: [Boost-users] BGL new graph type implementation trouble
From: Andrew Sutton (andrew.n.sutton_at_[hidden])
Date: 2009-09-01 17:30:14

> I found out that if vertex_descriptor is something like std::size_t for
> which all sort of operators are defined, everything is ok. So I suppose it
> is sufficient to supply equality operators and the like for my custom
> vertex_descriptor and I will be fine, right? Can I get the newer quickbook
> version documents somewhere? svn? What branch? Would be great as it looks
> like graph documentation is rather out-dated, e.g. the parallel library is
> now in boost, but nowhere documented.
>

It's not really a case of using size_t. It's a case where graphs that use
size_t map those values onto vertices [0, n) and implicitly (or is it
explicitly? Depends on perspective, I guess) define an interior property
vertex_index_t. For most graph types with vertex_descriptor type == size_t,
the call:

im = get(vertex_index, g)

returns a vertex index map (im), and calling

get(im, v)

with v a vertex descriptor actually just returns v.

For graphs with void* descriptors (or otherwise), there is no implicit
vertex index map. The first call above will fail unless you explicitly
create a vertex_index_t property for the graph. Then you still have to
*assign* the indices. It's not done automatically.

For your graph impl, if you're using something like size_t that maps onto
vertices, then you could probably get around this by providing the following
function (or something similar).

identity_property_map get(vertex_index_t, my_graph_type& g) {
  return identity_property_map();
}

Calls to get(vertex_index, g) where g is an object of your graph type will
use this overload. identity_property_map, I forget if it actually exists, is
basically the type of im in the examples above. I also forget the constness
of these things...

This approach may help solve your problems.

>
> Well, yes I need it. I am using the same program with different underlying
> graphs, depending on what I want to do. So I definetly would like to make
> things work with copy_graph ... I looked into the definition of
> adjacency_list, but this is a beast in my eyes and is not well readable to
> me. So this vertex_all-property is still puzzling me...
>

That's unfortunate :) I'll take a look tomorrow. Maybe Nick or Jeremiah is
more familiar with it?

Andrew Sutton
andrew.n.sutton_at_[hidden]