Wanted: Minimal spanning tree for a DAG.

Topics: algorithm
Aug 2, 2012 at 2:13 AM
Edited Aug 2, 2012 at 2:34 AM

Over 30 years ago I attended lectures on combinatorics so my knowledge is a bit rusty and probably out dated.

I'm using QuickGraph to compute software component build dependencies for a large software project.  I'm already using a topological sort to determine the build order (thanks!).

I'd now like to reduce the number of dependency edges. I think I need a minimal spanning tree for this but the QuickGraph library appears to only support undirected graphs (right?) and mine are directed (usually a connected DAG actually).

Any suggestions for how can I proceed?

Thanks for QuickGraph!

P.S. I'm using QuickGraph 2.0 at the moment .. but I can switch to 3.0 if needed.

Note my graph would have a maximum of a 200 vertices so I can wear the cost of a slower algorithm.