2
$\begingroup$

Hopefully this question makes sense. Basically, given a DAG, a set of nodes A, and another node b, I'd like to know if node b is an ancestor of any of the nodes in A in that graph.

This is my current implementation:

def is_ancestor(graph, A, b):
    nodes_visited = set()
    frontier = list(A)
    while frontier:
        node = frontier.pop()
        if node not in nodes_visited:
            if node == b:
                return False
            nodes_visited.add(node)
            # add immediate predecessors to the frontier
            frontier.extend(graph.predecessors_iter(node))
    return True

However, in the worst case this is O(|graph|), and this would be a function I would need to call very often, so I'm wondering if I'm missing anything that might make this run faster, preferably without requiring quadratic memory, because then I could just store everything and get O(1).

$\endgroup$
  • 1
    $\begingroup$ Are you asking how to do a one-time precomptutation, so that subsequent queries are fast? If you only have a single query to do, you can't do better than $O(|V|+|E|)$ time -- in the worst case you'll need to look at every node. $\endgroup$ – D.W. Nov 27 '15 at 20:57
  • $\begingroup$ Basically, yes. I will have to call this function many times on the same graph. I've since discovered this wikipedia page, which is basically what I want (except from a set of nodes instead of a single one, but that seems to be trivial). $\endgroup$ – Robin Nov 27 '15 at 21:17
2
$\begingroup$

As far as I know, it is an open problem whether one can do significantly better (in an asymptotic sense).

This is known as the reachability query problem for DAGs. You want to do some precomputation, after which you can answer queries of the form Reachable$(u,v)$ (which should return true if $v$ is reachable via some path from $u$, i.e., if $u$ is an ancestor of $v$).

There are two trivial algorithms:

  • With no precomputation, you can answer each reachability query in $O(|V|+|E|)$ time by just using DFA.

  • With a $O(|V| \cdot |E|)$-time precomputation and $O(|V|^2)$ space, you can precompute the transitive closure of the DAG and then answer each query in $O(1)$ time.

Apparently it is an open problem to do significantly better than this: e.g., to precompute something with less than $O(|V|^2)$ space that enables you to answer reachability queries efficiently. See https://cstheory.stackexchange.com/q/25298/5038 and https://cstheory.stackexchange.com/q/21503/5038.

$\endgroup$
  • $\begingroup$ I seem to have found something. If I'm correct, it needs $O(log(l) ( k - N))$ space, where $l$ is the length of the longest path in the graph, $k$ is the total number of edges in the graph and $N$ is the number of nodes, and the precomputation time... probably $O(N * (k - N))$? and it allows you to answer the queries in $O(1)$, but I don't know if it's actually correct. (Also, if it actually has the performance I think it does) $\endgroup$ – Robin Nov 27 '15 at 21:28
  • 1
    $\begingroup$ @Robin, OK. Sounds like your next step is to (a) try to prove your algorithm correct (by trying to find a proof), and (b) try to prove your algorithm incorrect (by looking for counterexamples). If you manage to prove it correct, you can write an answer to your own question. If you try both and aren't able to succeed at either, you might be in a position to ask a new question asking whether that algorithm is correct. $\endgroup$ – D.W. Nov 27 '15 at 21:43
  • $\begingroup$ I'll try that. In the meanwhile, here is my actual code, for anyone who wants to see it: gist.github.com/gvx/cec8e36048212d08d3ae $\endgroup$ – Robin Nov 27 '15 at 21:46

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.