algorithmdirected-acyclic-graphsdirected-graphtopological-sort

How to tell if adding an edge to a DAG forms a directed cycle?


Assuming I have a DAG and a given topological order function for every vertex v in the graph, when looking at 2 particular nodes: x, y which I know that |top(x)-top(y)|<10 how can I tell if adding the edge x->y will form a cycle in the graph? I'm trying to achieve a solution that is better then O(V+E)...

What I thought was just checking if top(x) > top (y), if it is then we created a cycle. But i'm afraid I might miss a case, also, does the fact that |top(x)-top(y)|<10 give me any additional info? any enlightments?


Solution

  • We can use the fact that |top(x) < top(y)| < 10 to find an efficient solution.

    First, note that if top(x) < top(y) there is no cycle. Otherwise, let ar[] = y, z₁, z₂ … z_k, x be the nodes in the topological sort between y and x. If there is a path from y to x, it can only go through these vertices. So just check if there is a path:

    haspath[] = {false}
    haspath[1] = true
    for i = 2 to k+2
      for j = 1 to i-1
        if haspath[j]==true and edge(ar[j],ar[i])
          haspath[i] = true
          break
    

    There is a path from y to x iff haspath[k+2] is true.