Hi! I am currently trying to implement a new graph type which I want to use with

...

the BGL. The graph implements the Incidence Graph concept and should work out of the box with DFS algorithm of the BGL. However, I had to find out that the edge_descriptor must obey an EqualityComparison concept which keeps DFS from compiling. My current edge_descriptor is just a typedef to std::pair. The vertex_descriptor itself is a custom object I wrote myself.

This is actually documented in the quickbook version of the documents... which are incomplete and not distributed :)

I am actually working on them today... A rare case of free time before I have to teach a class.

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.

...

Another problem turns out to appear with the copy-graph algorithm. This algorithm tries to copy vertex_all-property maps and edge_all property maps which I simply do not have defined in my custom graph as I only support the vertex_index mechanism. So what to do here? How can I tell copy-graph that these maps are not existent?

Any help would be great here as I have the impression to hit limits of the documentation (the Equality-thing is not mentioned in the docs, at least I did not find it...).

I'm not particularly familiar with the inner workings of the algorithm. Do you actually need the algorithm? Most graph data structures are CopyConstructible and Assignable (Semiregular, I think). If your graphs are of the same type, you could probably use those features.

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... Thanks a lot, Sebastian

Andrew Sutton andrew.n.sutton@gmail.com

_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

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.

Look in libs/graph_parallel/doc

Likewise for the quickbook docs. They're in libs/graph/quickbook and aren't (or shouldn't) yet part of the release. They're actually less complete - it's been a long process since I've got a lot of other stuff going on - but they're a little more updated in some respects. They may ore may not be helpful yet. Andrew Sutton andrew.n.sutton@gmail.com

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@gmail.com

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.

I'll assume you aren't talking about const/non-const since that can be done with an overload. As a matter of fact, there is. I added a framework for compile-time mutability properties of graphs that (kind of) parallels the mutability concepts (in graph_concepts, not the documentation), Basically, it assigns tag classes to graphs based on their ability to add and remove vertices and edges with or without properties. You can specialize the graph_mutability_traits for your derived type. There are also a number of metafunctions, graph_has_remove_vertex and is_mutable_graph. The mutability traits aren't actually used outside the BGL tests. They could be, but there aren't really that many generic mutating algorithms. Naturally, it's all undocumented :)

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 working on it. I think I merged all of the quickbook examples into the example directory and forgot to update the links.

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

I'll look into it. Andrew Sutton andrew.n.sutton@gmail.com

Another issue: My custom graph seems to work quite nice, but my application slowed down by a factor of 10 or something similiar. The reason is, at least as I understand, that my vertex_descriptor is now an array which is costly to copy around. However, the vertex_descriptors are passed almost everywhere by value such that the structure gets copied over and over resulting in the performance degradation. Is there a simple trick to avoid this? It would be very helpful if tere is an easy way...

The descriptor is an array? Of what size? Most descriptors are typically small - vertices are either sizeof(size_t) or sizeof(void*) and edge descriptors usually 2 or 3 times that size. How big is the array? You could always make the descriptor a pointer to the first element.

...

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

...

great.

I'll look into it.

Looking forward to it.

After some digging, the all_t selector is a kind of fake property that selects whatever data member is storing the user-defined properties of a vertex or edge. I say that it's fake because the graph type has to explicitly provide support for it by specializing some class templates. The only two graphs that actually do this are adjacency_list and leda_graph. I think the leda_graph uses this feature nicely by overloadin get(vertex_all, g) and get(edge_all, g) and providing special property maps. Andrew Sutton andrew.n.sutton@gmail.com