9

I want to convert a cyclic graph into an acyclic graph. Is there an pseudocode that can do this? I did try to search but most of them returned where mathematical based on markov chain or research articles.

I want to write a program to do it and any directions will be useful. for example consider this below graph.

A->B
B->C
C->A

I saw a solution in an MIT lecture but the lecture skimmed over it with reference to something taught earlier and couldn't catch it. In short it kind of replicates the nodes in layers in a way that the end graph denotes a DAG but conveys the same path information.

[See 46:59]

https://www.youtube.com/watch?v=OQ5jsbhAv_M Edit: There is an explanation of turning cyclic graphs into dags in this MIT recitation at 36:57 https://youtu.be/IFrvgSvZA0I

Se also Wikipedia : cycle and forest Edit:

I want to apply dynamic programming over a problem which is a cyclic graph e.g) say shortest path problem Delta(S,D) where S-> Source node and D->Destination node. Since DP over cyclic graph is infinite algorithm, we first need to convert the cyclic graph into acyclic graph and then apply the dynamic programming technique over it.

Aubin
  • 14,617
  • 9
  • 61
  • 84
Dexters
  • 2,419
  • 6
  • 37
  • 57
  • 2
    What do you mean by converting a cyclic graph into an acyclic one? Finding a maximal spanning forest? Something else? Maybe the meaning of your question is in the linked video, but questions on s-o are ideally self-contained, so perhaps you could include relevant details in the text of the question? – Paul Hankin May 15 '16 at 10:13
  • @PaulHankin I have added a few comments, not sure if that clarifies enough. – Dexters May 15 '16 at 23:32

1 Answers1

1

I believe you pointed out the wrong video, here it is (46:59): https://www.youtube.com/watch?v=OQ5jsbhAv_M

The idea exposed here, is to make several copies of the graph and to arrange them into layers. Each one represents the state of the graph at a given time, and for every edge traversed you go down by one layer. I did not find pseudo-code for this, but the way of doing this is detailed here: https://cstheory.stackexchange.com/questions/14591/combinatorics-of-bellman-ford-or-how-to-make-cyclic-graphs-acyclic

Community
  • 1
  • 1
T. Claverie
  • 11,380
  • 1
  • 17
  • 28
  • Thakns. I thought that question was not answered as well. Will check that again. – Dexters May 15 '16 at 23:35
  • what i don't understand about that lecture is that he puts v in the second slot. shouldn't it be in the third slot? – frei Feb 07 '21 at 10:50