Check if two nodes are on the same path in constant time for a DAG
<p>I have a DAG (directed acyclic graph) which is represented by an edge list e.g.</p>

<pre><code>edges = [('a','b'),('a','c'),('b','d')]
</code></pre>

<p>will give the graph </p>

<pre><code>a - &gt; b -&gt; d
|
v
c
</code></pre>

<p>I'm doing many operations where I have to check if two nodes are on the same path (<code>b</code> and <code>d</code> are on the same path whereas <code>b</code> and <code>c</code> are not from example above) which in turn is slowing down my program. I was hoping I could somehow traverse the graph once and save all paths so I can check this in constant time.</p>

<p>Is this speed-up possible and how would I go about to implement this in python?</p>

<p>Edit: 
Note that I need to check for both directions, so if I have a pair of nodes <code>(a,b)</code> I need to check for both <code>a</code> to <code>b</code> and <code>b</code> to <code>a</code>.</p>

<p>You actually want to find the <a href="https://en.wikipedia.org/wiki/Transitive_closure" rel="nofollow">transitive closure</a> of the graph. </p>

<blockquote>
  <p>In computer science, the concept of transitive closure can be thought
  of as constructing a data structure that makes it possible to answer
  reachability questions. That is, can one get from node a to node d in
  one or more hops?</p>
</blockquote>

<p>There are multiple ways of finding the transitive closure of the graph. The simplest way is using the <a href="https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm" rel="nofollow">floyd-warshall</a> algorithm <em>O(|V|<sup>3</sup>)</em>. Explained <a href="http://www.geeksforgeeks.org/transitive-closure-of-a-graph/" rel="nofollow">here</a>.  </p>

<p>Another way is to perform a DFS from each node and mark all the nodes you visit as reachable from the current node. Explained <a href="http://www.geeksforgeeks.org/transitive-closure-of-a-graph-using-dfs/" rel="nofollow">here</a>.</p>

<p>There is also a method that works only on DAGs. First perform a topological sorting on your DAG. Then work backward in the topological sorted list and <code>OR</code> the transitive closure of the children of the current node together, to get the transitive closure of the current node. Explained <a href="http://cs.stackexchange.com/questions/7231/efficient-algorithm-for-retrieving-the-transitive-closure-of-a-directed-acyclic">here</a>.</p>

<p>Below is the Python implementation of the DFS based method:</p>

<pre><code>def create_adj_dict_from_edges(edges):
    adj_dict = {}

    for e in edges:
        for u in e:
            if u not in adj_dict:
                adj_dict[u] = []

    for e in edges:
        adj_dict[e[0]].append(e[1])
    return adj_dict

def transitive_closure_from_adj_dict(adj_dict):

    def dfs(node, visited):
        if node not in adj_dict:
            return
        for next in adj_dict[node]:
            if next in visited:
                continue
            visited.add(next)
            dfs(next,visited)

    reachable = {}
    for node in adj_dict:
        visited = set(node,)
        dfs(node,visited)
        reachable[node] = visited

    return reachable

def main():
    edges = [('a','b'),('a','c'),('b','d')]
    adj_dict = create_adj_dict_from_edges(edges)
    tc = transitive_closure_from_adj_dict(adj_dict)
    print tc
    # is there a path from (b to d) or (d to b)
    print 'd' in tc['b'] or 'b' in tc['d']
    # is there a path from (b to c) or (c to b)
    print 'c' in tc['b'] or 'b' in tc['c']


if __name__ == "__main__":
    main()
</code></pre>

<p><strong>output</strong></p>

<pre><code>{'a': set(['a', 'c', 'b', 'd']), 'c': set(['c']), 'b': set(['b', 'd']), 'd': set(['d'])}
True
False
</code></pre>

python algorithm graph-algorithm directed-acyclic-graphs graph-traversal