data structure (and graph edition)

graph-tool
1

Hi Matthieu,

Is this what you're looking for?

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

Best

Haiko

2

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

3

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

4

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

5

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:
Fast and compact data structure for dynamic graphs - Computer Science Stack Exchange

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