How to check if two DAGs after merge of 2 nodes will not have cycles?

user_1953079 0
Viewed 77

Given 2 random DAGs, which may or may not have common nodes. We randomly pick one node from each, and call them A and B respectively. A != B.

How to check before merging, that if we merge node B into node A (by copying edges from B to edges in A, and destroying the node B), there will be no cycles?

I want to avoid exhaustive search - when we 'virtually' merge this nodes and then for all nodes in resulting graph search for paths from this node to itself.

A Node has unique ID and roughly defined like this:

class Node:
  def __init__(self, id):
    self.id = id
    # set of outgoing nodes
    self.deps = set()
    # set of incoming nodes
    self.dependants = set()

# in the end, I want to write function like this:
def check(A, B):
  assert isinstance(A, Node) and isinstance(B, Node)
  if "there will be no cycles":
    return True # we can merge
  else:
    return False # we can not merge

I do not need the code, algorithm description or algorithm name would be enough.

graph-algorithm algorithm python
1 Answers
  • When B is not a predecessor of A there is no cycle.
  • If B is a direct predecessor of A and B without the edge to A is not a predecessor of A. there is no cycle
  • otherwise there is a cycle

Hmm, pseudo code

if not A in DFS(B) // B is not a predecessor
  return noCycle
if A in B.outEdges and not A in DFS(B less A-Edge) // direct predecessor
  return noCycle
return cycle

which can be optimized to

if not A in DFS(B less A-Edge) 
  return noCycle
return cycle

Consider

B->C->A

Merging A and B will result in

C->A->C

Which is a cycle.

B->A
 ->C

Becomes

A->C

Where

B->A
 ->C->A

becomes a cycle

A->C->A
user_40132580
Related