Re: [boost] [BGL] connected_components() 2nd arg type?

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2001-11-06 14:00:35

Hi Petr,

(Lie-Quan Lee and I are figuring this out...)

On Tue, 6 Nov 2001, Petr Ovchenkov wrote:

ptr> Dear Lee,
ptr>
ptr> Great thanks for you answer.
ptr>
ptr> Can I clarify one more thing?
ptr>
ptr> How much memory require
ptr> boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS>?
ptr>
ptr> Say, I have 2899233 vertexes, so for vector<int> it will be about
ptr> 2899233 * 4 = 11M

No, there's about 20 bytes per vertex. Each vertex has an out-edge
list which is a std::vector, which is 16 bytes, and then there's
another byte where the property object would go.

2899233 * 20 = 57M

ptr> But I see allocation of ~65M. So we have 5 integers (or pointers) per
ptr> vertex.

So that's in the right ballpark.

ptr> Then I begin to add edges, my heap grow up to 380M, and I see that
ptr> this is not enough. The number of edges is less then twice number
ptr> of vertexes (65M * 3 = 195M + 65M = 260M ???).

There's also about 36 bytes per edge. We keep a std::list of all the edges
in the graph. In this list is the edge property object (4 bytes) and the
source/target vertex pointer (8 bytes). The list has a prev/next pointer
(8 bytes). There's 2 pointers in the out-edge lists to each edge in the
std::list (8 bytes). Also there's the two target vertex pointers in the
out-edge lists (8 bytes).

So for 2 * 2899233 = 5798466 edges

we have 209M

for a total memory of 57M + 209M = 266M.

Hmm, we are still a bit off from what you saw. Our estimation of bytes per
vertex and edge is based on the SGI implementation of std::vector and
std::list. If you are using a different implementation that could change.
There's also a chance we forgot about a few bytes.

ptr> I am not expected such numbers.
ptr> What estimation of required memory we should use for V vertexes,
ptr> E edges with object size S?

There would be two objects sizes, one for vertex properties (VS) and one
for edge properties (ES). With no properties, VS and ES are 4 bytes each.

V * (16 bytes + VS) + E * ( 32 bytes + ES)

So the adjacency_list class is not as lean memory wise as you might like.
We did not have space efficiency as the first priority for adjacency_list,
Time efficiency and functionality were the primary goals. One could reduce
the size a lot by giving up some functionality or lots of time.

For example, a really space efficient representation would be to use the
forward star representation (Network Flows by Ahuja et. all). But then
adding and removing edges would be very slow.

If space efficiency is your primary requirement, I would suggest writing
your own graph class, and you might even consider submitting it to Boost!

Cheers,
Jeremy and Lie-Quan

----------------------------------------------------------------------
 Jeremy Siek                          http://php.indiana.edu/~jsiek/
 Ph.D. Student, Indiana Univ. B'ton   email: jsiek_at_[hidden]
 C++ Booster (http://www.boost.org)   office phone: [phone]
----------------------------------------------------------------------