Let's say I have an edge type in my datastructure which has two references to
its incident vertices and I have the source and target functions implemented
such that I can get the two vertices. Let's also say the edge type is not so
lightweighted and I use some kind of handle, i.e. and index or pointer, to
pass them around. I implement out_edges such that the iterator can be used to
access all edges incident to a vertex via the handles.
If out_edge together with target is used to get all incident vertices - as
done in BGL - I must impose an artificial direction on the edges, i.e. i have
to attach a flip flag or something similar in order to guarantee that the target
function returns the desired vertex next time it is called. If you use an
lightweited edge type such as std:pair this is not problematic, as the edges
can be created on the fly by out_edges_iterator with the desired implicit
direction.
Don't think of the edge descriptor as simply referring to an edge that connects two vertices.Think of it as a traversal descriptor that says, "you're moving from source to target along this edge".
You could adapt your edge descriptor as the same kind of pair that you're describing:
struct edge_descriptor {
my_edge* edge;
my_vertex* source;
};
Assuming that you can figure out the target from the source, then this would satisfy all of the requirements of the BGL. Your out_edge_iterator would have to be specialized to construct these descriptor objects when being dereferenced, but that shouldn't be too hard.
So my question is why BGL doesn't use adjacency_iterator for vertex-ring
traversal in their algorithms?! If done so I could implement
adjacency_iterator for my datastructure without the headache of implicit
directions!
As I said before, there are applications that need to know about the edge being traversed. Using adjacency_iterator would preclude all of those applications.
Adapting graph classes to the BGL is a fairly non-trivial problem. If you want your graph data structure to work with their algorithns, then you have to adapt to its semantics. This usually requires a lot of extra code in the form of descriptors and iterators.