[Networkit] Graph.shrinkToFit()

Florian Weber uagws at student.kit.edu
Mon May 12 23:36:44 CEST 2014


> I believe in the worst case the graph takes 
> almost twice as much memory as needed. 

It's actually worse than that: std::vector never decreases it's size
unless this is explicitly requested:

std::vector<int> vec;
assert(vec.capacity() >= 100);

The assert is guaranteed by the iso-standard not to fail.

> So this could be an important improvement. I say
> „could“ because there is one thing that needs to be checked, namely whether 
> shrinking significantly increases construction time. 

construction time of what? Copy-Ctors don't care for the capacity of the
object they copy.

> If it does we need to see 
> if we want to make the tradeoff.

I would recommend implementing this with a shrinkToFit-method that is to
be called by the user (basically exactly the same that std::vector
does), so that there really wouldn't be a tradeoff. (Graph has so many
methods, this one, that unlike many others really cannot be reasonably
implemented as a free function, won't be a problem there).

Best regards

-------------- n?chster Teil --------------
Ein Dateianhang mit Bin?rdaten wurde abgetrennt...
Dateiname   : signature.asc
Dateityp    : application/pgp-signature
Dateigr??e  : 901 bytes
Beschreibung: OpenPGP digital signature
URL         : <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20140512/a4abc2c4/attachment-0001.sig>

More information about the NetworKit mailing list