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! Am Montag, 15. Juni 2009 13:18:59 schrieb Andrew Sutton:

...

I'm trying to implement the IncidenceGraph concept for an non-BGL undirected graph like datastructure. Following the boost documentation the target function used with edges from out_edges(u,g) must give vertices != u.

Can somebody please explain me why this requirement is in BGL! I think it can make the adaption very difficult as it requieres to artificially orientate undirected edges for each call to out_edges. Any help would be much appreciated!

I'm not entirely sure. The constraint makes sense if you're building graphs that don't allow loops, but otherwise, it would not seem to be necessary. There's a small possibility that the requirement actually stemmed from an adjacency_list bug that caused problems when deleting loop edges, but the bug has since been fixed.

I would say: do what you think is right for your own graph structure.

Andrew Sutton andrew.n.sutton@gmail.com

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@gmail.com

Hello,

For an undirected graph there is, by definition/no source or target vertex implicit in the edge. And yet, source() and target() are still required for an undirected graph to behave properly with virtually every BGL algorithm. I used the term "esoteric" because this requires you to apply directional semantics to undirected edges, which is somewhat contradictory and imposes some interesting implementation requirements. Yes, Im ok with this, you still want the incident vertives for a given edge and there is no need to define extra functions for this for undirected graphs.

The out_edges() requirement is a badly stated requirement that is trying to describe source/target requirements for undirected graphs, but do so in a way that precludes an implementation of graphs that contain loops. As such you should probably ignore the requirement.

Explicit function for what? A explicit function for traversing all vertices connected via an edge to a fixed vertex. For example, looking at the implementation for depth_first_visit you can find :

//ei an ei_end are out_edge_iterators tie(ei, ei_end) = out_edges(u, g); //... while (ei != ei_end) { Vertex v = target(*ei, g); //... } as you can see 'out_edges' together with 'target' is used to do this, i.e. for traversing the so called vertex-ring of a given vertex. So why is there no function called "vertex-vertex-Ring(vertex_descriptor u)" for this. Doing this with "out_edges" and "target" means to change the implicit direction of an undirected edge over and over again! best regards, Chris

That's exactly what the adjacency_iterator is for.

http://www.boost.org/doc/libs/1_39_0/libs/graph/doc/AdjacencyGraph.html http://www.boost.org/doc/libs/1_39_0/libs/graph/doc/adjacency_iterator.html

Thank you for this info. However, it is not used (!) in -for example- connected_componets of the BGL which means - please, I have to insist on this point - that connecetd_components will not work if my datastructure does not support the discussed requirement on out_edges. Is there any reason why adjacency_iterator is not used in some cases by BGL algorithms but instead out_edges together with the target function?

What do you mean "doesn't work?". You have to be more explicit. 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. 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! I hope this was explicit enough and thank you in advance for your patience! best regards, Chris