3
$\begingroup$

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

  • Adjacency Lists
  • Adjacency Matrix
  • Incidence Matrix

While I was learning about these structures, another implementation 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 cost of their 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)$
  • Add vertex: $O(1)$
  • Add edge: $O(1)$
  • Remove vertex: $O(V)$
  • Remove edge: $O(1)$
  • Query cost between vertices: $O(1)$

Since this implementation has strictly better time and space complexity then all three options listed, I'm confused as to why this option isn't.

Why isn't this implementation used in practice?

$\endgroup$
  • 1
    $\begingroup$ Terrible cache performance when enumerating the neighbours of a vertex would be one drawback. That's a very common operation in algorithms. $\endgroup$ – David Richerby Jun 29 at 21:56
  • 1
    $\begingroup$ This is basically an adjacency matrix representation but utilizing a sparse matrix representation. $\endgroup$ – Derek Elkins Jun 29 at 22:27
3
$\begingroup$

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

Created by Ryan at cs.stackexchange.com/questions/106457

$\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)$.

$\endgroup$
  • $\begingroup$ In fact, the time-complexity of the most basic operations when they are repeated multiple times using edge-weight hashmap may not as good as indicated by the table above for large graph because of its bad memory locality of reference, as noted by David Richerby. $\endgroup$ – Apass.Jack Jul 1 at 15:38
  • $\begingroup$ Why aren't nested hashmaps listed as used in practice? $\endgroup$ – timotree Jul 2 at 2:10
  • $\begingroup$ Good question. Here is how I will explain it in simplest terms. It is preferred to store a weight graph as an array of data $g=[g[0], g[1], g[2], \cdots,g[n-1]]$, where $g[i]$ stores the information adjacent to vertex $i$ (or $i$-th vertex). $g[i]$ can be a hashmap or an array of $(j,w)$ pairs, where $j$ goes through the neighborhood of $i$ or all vertices of the graph. What is nice about this setup is that we can build and access $g[i]$ easily. That is why the nested hashmap is not seen frequently. $\endgroup$ – Apass.Jack Jul 2 at 3:56
0
$\begingroup$

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.

$\endgroup$

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.