Re: [Boost-users] [BGL] IncidenceGraph and out_edges

Subject: Re: [Boost-users] [BGL] IncidenceGraph and out_edges
From: Andrew Sutton (andrew.n.sutton_at_[hidden])
Date: 2009-06-20 08:57:20

>
> 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.

Andrew Sutton
andrew.n.sutton_at_[hidden]