Re: [Boost-users] [Graph] Guarantee on bidirectional graphs

Subject: Re: [Boost-users] [Graph] Guarantee on bidirectional graphs
From: alex (alexhighviz_at_[hidden])
Date: 2014-03-13 14:44:38

>From: >Sensei
>in a bidirectional graph there is no
>distinction between in and out edges, so I am worried BGL could
>rearrange them for some internal representation reason.
>

Well, the documentation promises not to do that. And many applications would
fail if BGL didn't live up to that promise. 

http://www.boost.org/doc/libs/1_55_0/libs/graph/doc/BidirectionalGraph.html

" For both directed and undirected graphs, the target of an out-edge is
required to be vertex v and the source is required to be a vertex that is
adjacent to v. "

http://www.boost.org/doc/libs/1_55_0/libs/graph/doc/IncidenceGraph.html#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)."

> By the way, is there the analog index function for edges as far as you 
> know? This code works (the ei->idx), but I fear I'm on the edge of a 
> disaster like I was with the nodes :)

Yes it looks like disaster, at least it doesn't seem to be a generic
solution. I think the generic approach would be to use an (external or
internal) edge index map. So you could do
auto index = get(my_index_map, *ei);

http://lists.boost.org/boost-users/2010/04/57922.php