1
$\begingroup$

In trying to understand how to convert DCG's (Directed Cyclic Graphs) to DAG's (Directed Acyclic Graphs) without removing all the edges, I came across this paper which says:

Since the problem involves DCG, therefore a new algorithm to reduce the DCG into the form of a DAG should be proposed. It is simpler when no cycle exists in a graph. A DCGSimplify algorithm is presented to reduce the graph from DCG to DAG.

Update

I am wondering what advantages you gain by removing cycles from your data structure. For example, maybe it allows you to traverse it easier during graph matching, or it makes it so you can generate a graph covering of some sort that's not possible with cyclic graphs. Basically I have noticed many papers talk about DAG's, even in relation to CFGs (Control-Flow Graphs) and data-flow graphs, which in practice always have cycles. They restrict it to DAGs for some reason, and don't address Directed Cyclic Graphs, which CFGs and such are most of the time. Wondering why this is, what advantage does DAGs have from a mathematical perspective or computer science perspective.

$\endgroup$
  • $\begingroup$ What exactly is your question? I don't understand what you mean by "when is it simpler". I also don't understand what you mean by "when is having cycles a problem". Those sound very broad and open-ended, which aren't a good fit here (see our help center). Can you narrow your question down to something specific, answerable in a paragraph or two, and objective? What is the context? What kind of problem are you trying to solve? $\endgroup$ – D.W. Apr 10 '18 at 16:28
  • $\begingroup$ We expect references to fulfill the minimal scholarly requirements and be as robust over time as possible. Please take some time to improve your post in this regard. We have collected some advice here. Thank you! $\endgroup$ – D.W. Apr 10 '18 at 16:29
4
$\begingroup$

Let me mention one thing which is absent in the other answers: DAGs actually occur in applications. For example, a Boolean circuit is an ordered DAG whose vertices are labeled by logic gates. Dependencies of various sorts, like prerequisites for different parts of a project, also form a DAG. Wikipedia has many other examples.

Some problems can only be stated for DAGs. For example, topological ordering only makes sense for a DAG. Other problems can be solved faster on a DAG due to its restricted nature. This suggests studying algorithms on DAGs. For similar reasons, there is a lot of literature on algorithms for planar graphs – another naturally occurring class of graphs on which some algorithms run faster.

$\endgroup$
  • $\begingroup$ Thanks this helps a lot. I didn't realize Boolean circuits are DAGs, since it seems they would have cycles/loops (I don't know much about circuits). Random paper (authors.library.caltech.edu/26130/1/etr099.pdf) "The accepted wisdom is that such circuits must have acyclic (i.e., loop-free or feed-forward) topologies. In fact, the model is often defined this way – as a directed acyclic graph (DAG)." $\endgroup$ – Lance Pollard Apr 10 '18 at 21:52
  • $\begingroup$ Sometimes you might have a cyclic dependency, in which case it usually throws an error :) $\endgroup$ – Lance Pollard Apr 10 '18 at 21:54
  • $\begingroup$ I wonder if there's anything on "partial topological sort", because say $x$ is a loop and you have $a \rightarrow x \rightarrow b\dots$ maybe you could just say "$x$ is a chunk, so treat it as a supernode, and use that in the ordering", since in the end $b$ is after $a$ eventually. $\endgroup$ – Lance Pollard Apr 10 '18 at 22:03
  • $\begingroup$ There's the DAG of strongly connected components. $\endgroup$ – Yuval Filmus Apr 10 '18 at 22:07
2
$\begingroup$

First, you're drawing overly broad conclusions from one sentence. Just because that one paper happens to look at DAGs doesn't mean you should conclude that scholarly papers focus on DAGs instead of general directed graphs.

Why are some graph problems harder when you have to deal with cycles? Because acyclic graphs are promised to have no cycles, whereas general graphs either might have graphs or might not. As a consequence, in the latter case the algorithm will have to deal with both situations, whereas in the former case the algorithm only has to deal with one of the two situations.

Finally, the most significant reason: DAGs can be ordered. You can topologically sort them, to put the vertices in a particular order. Many problems become simpler to solve. Not all, but many of them. The best way to understand why is to study some examples on your own: say, how to find shortest paths in a general undirected graph vs a dag.

$\endgroup$
1
$\begingroup$

The advantages you get is that you can order vertices and facilitate searches in graphs and finding strongly connected components.

You may find more information in the excellent "Algorithms" (Papadimitriou, Dasgupta, Vazirani) at http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-Vazirani.pdf page 96.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.