Fast and compact data structure for dynamic graphs

Question

A graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$ may be represented in central memory as follows:

• an associative array (hash table) $V$ gives for any $v\in \mathcal{V}$ the list of its neighbors $V[v]$, each of these lists being represented as a dynamic array;

• another associative array $E$ gives, for any $(u,v)\in \mathcal{E}$, the index of $v$ in $V[u]$.

This structure is very appealing if many graph updates (vertex and/or edge additions and/or removals) are performed. Indeed, graph updates may be performed in constant time (details below), and the whole structure takes only linear space. In addition, testing edge presence is in constant time and parsing node neighborhoods is optimal.

The literature on dynamic graph structures is very rich (see examples below). Yet, I can't find any (formal or empirical) analysis of this simple structure anywhere.

Does anyone have a pointer to such a study? If not, is this because people focus on worst case complexity only, and avoid hash tables for this reason? or because they assume only few graph editions are performed? or because it is considered too space costly? ...

---

Linear time updates are obtained as follows:

• adding vertex $x$ is just adding the key $x$ to the associative array $V$, with an empty dynamic array as associated value;

• removing vertex $x$ is just removing key $x$ from the associative array $V$ (assuming it has no edge at removal time);

• adding edge $(x,y)$ is just adding $y$ to the end of the dynamic array $V[x]$ and setting $E[x,y]$ to the correct value, $len(V[x])-1$;

• removing edge $(x,y)$ is slightly more subtle if $x$ has more than one neighbor; it consists in moving the last element $z$ of $V[x]$ to the position of $y$ and removing the last element of $V[x]$, which may be done efficiently thanks to the associative array $E$:

  0. $z \gets V[x][len(V[x])-1];$
  1. $V[x][E[x,y]] \gets z;$
  2. $E[x,z] \gets E[x,y];$
  3. remove last element of $V[x]$;
  4. remove key $(x,y)$ from $E$.

Operations on dynamic arrays are in $O(1)$ amortized time, and operations on associative arrays (i.e. hash tables) are in $O(1)$ expected time. Therefore all operations above are in constant time. Testing edge existence is in constant time too (hash table access), and one may also optimally parse the neighborhood of any vertex (it is an array). In addition, the whole data structure needs linear space $O(|\mathcal{V}|+|\mathcal{E}|)$ only, as hash tables and dynamic arrays do.

---

The literature on dynamic graph representations does not seem to consider the structure above, see for instance:

• On dynamic succinct graph representations by Miguel E. Coimbra, Alexandre P. Francisco, Luís M. S. Russo, Guillermo de Bernardo, Susana Ladra, Gonzalo Navarro
• CSR++: A Fast, Scalable, Update-Friendly Graph Data Structure by Soukaina Firmli, Vasileios Trigonakis, Jean-Pierre Lozi, Iraklis Psaroudakis, Alexander Weld, Dalila Chiadmi, Sungpack Hong, Hassan Chafi
• Low-Latency Graph Streaming Using Compressed Purely-Functional Trees by Laxman Dhulipala, Julian Shun, Guy Blelloch

Likewise, popular graph libraries do not seem to use this data structure, even performance-oriented ones that allow graph updates, like Networkit.

Answer 1

Your data structure is a variant of the following standard data structure to represent a graph:

edges: Map[V, Set[V]]

where V is the type of vertices. That is, for each vertex, we store the set of adjacent vertices in a set. The map and set can be implemented as hashtables, so this is a hashtable of hashtables.

Sources (sorry I don't have more!)

I did a bunch of digging through textbooks, Wikipedia, and implementations, and admit I am baffled that this representation does not seem often covered. So, I asked a separate question about it here. This is a related question, where the top answer suggests using the above representation. I did find the following brief mentions:

• Cormen Leiserson Rivest Stein: Introduction to Algorithms, Exercise 22.1-8.

• Morin: Open Data Structures, page 255: "What type of collection should be used to store each element of adj?"

Comparison to your representation

Your representation differs in that you store the incident vertices as a dynamic array, rather than as a set. But the dynamic array (together with your edge map $E$ to recover the index in the dynamic array from the edge name) is not really necessary. Instead of having $E$ to recover the index, above we store the incident vertices by label directly rather than by index.

The above supports all the operations you support in constant time: adding a vertex, removing a vertex, adding an edge, removing an edge, and checking edge existence. It also uses linear space. If a directed graph is desired, we can have two maps, fwd_edges: Map[V, Set[V]] and bck_edges: Map[V, Set[V]] to allow iterating over either forward or backward edges.

I don't think that your representation is fundamentally different from the above, but I do like your careful development of the map $E$ and I would be curious to see if you can show formally whether or not it is equivalent to this representation.

Other variations

By the way, you may be interested in important variations of adjacency lists. One variation is if you want to support quickly merging vertices. Merging two vertices as array lists or sets is not possible efficiently, but for some dynamic graph algorithms we need $O(1)$ merge. For this, researchers use a union-find data structure to merge the vertex labels, and instead of Set[V] or your dynamic array, vertices are stored using a linked list. Linked lists can be merged in $O(1)$, so everything remains $O(1)$ except, unfortunately, checking for existence of an edge and deleting an edge, which require iterating over all possible edges. See for example, A New Approach to Incremental Cycle Detection and Related Problems, Bender, Fineman, Gilbert, Tarjan, 2015 for such a data structure in use.