Hi Matthieu, On Thu, Dec 9, 2021 at 4:41 PM Matthieu Latapy <[email protected]> wrote: > > > 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
Memory is one problem but I don't think its the main problem. Try iterating over std::vector vs any hash based data structure (or just search for such benchmarks). What might be interesting is research on improved hashmaps and I've seen a talk on CppCon from Facebook about their improvements to hashmaps, better memory packing, reduced collisions (sorry I don't remember the name of the talk) but its probably implemented in Folly. Another related area where this is studied are sparse matrices. Not directly answer to your questions but hopefully this helps in your search for relevant papers. Best, Aleks > 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] _______________________________________________ graph-tool mailing list -- [email protected] To unsubscribe send an email to [email protected]
