Re: [Boost-users] BGL new graph type implementation trouble

Subject: Re: [Boost-users] BGL new graph type implementation trouble
From: Andrew Sutton (andrew.n.sutton_at_[hidden])
Date: 2009-09-03 08:25:07

> Another issue: My custom graph seems to work quite nice, but my application
> slowed down by a factor of 10 or something similiar. The reason is, at least
> as I understand, that my vertex_descriptor is now an array which is costly
> to copy around. However, the vertex_descriptors are passed almost everywhere
> by value such that the structure gets copied over and over resulting in the
> performance degradation. Is there a simple trick to avoid this? It would be
> very helpful if tere is an easy way...
>

The descriptor is an array? Of what size? Most descriptors are typically
small - vertices are either sizeof(size_t) or sizeof(void*) and edge
descriptors usually 2 or 3 times that size. How big is the array?

You could always make the descriptor a pointer to the first element.

>
>
>> Still the vertex_all stuff would be nice to know about. Any hint would be
>>> great.
>>>
>>
>> I'll look into it.
>>
>
> Looking forward to it.
>

After some digging, the all_t selector is a kind of fake property that
selects whatever data member is storing the user-defined properties of a
vertex or edge. I say that it's fake because the graph type has to
explicitly provide support for it by specializing some class templates. The
only two graphs that actually do this are adjacency_list and leda_graph.

I think the leda_graph uses this feature nicely by overloadin
get(vertex_all, g) and get(edge_all, g) and providing special property maps.

Andrew Sutton
andrew.n.sutton_at_[hidden]