How to convert an undirected graph to a DAG?

Question

The Wiki page says

Any undirected graph may be made into a DAG by choosing a total order for its vertices and orienting every edge from the earlier endpoint in the order to the later endpoint.

But I don't know how to get the total order of an undirected graph. Should I use DFS? If so, how would I proceed?

More info: I'm working on an un-directed graph which has one source and one sink. I'm trying to direct these edges so that by following the edge direction I can get from the source to the sink.

Solution 1

A total order is basically just arranging all the vertices in some order -- think of it as labelling each vertex with a number from 1 to |V(G)|. This gives us a consistent way to know which vertex is higher for any pair of vertices we examine.

Yes, you can obtain a total ordering with depth-first search. Just assign each vertex the value of an incrementing counter each time you explore a vertex in DFS. This is how you can get a total ordering.

But you don't need to explicitly get a labelling of a total ordering to get a DAG. If we use the above time-of-exploration as our ordering, then we can proceed as follows: Orient edges as you do the DFS traversal, pointing each undirected edge away from the vertex that you're currently expanding.

Basically, we have vertices explored earlier pointing to vertices explored later.

eg. if you had

  A
 / \
B---C

and you started by exploring A, you would orient edges incident on A away from A:

A --> B
A --> C
B --- C

Now say you choose B to explore next in your DFS traversal. Then you would leave the edge between A and B alone, because you've already oriented that edge (A has already been fully expanded). The edge between B and C was untouched, so orient that away from our current vertex, B, to get:

A --> B
A --> C
B --> C

When you explore C, all of its neighbours have been fully expanded, so there is nothing left to do for C, and there are no more vertices left to explore.

Response to "More Info":

In that case, just make sure you expand the source vertex first and just don't explore the sink. Eg. for

A-B-C
|/
D

where D is the source and B is the sink, you could: expand D, then A, then C. You would get:

D --> A
D --> B
A --> B
C --> B

Solution 2

Actually I think what it means in the wiki page by "choosing a total order" means defining a total order yourself. In other words, if we check the simplest undirected graph:

A----B

Converting this undirected graph to a DAG clearly depends on whether you choose to order A before B or A after B. If you choose A before B, then it becomes:

A--->B

Otherwise, it becomes:

B--->A

That is exactly what it means by "orienting every edge" from the "EARLIER" endpoint (endpoints that appear earlier in the total order) to the "LATER" endpoint.

Similarly, for:

    A
   / \
  /   \
 B-----C

If you define the total order as:

B A C

Then the directed graph should be something like:

B->A, B->C, A->C

Solution 3

The problem is that after we change our undirected edges into directed ones we don't want any cycles left.

For example, suppose we have the complete triangle graph

A -- B
  \  |
   \ |
     C

We could choose orientations for the edges as A -> B, B -> C and C -> A

A -> B
 \\  |
   \ v
     C

But then we'd get a cycle and that is not a Directed Acyclic Graph.

The trick suggested in the Wikipedia page is choose an ordering of the vertices, any ordering, actually, and use that to decide what directions to point the edges.

Since the edges point upwards in the ordering we can never "fall back down" again to complete a cycle so the resulting graph is guarantted to be acyclic.

Comments

[Terry Shi]

I just refine the original question a lit bit.

[Cameron Bieganek]

Thanks. "any ordering actually", that's the part I was looking for.