Search code examples
algorithmgraphnetworkxgremlingraph-algorithm

Converting a DAG to Binary Tree

I am trying to convert a DAG to a binary tree. Consider the following graph enter image description here

I want to have the following output for above tree. enter image description here

Since A,B,C,E forms a diamond, to convert it into a tree, I need to move B and C into a line.

I have tried following:

  1. Topological Sort : Output is A -> D -> B -> C -> E -> F .
  2. Topological Sort with order : A -> [B,C,D] -> E -> F

Topological Path gives us a straight path. But, I want to preserve the sequence if possible i.e. A -> D. However, if there is a diamond, I want a node to only have one parent and sequence these parents as well.

Is there a way to generate a tree from a DAG for above cases?

Solution

  • Algorithm in pseudo-code

     Run a topological sort on the graph

 For every node B, in reverse order of the topological sort:
    If B has more than one parent:
        Order its parents A1, A2, ..., An in the order of the topological sort
        For every i in 1..n-1:
            Add an arc from Ai to A(i+1)
            Remove the arc from Ai to B

    Proof of correctness

    • The algorithm always terminates, since it is a loop of fixed length; its time complexity is O(N^2) where N is the number of nodes
    • Immediately after the step on a given node B, B has no more than one parent
    • If the step on a given node C has already been executed, then executing the step on a node B that comes before C in the topological order only adds arcs to nodes that come before C in the topological order; hence once a node's step has been executed, they never gain new parents.

    This proves that the algorithm terminates and that every node has at most one parent after executing the algorithm. Since we only remove parents from nodes which had more than one parent, I think it also satisfies your question.