How to convert a graph that is NOT DAG to a graph that is DAG?

Question

Hello there everyone,

Is there any general algorithms that takes a non DAG(directed acyclic graph) as input and outputs a directed acyclic graph.

Currently, I am not sure which data structures I will be using to represent my graph. But, I am searching just for the algorithm at this point.

Hope you guys can inform me on the matter.

Cheers~

I want to go from this:

To this:

NEW GRAPH GRAPH THIS IS ONLY FOR THE SOLUTION BeyelerStudios provided

You could go through directing all visited edges and breaking cycles... but what do you actually want to achieve here? You're changing the property of the input graph, so what are your intentions? — BeyelerStudios, Jun 28 '16 at 12:34
There isn't a single well-defined way to do it, any way to do such a "conversion" will be wrong in some context because it's not a real conversion, you're making an entirely new graph that shares some properties with the original but not all. So what do you actually want the result to be? — harold, Jun 28 '16 at 12:35
@BeyelerStudios Well, for the needs of my research in Bayesian Networks, we have a lot of data from the gene regulatory network, and we organize that data into a kind of undirected cyclic graph. My job is to take that graph and make it into a directed cyclic graph, regardless if some nodes may be lost in consequence of trying to make the graph cyclic. And then the edges that cannot be reversed, I want to lock, so in future instances, we can keep adding to this cyclic graph, without breaking the DAG constraint. — TheQ, Jun 28 '16 at 12:41
@harold Hey harold, well, ideally, the output should be a directed acyclic graph (you're right) that shares a lot of properties (edges) from the undirected graph. The output should be all acyclic WHILE still having as many edges or nodes to the undirected cyclic graph. Does that make any sense? — TheQ, Jun 28 '16 at 12:44
I guess you could do it, but I don't see any easy way to do it yet — harold, Jun 28 '16 at 14:13
" My job is to take that graph and make it into a directed cyclic graph, " sorry i meant directed ACYCLIC graph. — TheQ, Jun 29 '16 at 11:59
Two straight thoughts: you could decompose the graph into a DAG of strongly connected components (Tarjan's algorithm), and then solve each SCC independently. Since you're doing Bayesian stuff you have numbers on things. Maybe you could run a voting system, e.g. the Schulze (Condorcet) method using edge/vertex weights as ballot counts, to decide which edges to delete? [Trivially you could delete all edges to produce a DAG, but I figure that's unsatisfactory.] — Jonas Kölker, Aug 28 '17 at 23:06

score 1 · Answer 1 · edited May 23 '17 at 11:52

You can always simply flip some edges to get an acyclic graph from a cyclic one (graph G with vertices V and edges E):

input: G(V,E), n = |V|

visited <- empty set
queue <- empty queue
for each node in V
    // skip visited nodes
    if visited.find(node)
        continue
    // push a dummy edge (node is unvisited)
    queue.push(edge(inf, node))
    while !queue.empty()
        edge <- queue.pop()
        if visited.find(edge.stop)
            // potential cycle detected
            if edge.start != edge.stop
                // eliminate loops, if any
                E.flip(edge)
        else
            visited.insert(edge.stop)
            for each outgoing edge e at edge.stop
                queue.push(e)

Depending on the queue you use you get different behaviour:

a stack (LIFO queue) results in depth-first traversal
a FIFO queue results in breadth-first traversal
a priority queue results in a DAG containing its spanning tree(s)

There's a caviat in the above code: potential cycle detected. Imagine a graph with vertices A, B, C and edges A->B, A->C, C->B. The above snippet detects a potential cycle when processing C->B last. If you want to disambiguate valid edges from edges introducing cycles at that point you need to show that there are no paths from B to C yet. This is a much harder task and there are some good answers (and hints) in this answer here: basically you'd need to perform another graph traversal to detect (or exclude) such a conflicting path.

How to convert a graph that is NOT DAG to a graph that is DAG?

1 Answers1