1
$\begingroup$

Consider a graph $G = (V,E)$ and the following operation

$\text{neighbour}(v_1,v_2)$: returns true if the vertices $v_1$ and $v_2$ are adjacent, and false otherwise.

I now consider two standard data structures:

Adjacency Matrix. Space complexity is $\mathcal{O}(|V|^2)$ and supports the neighbour-query in $\mathcal{O}(1)$ time.

Adjacency List. Space complexity is $\mathcal{O}(|E| + |V|)$ as far as I understand, however the neighbour-query depends on the degree size.

My question is the following:

How can we improve these data structures using hashing? (space/time complexity in terms of $|V|$ and $|E|$)

Can we e.g. reduce the space complexity of the adjacency matrix and retain an average constant time query?

$\endgroup$
3
$\begingroup$

With hash the space needed is $\mathcal O(|E| + |V|)$ (depending on array size given), and the time is expected $\mathcal O(1)$, but might degrade to $\mathcal O(|V|)$ (depending on collision resolving scheme).
With minimal perfect hash the space is exactly $|E| + |V|$ of entries (of appriopriate entry size).

Minimal perfect hash will map without collisions the given set - array for $n$ elements will have exactly $n$ length, so the $|E|$ edges will occupy exactly $|E|$ array elements. Defined function $h$ will disregarding the number of entries, as opposed to normal hash which might be several times bigger than number of entries and collisions degrade the query time (as linked-list).

This is very efficient scheme for static graph, in case of dynamic one the same issue of rehashing holds. It does not matter how the nodes are encoded (string, int etc.).

How MPH works.

$\endgroup$
  • $\begingroup$ Thanks, +1. Can you go a little more into detail in the last sentence? How? $\endgroup$ – Eff Jul 28 '16 at 18:19
  • $\begingroup$ @Eff if some array (2D) or linked-list or tree is used to store the neighbours then using hash will go into that place. Standard hash presents nasty worst case, so to fullfill benefits of constant time access it must be enforced on hash (hence MPH). The steps to create it are like in ordinary hash. If your setting is different (e.g. dynamic) then it might be heavier step to rehash. If something is unclear please write a comment. $\endgroup$ – Evil Jul 28 '16 at 18:54
  • $\begingroup$ Thanks for the elaboration. It'll take me a little time to think through each step. I usually wait a short while before accepting an answer, but your answer seems good. $\endgroup$ – Eff Jul 28 '16 at 18:56
  • $\begingroup$ No problem, and sure, please wait, check everything and mayhap some better answer show up then of course choose the best. $\endgroup$ – Evil Jul 28 '16 at 19:06
2
$\begingroup$

I have done it this way, but this implies you have your nodes represented as integers from $0$ to $|V| - 1$. It is actually quite similar to adjacency lists, but instead of have a list to store the indexes of the neighbors you will have a hash table (or a hash set depending on your specific problem), the space complexity depends on the specific implementation but with a dynamic array tou may reach $O(|d_{i}|)$ for a given node $i$, to achieve a $O(|E|+|V|)$ space complexity.

In terms of time, as you have a list of hash tables/sets the access for a given node is constant in the list, and depending on your hashing scheme you may achieve $O(1)$ access for each node. As I've mentioned before this assumes you have represented your nodes as integers, so a common hashing method as Knuth's multiplicative method would be fine to retain constant access.

Another option is to represent your graph directly as edges and do a hashing function over the pairs of nodes that represent an edge, this would lead to $O(|E|)$ in theory, depending on your implementation. A common way to implement those hash function is to combine the hash functions of each component of the pair, typically computing the xor of the hash functions. If you already know the size of the graph and it is static is straightforward to came up with a perfect hash function to achieve a tight bound in space and complete $O(1)$ access. It depends on the problem you are solving though.

$\endgroup$
  • $\begingroup$ Thanks for the answer, +1. Both answers agree that one can reduce the query time to $\mathcal{O}(1)$, which was also what I expected. $\endgroup$ – Eff Jul 28 '16 at 18:59

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.