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