How do I transform an undirected, very cyclic graph into a directed acyclic graph?

I'm working on a modified TopSort algorithm and am having trouble finding / creating large (more than 1000 nodes) directed acyclic graphs 开发者_开发问答to use for testing. I have an undirected sample graph from another project that is of a good size, but has many cycles. Is there an algorithm I could use to direct the edges so that there are no longer cycles?

this provides a way to get acyclic graphs. Basically, a graph traversal produces a tree, which defines a partial order on the original nodes. Then, just direct all the edges so that they either point in a consistent direction according to the partial order, or are between 2 elements that are not ordered (these can point in any direction).

To garuantee that the new directed graph is connected would I use beadth-first search as follows.

 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 should contain all the edges of the original graph but the should be so directed that there won't be any circles.

You are looking to convert the graph into a forest of rooted trees. make a breadth-first or depth-first graph traversal of each component of the graph. During the traversal, make a directed edge between parent-child vertices.

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