12
$\begingroup$

In answering this question, I was looking for references (textbooks, papers, or implementations) which represent a graph using a set (e.g. hashtable) for the adjacent vertices, rather than a list. That is, the graph is a map from vertex labels to sets of adjacent vertices:

graph: Map<V, Set<V>>

In fact, I thought that this representation was completely standard and commonly used, since it allows O(1) querying for an edge existence, O(1) edge deletion, and O(1) iterating over the elements of the adjacency set. I have always represented graphs this way both in my own implementations and teaching.

To my surprise, most algorithms textbooks do not cover this directly, and instead represent it using a list of labels:

graph: Map<V, List<V>>

As far as I understand, adjacency lists seem strictly worse: both representations support O(1) vertex additions and iteration over adjacent edges, but adjacency lists require O(m) for edge removal or edge existence (in the worst case).

Yet I am baffled that, for example Cormen Leiserson Rivest Stein: Introduction to Algorithms, Morin: Open Data Structures, and Wikipedia all suggest using adjacency lists. They mainly contrast adjacency lists with adjacency matrices, but the idea of storing adjacent elements as a set is only mentioned briefly in an off-hand comment as an alternative to the list representation, if at all. (For example, Morin mentions this on page 255, "What type of collection should be used to store each element of adj?") I must be missing something basic.

Q: What is the advantage of using a list instead of a set for adjacent vertices?

  • Is this a pedagogical choice, an aversion to hashmaps/hashsets, a historical accident, or something else?

  • This question is closely related, but asks about the representation graph: Set<(V, V)>. The top answer suggests using my representation. Looking for a bit more context on this.

  • The second answer suggests hash collisions are a problem. But if hash sets are not preferred, another representation of maps and sets can be used, and we still get great performance for edge removal with a possible additional logarithmic factor in cost.

  • Bottom line: I don't understand why anyone would implement the edges as a list, unless all vertex degrees are expected to be small.

$\endgroup$
12
  • 2
    $\begingroup$ A list is a lot easier to implement. Consequently, some operations would be faster. Also, the memory footprint is probably lower. $\endgroup$ Dec 9, 2021 at 20:57
  • 1
    $\begingroup$ …and instead of an adjacency matrix you can also use a Set<(V, V)>. Just different memory consumption and less direct (but still average O(1)) access. I guess it depends mostly on the sparsity of the graph (how many edges each node has on average) how well they perform in practice. $\endgroup$
    – Bergi
    Dec 10, 2021 at 13:07
  • 2
    $\begingroup$ Same question on Stack Overflow: stackoverflow.com/q/69777086/12299000 $\endgroup$
    – kaya3
    Dec 11, 2021 at 9:50
  • 1
    $\begingroup$ In addition, "list" is a rather unambiguous term in computer science; "set" is a term with a very different meaning in mathematics than in programming languages. Since computer science is a subfield of mathematics, most computer science books avoid the word "set" completely when naming data structures. (At least, most computer science books that I've read avoid it.). A hash table is called a hash table, and the word "set" is reserved for its mathematical meaning. It would be kinda sad to make hash tables a prerequisite for learning about graphs. $\endgroup$
    – Stef
    Dec 11, 2021 at 15:00
  • 1
    $\begingroup$ @6005 You can go through 5 years of theoretical computer science, studying graphs and graph algorithms, with vertices always numbered from 0 to n-1. And during practical exercises, when you need to actually program something and your vertices are given as something else than a number, it's not a hard mental gymnastic to add one look-up table somewhere in the program. $\endgroup$
    – Stef
    Dec 11, 2021 at 22:05

4 Answers 4

26
$\begingroup$

In many algorithms we don't need to check whether two vertices are adjacent, like in search algorithms, DFS, BFS, Dijkstra's, and many other algorithms.

In the cases where we only need to enumerate the neighborhoods, a list/vector/array far outperforms typical set structures. Python's set uses a hashtable underneath, which is both much slower to iterate over, and uses much more memory.

If you want really efficient algorithms (and who doesn't), you take this into account.

If you need $O(1)$ lookup of adjacencies and don't intend to do much neighborhood enumeration (and can afford the space), you use an adjacency matrix. If expected $O(1)$ is good enough, you can use hashtables, sets, trees, or other datastructures with the performance you need.


I suspect, however, that you don't hear about this so often, is because in algorithms classes, it makes analysis much simpler to use lists, because we don't need to talk about expected running time and hash functions.


Editing in two comments from leftaroundabout and jwezorek. Many real world graphs are very sparse and you often see $O(1)$-sized degrees for most of the graphs. This means that even if you want to do lookup, looping through a list is not necessarily much slower, and can in many cases be much faster.

As a "proof", I add some statistics from the graphs from Stanford Network Analysis Platform. Out of approximately 100 large graphs, the average degrees are

Avg. degree number of graphs
< 10 35
< 20 43
< 30 10
< 40 4
< 50 2
< 70 3
< 140 1
< 350 1
$\endgroup$
4
  • $\begingroup$ This all makes sense, thanks. Perhaps another factor is that in an algorithms class, often the graph is given as a static input. So you can store the adjacency lists up front, and even sort them if needed, and edge removal is not a concern. On the other hand, edge removal matters for a graph data structure that is updated dynamically. $\endgroup$
    – 6005
    Dec 9, 2021 at 22:18
  • 1
    $\begingroup$ Yes, exactly. There are many variables ranging from space consumption to memory layout. Whether you need to add or delete edges and vertices during the "hot loops" massively affects the decision of data structure. $\endgroup$
    – Pål GD
    Dec 9, 2021 at 23:27
  • 5
    $\begingroup$ Another aspect is that many graphs are sparse in practice, so the overhead of a set may outweigh its asymptotic disadvantage even if direct lookup is required. $\endgroup$ Dec 10, 2021 at 7:30
  • $\begingroup$ Also graphs that come up in practice often do not have degrees that are arbitrarily high. in various applications of graph algorithms you often have a sense of the maximum number of neighbors any vertex will have. If that maximum is not particularly high then you can treat vertex neighbor lookups as O(1) even doing a linear search. $\endgroup$
    – jwezorek
    Dec 11, 2021 at 23:37
2
$\begingroup$

In general you are correct, however the list version is sort-of legitimate in the odd case where there can be more than one edge between two nodes. Of course it would still be more conceptually correct to represent the neighbors of each node as a mapping type between node and amount of edges.

When I say "conceptually correct" I mean that due to the fact that the neighbors of a node are not ordered, conceptually, using an ordered structure to represent that collection is not proper. The abstract mathematical definition of a graph represents the collection of neighbors as a set, because that's what it is. Programming close to the mathematical representation helps with clarity. If tomorrow I stumble upon a graph implementation where the collection of neighbors is an array or a list I will immediately be suspicious that neighbor order plays a role somewhere, which is an enormous addition on mental load.

Depending on the expected use of the graph, it can be faster to use linked lists, arrays, tree-based sets or hash-based sets to hold the neighbors of each node. In my experience (with high level languages where these collections are easy to use), sets are usually the best choice because testing for adjacency between two arbitrary nodes is what I typically happen to do a lot.

As to why they are represented like that in those books, I think you gave the answer already: the authors didn't think the distinction to be worth much discussion. Graphs are an ancient topic in programming courses, and it very well might be that these passages date back to a time where lists and arrays were abstractions implemented by the language itself, but not sets. And so it was much easier and less confusing to talk to students back then about the collections they could most easily get access to.

$\endgroup$
1
$\begingroup$

In one of the comments, Yuval mentions that the memory footprint is far lower. I'd like to expand on that point a little.

The adjacency data structure is conceptually a subset of $V$. Suppose there are $k$ edges from some vertex. Assuming the edges are independent, there are ${ \left|V\right| \choose k }$ possible subsets. So any representation of this adjacency collection must require at least this many bits to store:

$$\log { \left|V\right| \choose k }$$

(Note that since we're doing information theory, all logarithms are base 2.)

Let $p = \frac{k}{\left|V\right|}$ be the probability of an edge being present. Then by Stirling's approximation:

$$\begin{eqnarray*}\log { \left|V\right| \choose k } & \approx & \left|V\right| \log \left|V\right| - k \log k - (\left|V\right|-k) \log (\left|V\right|-k) \\ & = & \left|V\right| H_b(p)\end{eqnarray*}$$

where $H_b$ is the binary entropy function:

$$H_b(p) = -p \log p - (1-p) \log (1-p)$$

When $p \approx \frac{1}{2}$, $H_b(p) \approx 1$, so you need at least $\left|V\right|$ bits of information to represent this collection. A bit vector is optimal.

When $p \ll \frac{1}{2}$, $\log { \left|V\right| \choose k } \approx k \log \left|V\right|$, so an array of $k$ elements, each containing an integer between $1$ and $\left|V\right|$, is optimal.

(Note that when $p > \frac{1}{2}$, it may be more space efficient to store the vertices that are not present.)

So in the sparse case, not only is smaller, it is an optimal representation.

$\endgroup$
3
  • $\begingroup$ That's an insightful perspective, thanks. However, won't a set data structure take the same space as the array? (Up to 2x more for a hash table based set, or roughly the same amount of space for a tree-based set) $\endgroup$
    – 6005
    Dec 11, 2021 at 4:58
  • $\begingroup$ "Up to 2x more" is double, and similarly, if you use a tree, there's extra space required to represent the structure of the tree. Unlike in time analysis where there's always a constant factor because of clock speeds and compiler differences, with space analysis bounds can be tight. Having said that, it is possible to get very close to the optimal size with hashing if you use an invertible hash function, so you can recover part of the key from the index of the hash slot. $\endgroup$
    – Pseudonym
    Dec 11, 2021 at 8:31
  • $\begingroup$ If it helps, a compression algorithm that takes twice as long to run than you expect might still be practical, but one that compresses to only a factor of two larger than you expect could be useless. $\endgroup$
    – Pseudonym
    Dec 11, 2021 at 10:22
1
$\begingroup$

Here is a different way to think about it. Let's try to represent a graph with adjacency hash tables instead of adjacency lists.

What hash function will we choose, and how large must the table be?

If there are $n$ vertices and they are already numbered $0...n-1$, then I think the most sensible choice of hash function is the identity function! And the size of each hash table will be exactly $n$. Finally, each hash table is simply a boolean vector of length $n$.

Finally, instead of an array of hash tables, we end up with a boolean matrix, called an adjacency matrix. Adjacency matrices have been well-suited, and in fact they are better than adjacency lists for some purposes. But worse than adjacency lists for some other purposes.

  • "Iterate on the neighbours of a given vertex" is a $\Theta(d)$ operation with adjacency lists, but $Θ(n)$ operation with an adjacency matrix, where $d$ is the degree of that vertex and $n$ the total number of vertices, so lists are better for that purpose;
  • "Are two given vertices neighbours?" is an $O(1)$ operation with a matrix, but $O(d)$ operation with adjacency lists;
  • You can do linear algebra with a matrix, but not with lists; in particular, if $M$ is the adjacency matrix of a graph, then $M^k$ gives the number of walks of length $k$ between each pair of vertices; using fast matrix exponentiation, this can allow for much faster algorithms than adjacency lists for some problems.

Adjacency hash tables appear to be slower than adjacency lists on the first point, and slower than matrices on the last two points.

$\endgroup$
16
  • $\begingroup$ Thanks for the answer. I agree up until the last paragraph: the size of the hash table should be much less than $n$, if $n$ is large, right? That's the whole point of using hash tables $\endgroup$
    – 6005
    Dec 11, 2021 at 17:18
  • $\begingroup$ Also in practice, we can't assume that the vertices are already numbered $0$ to $n-1$, typically they would be something like strings or arbitrary objects. So we need a hash table anyway to assign identifiers to vertices. $\endgroup$
    – 6005
    Dec 11, 2021 at 17:18
  • $\begingroup$ Yes, you might have one hash table to map the vertices' names to their indices, and an array of pointers mapping their indices back to their name (and other proprieties), but typically, when solving a problem, you'd only need to refer to those tables once at the beginning (to go from name to index) and once at the end (to go from index back to the full object), but not during the bulk of the calculations. $\endgroup$
    – Stef
    Dec 11, 2021 at 22:11
  • $\begingroup$ OK, agreed on the $0$ to $n-1$ numbering point. But do you agree that this statement is wrong: "the size of each table would be much greater than $n$". Hash table would be O(degree of the vertex). Unless I misunderstood your point. $\endgroup$
    – 6005
    Dec 12, 2021 at 4:52
  • 1
    $\begingroup$ Wait, on par with adjacency lists on the second point? It's $O(1)$ on average $\endgroup$
    – 6005
    Dec 12, 2021 at 18:45

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.