CODEWITHSUNDEEP
algorithmdirected-acyclic-graphsdirected-graph
jeevcat
jeevcat

Reputation: 363

Create Directed Acyclic Graph from Undirected Acyclic Graph given "roots"

Consider the following undirected acyclic graph:

undirected

If we define the "roots" to be A and E, is there an algorithm that can determine the resulting directed acyclic graph?:

directed

I considered trying some kind of DFS or BFS starting from the roots but I wasn't really sure how to deal with the need to "wait" to see if another root might reach the given node.

Upvotes: 2

Views: 1090

Answers (1)

templatetypedef
templatetypedef

Reputation: 373112

I’m assuming that what you’re looking for is an orientation of the edges such that

  • the overall graph is a DAG, and
  • the source nodes of the DAG are the ones you’ve indicated.

For now, let’s ignore the second constraint. An easy way to make the whole graph a DAG would be to assign an ordering 1 ... n to the nodes, then have edges always point from lower nodes to higher nodes. So the question would then be how to assign the numbers in a way that gives you the second property.

I believe you can do this by running a BFS over the graph, seeding the queue with all k of your root nodes. If you number the nodes in the order in which they’re discovered, then you’ll get a DAG (any ordering of the nodes gives a DAG). Moreover, assuming no two of the roots are adjacent to one another and that there’s at least one root in each connected component of the graph, your roots will be the only roots.

To see this, suppose none of your roots are adjacent and the graph is connected, then assume for the sake of contradiction that some other node is a root. Take the lowest-numbered node other than one of your chosen nodes that’s also a root. Because the node was assigned a number, it must have been discovered in the BFS, so it’s adjacent to some other, lower-numbered node that was also found in the BFS. But then the edge from the lower-numbered node will have an arrow into the higher-numbered node, so it won’t be the root.

(In the event that you have two adjacent nodes that want to be roots, there’s no way to make this work, since one will have an arrow into the other.)

Overall, this runs in time O(m + n) because it’s just a BFS over the graph.

Upvotes: 2

Related Questions