You think not fulfilling this requirement should be no problem? I looked at the
implementation of connected components and to me it seems as if out_edges
together with the target function is used to traverse the vertex-ring of a
vertex!

Right, but that's one of the more esoteric requirements on the source/target requirements for undirected graphs - not necessarily the out_edge function. The basic rule is that edges must encode some notion of directionality. This lets algorithms easily (and uniformly) determine the direction of the traversal over an edge even if that edge is undirected.

Let's say you have the following:

graph g; // An undirected graph
vertex s = // Some vertex
vertex t = // The only vertex adjacent to s

Rules for out edges:
edge e = *out_edges(s, g).first;
assert(source(e, g) == s && target(e, g) == t);

// Rules for edge querues
edge e = edge(s, t);
edge f = edge(t, s);
assert(source(e, g) == s && target(e, g) == t);
assert(source(f, g) == t && target(f, g) == s);
assert(&g[e] == &[g[f]);

It isn't clear whether or not e == f (but it's unlikely).

In the case that, t == s, you have a graph with a loop. During the connected_components algorithm (DFS-based?), you pop source, coloring it non-white and the queue the adjacent vertices (via out_edges). Since s is non-white, it won't be requeued, so it the algorithm should operate as expected.

Andrew Sutton
andrew.n.sutton@gmail.com