[Boost-users] [Boost.Graph] Double sided edge properties in undirected graph

From: Ferdi Smit (Ferdi.Smit_at_[hidden])
Date: 2005-10-20 10:00:08

What is the easiest (is there any) way to associate an edge property 
with both edge ends in an undirected graph in the BGL? I would like to 
iterate over the incident edges of a vertex, and obtain the edge 
property for that side of the edge the vertex is on. Ie. for

A (5) <--E--> (1) B

when iterating the incident edges of A, a request for this edge's (E) 
property would return 5, and when iterating vertex B's incident edge (E) 
it would return 1.

For a directed graph this is simple: just store a "source" property and 
a "target" property in each edge. However in the case of an undirected 
graph the source vertex of an edge will always be the one you're 
iterating over incident edges from. So this wouldn't work, as it always 
return the "source" property then, no matter if I'm at A or B.

A solution that came to mind is to convert the undirected graph into a 
directed graph with double edges everywhere. Then I can simply iterate 
over the out_edges and obtain the right property. However, this seems to 
be tedious and possibly a waste of space as I'm reinventing undirected 
graphs manually. Plus I have to rewrite edge removal etc. to keep things 
consistent. I'm aware that this is how BGL works internally anyhow for 
undirected graphs, so I don't want to reinvent it.

Another "solution" is to store an associated vertex with the properties 
for the edge, giving two (vertex, value) pairs per edge. First of all 
this wastes space, and secondly it proves difficult to typedef this 
property inside the graph type as it is a cyclic dependency. External 
property maps could do the trick, but the space issue is still unresolved.

(I'm primarily speaking of adjacency_lists in this post)

A different issue: isn't BGLs genericity an illusion? Compared to for 
example the illusion of container independence in the STL? So far I've 
always needed to know what containers are used for the graph in order to 
make assumptions about iterator validity. For any algorithm using 
removal or addition a list is basically required, with all the added 
problems of the vertex indices not being ints... Is BGL still being 
actively developed? Can I expect positive changes in this area in the 
future? I really like the concept (no pun) of the BGL, but it's 
difficult to use at the moment imho.

-- 
Regards,
Ferdi Smit (M.Sc.)
Email: Ferdi.Smit_at_[hidden]
Room: C0.07  Phone: 4229
INS3 Visualization and 3D Interfaces
CWI Amsterdam, The Netherlands