3
$\begingroup$

I would like to merge connected nodes with a specific attribute of a directed acyclic graph. The purpose is to detect max connected clusters of blue nodes and merge them. After each merge operation, the graph should remain acyclic. Let's say my graph contains blue nodes and white nodes.

enter image description here

A and B are connected, they may be merged:

enter image description here

The above graph is DAG. Merging node {A,B} with node {D} is illegal since it creates a cycle!

enter image description here

My current algorithm is based on union-find.

For each blue node b:
   Make-Set(b)
For each two connected blue nodes a,b: 
   Union(a,b)
For each set://Created at the previous step
   merge all nodes of the set

The bug is the output graph contains cycles. How can I avoid merges that create cycles in the graph? Before each Union, I need to check that it "safe". Safe means that after merging cycle will not be created. I can find all passes between the set of a and set of b before Union but this solution is too expensive (time complexity). I can't use solutions with a quadratic time complexity since my graph is too big. Edit: We can merge nodes according to topological order but the following case will be messed (D):

enter image description here

Nodes A, B, and D may be merged, but we will merge only A and B. Max Cluster example: at the graph below the cluster is {A, B, C, D, E}

enter image description here

$\endgroup$
  • 2
    $\begingroup$ Are you familiar with a topological order of a DAG? If two vertices are consecutive in your topological ordering, can you then safely merge them? $\endgroup$ – Pål GD Aug 15 at 15:06
  • $\begingroup$ @PålGD, merging according to topological order is safe and correct but not optimal. Please take a look at the last edit. $\endgroup$ – David Aug 18 at 8:34
  • $\begingroup$ I don't think this is possible with an algorithm of linear time complexity, since simply checking for cycles in your DAG seems to take $O(|E|) \geq O(n)$ time. Do you have some information on the sparsity of the graph, e.g. does it have only $O(n)$ edges? $\endgroup$ – J. Schmidt Aug 18 at 15:17
  • 1
    $\begingroup$ Why would you only merge A and B in a topological merge and not D as well? $\endgroup$ – Bryce Kille Aug 18 at 18:28
  • 4
    $\begingroup$ Can you define "optimal"? The question doesn't state anything about optimality. If you have some requirement for optimality, please edit the question to explain that, in the question. In other words, the problem statement doesn't seem to be fully defined. I'm not sure what kinds of outputs are considered acceptable and what kind are not. $\endgroup$ – D.W. Aug 19 at 22:43
1
$\begingroup$

I think instead of performing merge at the beginning. We can add a node which has the similar edges as the two merged vertices.

Having the following DAG.

enter image description here

If we want to merge node A and B. We add a new node which has the similar attributes as A + B.

enter image description here

Then trasverse from new node AB (should be Depth-first):

  • If it find Node A or B, then the merge should be cancelled because it creates a cycle. simply delete Node AB.
  • If we do not se Node A or B, the merge is valid so delete node A and node B.
$\endgroup$
  • $\begingroup$ Thanks, I don't see how your algorithm solves the problem. Let's take a look at my main example. The wished output is the second picture. The merge should not be canceled, I would like to avoid merging node D since this merge creates a cycle. $\endgroup$ – David Aug 18 at 15:05
  • $\begingroup$ Why should it be a depth-first search, instead of a breadth-first? $\endgroup$ – J. Schmidt Aug 18 at 15:23
  • $\begingroup$ @J.Schmidt depth-first search is optimal when we want to look to the end of DAG first while breadth-first favors looking to nodes in the same level perspectively. Both depth-first and breadth-first can work in this but depth-first will help to find a circle faster because it will look up to the end of each graph branch first, then switch to another nodes' branch and perform the same trasversing. $\endgroup$ – Lam Nguyen Aug 19 at 0:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.