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-15 10:25:00

>
> 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_at_[hidden]