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

Subject: Re: [Boost-users] [BGL] IncidenceGraph and out_edges
From: Christian Bähnisch (christian-baehnisch_at_[hidden])
Date: 2009-06-17 03:30:34

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

I dont see why this requirement is one of the esoteric ones as traversing the 
set of all vertices incident to another vertex is a often used operation and I 
still do not undertand why out_edges is used for this. Why is there no 
explicit function for this purpose?

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