6
$\begingroup$

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$:

    1. $z \gets V[x][len(V[x])-1];$
    2. $V[x][E[x,y]] \gets z;$
    3. $E[x,z] \gets E[x,y];$
    4. remove last element of $V[x]$;
    5. 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:

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

$\endgroup$
3
  • $\begingroup$ There is some info in SNAP: A General Purpose Network Analysis and Graph Mining Library, in particular: "Other ... libraries ... are NetworkX ... and iGraph .... In terms of the speed vs. flexibility trade-off, NetworkX offers maximum flexibility at the expense of performance. Nodes, edges and attributes in NetworkX are represented by hash tables, called dictionaries in Python.". You can probably follow the references to find more info. I don't claim that the paper answers your question (I just found it by googling "networkx hashtable"). $\endgroup$
    – Dmitry
    Dec 2, 2021 at 20:09
  • $\begingroup$ Thanks @Dmitry! This partly answers my question: they indeed do not use dynamic arrays for neighborhoods, but hash tables everywhere, which is close. This makes the structure seriously bigger, though, and operations slower, but with complexities close to the ones I mentionned. Still, thanks to this structure, NetworkX indeed seems to be one of the best available options for huge number of updates (on not-too-large graphs). $\endgroup$ Dec 2, 2021 at 20:29
  • $\begingroup$ (Thanks @greybeard, replaced.) $\endgroup$ Dec 7, 2021 at 10:17

1 Answer 1

1
$\begingroup$

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:

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.

$\endgroup$
6
  • $\begingroup$ This is indeed a variation of the structure I ask about; it is the one implemented in NetworX and discussed in the comments above. It however has a set structure per node, implemented as a hash table, which needs much more space and is much slower than having dynamic arrays and a unique hash table for all edges. Still, I would not call it "the standard representation of a graph used in graph algorithms", as it is not presented in algorithms books and the references I cite in the question, for instance. What I am looking for is a study of this structure. $\endgroup$ Dec 7, 2021 at 8:20
  • $\begingroup$ @MatthieuLatapy I don't think it is slower or requires more space? Your data structure requires two hash table lookups for edge insertion and deletion too, and $E$ has to be roughly as large as the set of all edges. $\endgroup$
    – 6005
    Dec 7, 2021 at 13:27
  • $\begingroup$ Clarified the answer: this representation is standard in most implementations, to my knowledge. It's also mentioned in Cormen Leiserson Rivest Stein, Exercise 22.1-8. $\endgroup$
    – 6005
    Dec 7, 2021 at 13:40
  • $\begingroup$ Suggestions on how to improve the answer are welcome! $\endgroup$
    – 6005
    Dec 8, 2021 at 15:58
  • $\begingroup$ I am happy to know that a similar data structure is mentionned as an exercice in this great book, thanks. I am still looking for a documented study of its performances in theory and practice, though. And I still wonder why it is not discussed in publications like the ones cited in the question. I am interested in libraries implementing it, too; NetworkX does, NetworKit does not, for instance. $\endgroup$ Dec 9, 2021 at 8:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.