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

Subject: Re: [Boost-users] BGL new graph type implementation trouble
From: Sebastian Weber (sebastian.weber_at_[hidden])
Date: 2009-09-02 05:13:55

Hi!

I implemented a vertex_index for my custom graph and it works perfectly. I
am not sure what interior and exterior properties are when it comes to
custom graph types, I followed the code from leda_graph.hpp and adjusted
things accordingly. Thus I implemented something like you suggested, but
this does not solve the Equality-thing.

It actually turned out that once I defnied an Equality-operation for my
vertex_descriptors, the edge_descriptors which are std::pairs of those
vertex_descriptors, become Equality-compliant and in turn the
depth_first_search runs perfeclty as well as the breadth_first_search.

Now I am facing another problem: Is it possible to read of via graph_traits
somehow at compile time if the underlying graph type is mutable or not?
Depending on this I would like to change the compiled code. The concept
stuff is not the right thing here as it would stop compilation, but I want
to make a function call dispatch depending upon mutability. I only found the
traversal stuff in the traits-classes so I guess a trick is needed here.
Shouldn't graph_traits include some tag which converts to the implemented
concepts of the graph? This is what I was looking for, but well, it is not
there.

Thanks for the hint of the quickbook documents in the trunk - I went through
the process of generating the docs and there is a slight typo in the
qbk-files: It fails to compile the stuff since it assumes the examples to be
in the directory examples, but they are in the example (singular) directory.
A symlink solved it for me, but it ought to be corrected.

Still the vertex_all stuff would be nice to know about. Any hint would be
great.

Sebastian

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]
>
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>