0
$\begingroup$

I have a graph like this that starts from one top node and has cycles:

enter image description here

I need to write an algorithm to figure if node1 depends on node2. The most primitive algorithm I've written simply starts with node1 and recursively follows all available edges looking for node2 starting from node1. It's very inefficient because I traverse the graph over and over again. I'm wondering if there's an algorithm I can look at that caches nodes and dependencies it already walked through so that I don't go through paths I've walked once and can figure if there's a dependency or not from cache?

For example, if I'm given node D and the question is whether it depends on node F, I'll walk D->E->F, and when next time I get the question if node E depends on F, I'll get that from cache without walking the graph.

Thanks for any ideas and suggestions!

Improve this question
$\endgroup$
1
$\begingroup$

This is a classic problem known as "reachability querying". There are various algorithms possible, with different complexities.

Unless you are working with some huge graphs and can not afford to store the index, the simplest is storing the $O(|V|^2)$ transitive closure of your graph. This can be computed quite simply with Floyd-Warshall in $O(|V|^3)$, and with a lot more effort in $O(|V||E|)$ using the methods found in Nuutila's thesis.

Now if your graphs are truly large and you can not afford to spend $O(|V|^2)$ memory you enter an academic world of dozens upon dozens of papers, each with slightly varying performance characteristics (very often incomparable, yet almost always claiming to beat the competition), and varying difficulty of implementation. I guarantee you that almost all of them will be hard to implement however.

Allow me to reproduce Table 1 from Reachability querying: an independent permutation labeling approach, a recent paper by Hao Wei et. al. Here we have as main parameters $n = |V|$, $m = |E|$, $k$ is the width of the graph, $t$ is the number of non-tree edges of the graph after a spanning tree is formed.

enter image description here

Improve this answer
$\endgroup$
6
  • $\begingroup$ thanks! transitive closure is something I'll start with, just wondering if it makes sense to fill out the adjacency matrix gradually as I get request for a node instead of filling it all in a single run beforehand? $\endgroup$ – Max Koretskyi Jul 31 '20 at 14:17
  • $\begingroup$ @MaxKoretskyi That's up to you, if you can afford the precomputation I would recommend it since it makes everything super quick and predictable afterwards. $\endgroup$ – orlp Jul 31 '20 at 14:30
  • $\begingroup$ I see, appreciate your help! $\endgroup$ – Max Koretskyi Jul 31 '20 at 14:37
  • $\begingroup$ a quick question, you say this can be computed quite simply with Floyd-Warshall in O(|V|3), this articles states it can be computed in O(V2) using DFS, is it correct? $\endgroup$ – Max Koretskyi Jul 31 '20 at 15:44
  • $\begingroup$ @MaxKoretskyi No that's not correct, it's complexity is $O(|V|(|V|+|E|))$ which is $O(|V|^3)$ for dense graphs. $\endgroup$ – orlp Jul 31 '20 at 16:29

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.