Re: [Boost-users] Bidirectional Graph and undirected graphs

Subject: Re: [Boost-users] Bidirectional Graph and undirected graphs
From: Michael Olea (oleaj_at_[hidden])
Date: 2009-05-13 19:08:56

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