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?
_______________________________________________
Boost-users mailing list
Boost-users@lists.boost.org
http://lists.boost.org/mailman/listinfo.cgi/boost-users