title: Efficient algorithm for merging two DAGs
body: <p>I have two weighted DAGs (directed acyclic graphs) and need to merge them into one, so I can get a topological ordering (it could be more than two in some cases). The problem is that the graphs are acyclic each, but can form a cycle together. Also, the graphs are large (100k+ nodes, 500k+ edges).
  Is there a clever way to merge the graphs? Equally good would be an algorithm to traverse all graphs "at once".</p>
  
  <p>Edit:</p>
  
  <p>By "merge" I mean combining all edges and vertices of both graphs together (preserving weights of course), if they do not create cycles. If an edge already exists I want to use the greater weight for it.</p>
  
  <p>The idea is that starting with two acyclic graphs should give an advantage over simply "fixing" the result afterwards (this would imply to find the feedback arc set which is NP hard so I wanted to avoid that).</p>
  
  <p>Thank you for your suggestions.</p>