Re: converting from directed graph to directed acyclic graph

[Stefan Balev <stefan.balev AT gmail.com>]

Well, in case of directed graphs on can just ignore arc direction. That is exactly what GraphStream implementations of Kruskal and Prim do. Applying one of these to your DG and then removing the edges not belonging to the tree, you obtain a DAG containing the same set of vertices and a subset of arcs.

Best,

--

Stefan

2014-02-15 0:17 GMT+01:00 Haluk Dogan <hlk.dogan AT gmail.com>:

I want to keep some arcs. I have a directed graph, so spanning tree works on undirected graphs, right?

On Fri, Feb 14, 2014 at 4:09 PM, Stefan Balev <stefan.balev AT gmail.com> wrote:

Hi,

It depends. What kind of relation between the original and the "converted" graph you want to obtain?

If you want to keep the same set of vertices, a trivial solution consists in deleting all arcs :)

If you want to keep some arcs, maybe a spanning tree is what you want?

Best,

--

Stefan

2014-02-14 22:51 GMT+01:00 Haluk Dogan <hlk.dogan AT gmail.com>:

Hi,

How can I convert my DG to DAG?

Thanks.

--
HD

--
HD