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

[H.N. de R. <hnr...@gr...>]

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