On May 13, 2009, at 3:04 PM, Andrew Sutton wrote:



Undirected graphs store only one set of edges. The implementation of the just makes it seem like two different copies :)

I'm not sure I understand your response. I was being sloppy and using edge and edge descriptor interchangeably (since there is no separate concept of an edge).

Edge, edge descriptor. Close enough. In an adjacency list (at least), an edge descriptor is actually based on a pair. This means that the out and in edge iterators can construct an edge descriptor such that source and target return reasonable answers without having to duplicate data.

Right, but I believe that Daniel is asking what his code has to do so that his implementation of an undirected graph "works as a boost graph", which in this context I think means is a valid model of the incidence graph concept:

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

The note for out_edges(u, g):

Returns an iterator-range providing access to the out-edges (for directed graphs) or incident edges (for undirected graphs) of vertex u in graph g. The source vertex of an edge obtained via an out edge iterator is guaranteed (for both directed and undirected graphs) to be the vertex u used in the call to out_edges(u, g) and the target vertex must the a vertex adjacent to u.[1] 
Return type: std::pair<out_edge_iterator, out_edge_iterator>

And the footnote:

[1] For undirected graphs, the edge (u,v) is the same as edge (v,u), so without some extra guarantee an implementation would be free use any ordering for the pair of vertices in an out-edge. For example, if you call out_edges(u, g), and v is one of the vertices adjacent to u, then the implementation would be free to return (v,u) as an out-edge which would be non-intuitive and cause trouble for algorithms. Therefore, the extra requirement is added that the out-edge connecting u and v must be given as (u,v) and not (v,u).

So the answer to what I think Daniel is asking is "it won't work". In particular:

Currently our graph uses a pointer to an edge object as an edge descriptor. Getting the "source" using such an edge descriptor can't always return v since it has no way of knowing where the edge descriptor came from.

will cause algorithms like breadth_first_search to break.

I can change the edge descriptor to be a pair of vertices, which would solve the problem, but don't want to if not needed.

I think it's needed if algorithms like the BGL breadth_first_search are going to work. No?

-- Michael