Why isn't an edge-map graph implementation used in practice?

Question

Wikipedia states that three different graph implementations are used in practice:

• Adjacency Lists
• Adjacency Matrix
• Incidence Matrix

While I was learning about these structures, another option occurred to me that seems to have better asymptotic properties than Wikipedia's. My idea is to create a hash map where the keys are (vertex, vertex) pairs and the values are the weight of the edge.

Given that inserting into and querying from a hash map is $O(1)$, I believe the time complexity would be the following:

• Store graph: $O(|E|)$ space
• Add vertex: $O(1)$ time
• Add edge: $O(1)$ time
• Remove vertex: $O(|V|)$ time
• Remove edge: $O(1)$ time
• Query edge existence: $O(1)$ time

This structure has strictly better time and space complexities than all three options listed. So why isn't this implementation used in practice?

Answer 1

Assume we are dealing with the representation of a weighted graph. I will use Python as the programming language to illustrate the points, which will remain true largely if another programming language is used.

Let us call the graph representation raised in the question "hashmap from edges to their weights" or "edge-weight hashmap". I would agree that an edge-weight hashmap is seldom used to represent a weighted graph.

One overwhelming reason is that compared to edge-weigh hashmap, it is usually preferred to use the following popular variation of adjacency list, which I will call "adjacent hashmaps" or "nested hashmaps". The entire graph is represented by a big hashmap $g$, a.k.a. the outer hashmap, which is a collection of $(v, g[v])$ pairs, where $v$ is a vertex and $g[v]$ is a smaller hashmap, a.k.a. the inner hashmap. $g[v]$ is a collection of of $(u, w)$ pairs, where each vertex $u$ is a vertex that is adjacent to $v$ and $w$ is the weight of edge $(v,u)$.

An example

$\begin{array}{c|c} \text{Nested Hashmap} & \text{Edge-weight Hashmap} \\\hline \begin{array}{l@{}l@{}l@{}lll} \{\\ \quad1: &\{2:2,&4:5\},\\ \quad2: &\{1:2, &3:14, &4:5, &5:4\},\\ \quad3: &\{2:14,&5:34\},\\ \quad 4: &\{1:5, &2:5, &5:58\},\\ \quad 5: &\{2:4, &3:34, &4:58\}\\ \}\end{array} & \begin{array}{lllll} \{\\ \quad(1,2):2, &(1,4):5,\\ \quad(2,1):2, &(2,3):14,&(2,4):5,&(2,5):5,\\ \quad(3,2):14,&(3,5):34,\\ \quad(4,1):5, &(4,2):5, &(4,5):58,\\ \quad(5,2):4, &(5,3):34,&(5,4):58\\ \}\end{array} \\ \end{array}$

The alignment of data entries above is meant for easy reading of Python code. By the general nature of hashmap, the actual storage locations of the entries in a hashmap are sort of unpredictable.

Comparison of complexity between nested hashmaps and edge-weight hashmap

$\begin{array}{|l|c|c|}\hline &\text{Nested Hashmap} & \text{Edge-weight Hashmap}\\\hline \text{Store graph} &O(|E|) &O(|E|)\\\hline \text{Add vertex} &O(1) &O(1)\\\hline \text{Add edge} &O(1) &O(1)\\\hline \text{Remove vertex} &O(|V|)&O(|V|)\\\hline \text{Remove edge} &O(1) &O(1)\\\hline \text{Check if two vertices are adjacent} &O(1) &O(1)\\\hline \text{List neighborhood of a vertex }&O(|V|) &?\ O(|E| )\ ?\\\hline \end{array}$

The entry "$?\ O(|E| )\ ?$" entry on the column of "edge-weight hashmap" means that it is not clear how to list neighborhood of a given vertex $v$ efficiently. $O(|E|)$ refers to the time-complexity of the natural way, which goes over all the edges, keeping only the edges that contain $v$.

So both implementations have the same asymptotic time-complexity and space-complexity for all operations, except for listing the neighborhood of a vertex, arguably the most popular iteration on a graph, for which nested hashmaps are significantly faster. In practice, nested hashmaps should also exhibit better cache-friendliness.

Comparison of programming friendliness

Here are the code that does the basic iterations over a graph represented in variable $g$ using nested hashmap or edge-weight hashmap.

$\begin{array}{|l|l|c|}\hline &\text{Nested Hashmap} & \text{Edge-weight Hashmap}\\\hline \text{Iterate over all vertices} &\text{for v in g:} &???\\\hline \text{Iterate over the neighborhood of vertex u} &\text{for v in g[u]:} &???\\\hline \text{Iterate over all edges} &\begin{array}{c}\text{for u in g:}\quad\quad\\\text{ for v in g[u]:}\end{array} &\text{for e in g:}\\\hline \end{array}$

The "???" entries on the column of "edge-weight hashmap" means that it seems rather clumsy to write that piece of code in Python or other programming languages, assuming their generally-available implementations of hashmap.

Nested hashmaps are far more programmer-friendly than edge-weight hashmap.

Summary

Although the time-complexity of the most basic operations using edge-weight hashmap are very good, it does not support the basic iterations well. It should be replaced by nested hashmaps in general.

Exercises

Exercise 1. Verify that this answer is applicable for weighted directed graph after slight adaptation. Verify that this answer is applicable for (unweighted) directed or undirected graph as well.

Exercise 2. Compare edge-weight hashmap with adjacent-weight list in detail. An adjacent-weight list for the graph above in Python can be $g=[[], [(2,2), (4,2)],$ $[(1,2), (3,14), (4,5), (5,5)],$ $[(2,14), (5, 34)],$ $[(1,5), (2,5), (5,58)],$ $[(2,4), (3,34), (4,58)]]$, where $g[v]$ is a list of $(u,w)$ pairs for vertex $v=1,2,3,4,5$ (g[0] is ignored since 0 is not a vertex), where $w$ is the weight of edge $(v,u)$.

Answer 2

There's at least two points that should be raised here:

• Insert and query for a hash table are not in general constant time operations in the worst case.

• There is typically no implementation that would be suitable for every possible case (i.e., different algorithms might benefit from different implementations of the graph). As an example, it doesn't seem clear how you would efficiently iterate over the neighbors of a vertex which several graph algorithms need.