[Networkit] Graph.shrinkToFit()

Christian Staudt christian.staudt at kit.edu
Mon May 12 19:53:53 CEST 2014

Hi Marvin,

let’s switch to english for discussions on the list. You suggested that the graph data structure currently wastes a lot of memory, and that the std::vectors could be resized with std::vector::shrink_to_fit to free memory.

I agree with your observation. I believe in the worst case the graph takes almost twice as much memory as needed. I was not aware of the shrink_to_fit method. 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. If it does we need to see if we want to make the tradeoff.

You wouldn’t by any chance be interested in implementing the necessary changes to the graph?

Best regards

Am 12.05.2014 um 18:43 schrieb Marvin Ritter <marvin.ritter at student.kit.edu>:

> Hallo,
> die Graph Klasse nutzt viele dynamische Arrays, welche unter Umständen deutlich mehr Speicherplatz allokieren and letztendlich wirklich gebraucht wird.
> Da viele Algorithmen nach dem Einlesen/Generieren eines Graphen diesen nicht mehr verändern (soweit mir bekannt ist), könnte man diesen problemlos wieder freigeben.
> std::vector verfügt seit C++11 über die Methode shrink_to_fit() die genau das bewerkstelligt, sodass das ganze nur ein paar Zeilen in der Graph Klassen wären.
> Viele Grüße
> <ATT00001.c>

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20140512/c14bf21c/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 495 bytes
Desc: Message signed with OpenPGP using GPGMail
URL: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20140512/c14bf21c/attachment.sig>

More information about the NetworKit mailing list