Quantcast

converting directed graph to directed acyclic graph

classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

converting directed graph to directed acyclic graph

Haluk Dogan
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

------------------------------------------------------------------------------
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
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: converting directed graph to directed acyclic graph

H.N. de Ridder
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
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: converting directed graph to directed acyclic graph

Haluk Dogan
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 <[hidden email]> 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
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users



--
HD

------------------------------------------------------------------------------
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
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: converting directed graph to directed acyclic graph

H.N. de Ridder
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

------------------------------------------------------------------------------
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
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Loading...