On Thu, 29 Dec 2011, Kelvin Chung wrote:

On 2011-12-29 15:00:10 +0000, Nicholas Mario Wardhana said:

...

On 29 December 2011 15:16, Kelvin Chung <kelvSYC@mac.com> wrote:

...

Suppose I have the following:

template <class T> class Graph {   // Adapter class that I use for my purposes        typedef typename boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, T> innerGraph;        typedef typename boost::graph_traits<innerGraph>::vertex_descriptor VertexDescriptor;

       innerGraph G; public:        void addVertex(const T& vertex);        bool containsVertex(const T& vertex) const;

       void addEdge(const T& from, const T& to);        // More stuff here };

The intent of this adapter class is to basically abstract out all the mentions of stuff like the descriptors and such.  So a good helper function to this end would be a function that retrieves the VertexDescriptor for a given T, if it exists.  Is there such a function already in the BGL, or do I have to manage that separately (ie. having an external map)?

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

How about storing the descriptor in the T object, by having a member like

VertexDescriptor descriptor;

?

Constant-time retrieval is guaranteed, but then you have to typedef VertexDescriptor in your T. Alternatively, you can have it globally defined.

Wouldn't that impose a concept (or interface) requirement on T? (BTW, what are the current concept requirements for T? Does changing the second template param to boost::setS to disallow parallel edges also implies that T must be less-than comparable?) Or at least, present a chicken-and-egg problem regarding putting my T in a wrapper that also stores the VertexDescriptor? (Not that keeping an external T to VertexDescriptor map is any different, mind you, but at least I know what the external map means for the concept/interface requirements for T.)

You can use the adjacency_list_traits class (documented in the adjacency_list documentation) to get the descriptor types to use in your bundled property type.

(Sometimes the language of the BGL documentation confuses me. Especially the fact that "Bundled Properties" seems to be a euphemism of "use a data structure that you like")

That is exactly what it is for -- using your own data structure for properties. -- Jeremiah Willcock

Am 30.12.2011 11:27, schrieb Anders Wallin:

As a comment to this: when I write algorithms that do a lot of modifications to a graph, a common reason for a segfault is accessing the bundled property (either vertex or edge) of a BGL-graph with an illegal vertex/edge-descriptor. It would be useful if in debug-mode, or perhaps a special "safe"-mode BGL would guard against this segfault and produce an assert() on g[illegal_descriptor]

I wonder whether a special graph type might be sufficient/desired here? E.g., one might want to never re-use descriptors of deleted vertices/edges even by mistake. -- Jens

Am 05.01.2012 14:42, schrieb Jeremiah Willcock:

...

...

I wonder whether a special graph type might be sufficient/desired here?

E.g., one might want to never re-use descriptors of deleted vertices/edges even by mistake.

Yes, a special graph type is probably what would be needed; that would also allow vertices and edges to be deleted by just hiding them, avoiding invalidation of other descriptors (which makes working with graphs that are mutated very difficult in BGL now).

I think we think of two different things: My idea was a graph class that breaks immediately as soon something happens that is undefined behavior. E.g., one could put a version number in descriptors to be able to tell that they have become invalid. You in contrast want to ease some of these restrictions to make the graph easier to use. -- Jens