Thanks Tiago, and sorry I did not find it by myself.
I would love to have your feedback on this related question, if it is of interest to you: https://cs.stackexchange.com/questions/146325/fast-and-compact-data-structure-for-dynamic-graphs Best, ML On Thu, Dec 09, 2021 at 03:15:58PM +0100, Tiago de Paula Peixoto wrote: > Hi, > > The data structure is an adjacency list. The definition is here: > > > https://git.skewed.de/count0/graph-tool/-/blob/master/src/graph/graph_adjacency.hh > > Adding nodes or edges is O(1). > > Removing a node is O(N + E) in the worst case if the node index ordering is > preserved, otherwise it is O(k + k_last), where k is the degree of the > vertex being removed, and k_last is the degree of the nodes with the highest > index. > > Removing an edge is O(k_s + k_t), where k_s and k_t are the degrees of the > source and target nodes, if Graph.set_fast_edge_removal() has not been set, > otherwise it is O(1) (at the expense of more memory bookkeeping). > > This is all explained in the documentation... > > Best, > Tiago > > Am 09.12.21 um 15:06 schrieb Matthieu Latapy: > > Well, not far: this is the file format. But it seems very close to the > > central memory representation, right? > > > > Does this mean that the representation is an array indexed by nodes, and > > then for each node an array of its neighbors? How does this deal with graph > > updates? > > > > (It was so long since I read hexdump for the last time, thanks for this > > too! *__*) > > > > Best, > > ML > > > > On Thu, Dec 09, 2021 at 01:48:51PM +0000, Lietz, Haiko wrote: > > > Hi Matthieu, > > > > > > Is this what you're looking for? > > > > > > https://graph-tool.skewed.de/static/doc/gt_format.html > > > > > > Best > > > > > > Haiko > > > > > > _______________________________________________ > > > graph-tool mailing list -- [email protected] > > > To unsubscribe send an email to [email protected] > > > > > -- > Tiago de Paula Peixoto <[email protected]> > _______________________________________________ > graph-tool mailing list -- [email protected] > To unsubscribe send an email to [email protected] -- --------------- Matthieu Latapy http://latapy.complexnetworks.fr -------------------------------- _______________________________________________ graph-tool mailing list -- [email protected] To unsubscribe send an email to [email protected]
