## Re: [jgrapht-users] converting directed graph to directed acyclic graph

 Re: [jgrapht-users] converting directed graph to directed acyclic graph From: H.N. de Ridder - 2014-02-15 10:01:39 ```On Fri, Feb 14, 2014 at 03:43:24PM -0600, Haluk Dogan wrote: > I want to convert my directed graph to directed acyclic graph. I know > Feedback Vertex Set algorithm can do this. However, I couldn't see its > method in jGrapht. Can you describe more precisely what you mean by 'convert' and for which purpose? Add edges? Remove edges? Reorient them? Remove vertices? Any minimality constraints? Regards, Ernst -- Information System on Graph Classes and their Inclusions (ISGCI) http://www.graphclasses.org ```

 [jgrapht-users] converting directed graph to directed acyclic graph From: Haluk Dogan - 2014-02-14 21:43:30 Attachments: Message as HTML ```Hi, I want to convert my directed graph to directed acyclic graph. I know Feedback Vertex Set algorithm can do this. However, I couldn't see its method in jGrapht. Is there any other way to do this by using jGrapht? Thanks. -- HD ```
 Re: [jgrapht-users] converting directed graph to directed acyclic graph From: H.N. de Ridder - 2014-02-15 10:01:39 ```On Fri, Feb 14, 2014 at 03:43:24PM -0600, Haluk Dogan wrote: > I want to convert my directed graph to directed acyclic graph. I know > Feedback Vertex Set algorithm can do this. However, I couldn't see its > method in jGrapht. Can you describe more precisely what you mean by 'convert' and for which purpose? Add edges? Remove edges? Reorient them? Remove vertices? Any minimality constraints? Regards, Ernst -- Information System on Graph Classes and their Inclusions (ISGCI) http://www.graphclasses.org ```
 Re: [jgrapht-users] converting directed graph to directed acyclic graph From: Haluk Dogan - 2014-02-15 13:05:23 Attachments: Message as HTML ```Say I have a directed graph. I actually want to convert it to Bayesian Network which requires DAG. Even though, removing edges breaks the dependency relation of nodes, it is OK for this phase of my analysis. I'll do the same with Spirtes method later on. Adding, removing, reorienting edges are fine. But I can not remove vertices. Thanks. On Sat, Feb 15, 2014 at 3:45 AM, H.N. de Ridder wrote: > On Fri, Feb 14, 2014 at 03:43:24PM -0600, Haluk Dogan wrote: > > > I want to convert my directed graph to directed acyclic graph. I know > > Feedback Vertex Set algorithm can do this. However, I couldn't see its > > method in jGrapht. > > Can you describe more precisely what you mean by 'convert' and for which > purpose? Add edges? Remove edges? Reorient them? Remove vertices? > Any minimality constraints? > > Regards, > Ernst > > -- > Information System on Graph Classes and their Inclusions (ISGCI) > http://www.graphclasses.org > > > ------------------------------------------------------------------------------ > Android apps run on BlackBerry 10 > Introducing the new BlackBerry 10.2.1 Runtime for Android apps. > Now with support for Jelly Bean, Bluetooth, Mapview and more. > Get your Android app in front of a whole new audience. Start now. > > http://pubads.g.doubleclick.net/gampad/clk?id=124407151&iu=/4140/ostg.clktrk > _______________________________________________ > jgrapht-users mailing list > jgrapht-users@... > https://lists.sourceforge.net/lists/listinfo/jgrapht-users > -- HD ```
 Re: [jgrapht-users] converting directed graph to directed acyclic graph From: H.N. de Ridder - 2014-02-15 15:00:48 ```On Sat, Feb 15, 2014 at 07:05:16AM -0600, Haluk Dogan wrote: > Say I have a directed graph. I actually want to convert it to Bayesian > Network which requires DAG. Even though, removing edges breaks the > dependency relation of nodes, it is OK for this phase of my analysis. I'll > do the same with Spirtes method later on. > > Adding, removing, reorienting edges are fine. But I can not remove vertices. So minimality is not required? A useful heuristic when creating a DAG for drawing is reversing back edges in a DFS traversal, see for example the description of the GraphViz algorithm. It's easy to implement and quick, you might try how to performs for your application. Another idea is using one of the algorithms in org.jgrapht.alg.cycle to collect all cycles and remove an edge from each one. Regards, Ernst -- Information System on Graph Classes and their Inclusions (ISGCI) http://www.graphclasses.org ```