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