Hi,

The data structure is an adjacency list. The definition is here:

https://git.skewed.de/count0/graph-tool/-/blob/master/src/graph/graph_adjace...

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 -- graph-tool@skewed.de To unsubscribe send an email to graph-tool-leave@skewed.de

Hi Matthieu,

On Thu, Dec 9, 2021 at 4:41 PM Matthieu Latapy Matthieu.Latapy@lip6.fr 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-structur...

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_adjace...

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 -- graph-tool@skewed.de To unsubscribe send an email to graph-tool-leave@skewed.de

-- Tiago de Paula Peixoto tiago@skewed.de _______________________________________________ graph-tool mailing list -- graph-tool@skewed.de To unsubscribe send an email to graph-tool-leave@skewed.de

--

---

Matthieu Latapy http://latapy.complexnetworks.fr

---

---

graph-tool mailing list -- graph-tool@skewed.de To unsubscribe send an email to graph-tool-leave@skewed.de

_______________________________________________ graph-tool mailing list -- graph-tool@skewed.de To unsubscribe send an email to graph-tool-leave@skewed.de