Hi Matthieu,

Is this what you're looking for?

https://graph-tool.skewed.de/static/doc/gt_format.html

Best

Haiko

Hi Matthieu,

Is this what you're looking for?

https://graph-tool.skewed.de/static/doc/gt_format.html

Best

Haiko

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

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

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

Hi Matthieu,

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