[Boost-users] write_graphviz with listS as vertex container

From: Meredith L. Patterson (mlp_at_[hidden])
Date: 2004-11-05 17:01:56

Hi all,

I've been using the Boost Graph Library for a project that requires the 
use of the graphviz library, and have run into a quandary. For reasons 
that are a bit complicated to get into right now, my users need to be 
able to remove vertices from what are at times extremely large graphs 
(~75,000 vertices), so vecS is clearly the wrong type for runtime reasons.

The problem comes with write_graphviz. As the documentation points out, 
the graph must have an internal vertex_index property map; listS doesn't 
have an inherent vertex_index the way vecS does, so I've defined 
vertex_index as a property (along with vertex_name); the code compiles 
and runs. However, in the DOT output, I get a vertex list that looks like:

0[label="foo"];
1[label="bar"];
2[label="baz"];
[....]

and an edge list that looks like

0x8061d90->0x8061db8 [weight="5"];
0x8061d90->0x8061c50 [weight="13"];
[....]

Obviously, the edge list is using vertex descriptors (which in this case 
end up being the memory location of each vertex object), while the 
vertex list is using vertex indices (and a quick look at graphviz.hpp 
confirms this; starting from line 262, the function uses 
get(vertex_index, *i) to get vertex identifiers for the vertex list in 
the DOT file, and source(*ei, g) and target(*ei, g) to get source-vertex 
and target-vertex identifiers for the edge list. This isn't a big deal 
when the vertex list type is vecS, of course, because vertex-index is 
basically a pointer into the vector, but it doesn't work for listS, 
setS, et cetera.

Any suggestions for how to resolve this contradiction? I suppose I could 
try overloading source() and target(), but if there's an easier way to 
do it, I'd rather go that route. :)

Cheers,
Meredith L. Patterson