How to convert an undirected, very cyclic graph into a directed acyclic graph?

Question

I am working on a modified TopSort algorithm, and I am having problems finding / creating large (over 1000 nodes) directed acyclic graphs for testing. I have an undirected sample graph from another project that has a good size but has many loops. Is there an algorithm I could use to guide the edges so that there are no more loops?

Answer 1

this provides a way to get acyclic graphs. In principle, traversing the graph creates a tree that defines a partial order on the source nodes. Then just point all the edges so that they either point in a sequential direction according to a partial order, or are between two elements that are not ordered (they can point in any direction).

Answer 2

To make sure the new directed graph is connected, I would use the first search in the following order.

old_undirected graph G new_directed graph D dequeue Q v is any node in G add v to D Q.push_back(v) while(Q is not empty): v = Q.pop_front() for all neighbors u to v: if u in D add edge u->v to D else add u to D and add edge v->u to D Q.push_back(u) return D 

this graph must contain all the edges of the original graph, but must be directed so that there are no circles.

Answer 3

You want to transform the graph into a forest of root trees. make a crawl across the width or depth of each graph. During the traversal, make a directed edge between the vertices of parent-child.

see http://en.wikipedia.org/wiki/Graph_traversal