Menu
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?
219
The idea is to perform Breadth–first search (BFS) or Depth–first search (DFS) on the undirected graph starting from the given vertex and add edges to the directed graph in the direction of the scan.
Any undirected graph may be made into a DAG by choosing a total order for its vertices and directing every edge from the earlier endpoint in the order to the later endpoint. The resulting orientation of the edges is called an acyclic orientation.
An undirected graph is acyclic (i.e., a forest) if a DFS yields no back edges. Since back edges are those edges ( u , v ) connecting a vertex u to an ancestor v in a depth-first tree, so no back edges means there are only tree edges, so there is no cycle.
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).
103
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
