CODEWITHSUNDEEP
graph
Frank D.
Frank D.

Reputation: 61

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?

Upvotes: 6

Views: 6629

Answers (3)

Bertil Baron
Bertil Baron

Reputation: 5003

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.

Upvotes: 0

lijie
lijie

Reputation: 4871

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).

Upvotes: 4

gdj
gdj

Reputation: 1295

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

Upvotes: -1

Related Questions