Data structure and algorithms for a directed cyclic graph (F#)

Question

I'm trying to analyse an application where the assembly references should be a directed-acyclic-graph, but aren't. There is also a related problem of sub-assemblies referencing different versions of one sub-sub-assembly (think Escher...)

What I want to do is analyse each assembly-subassembly pair and build up a picture of where things are wrong.

I need some guidance on what would be a good data structure for this. I'm not too sure that I can build up an immutable one, but I don't mind having it mutable internally then transformed to immutable at the end.

The other part of the question is what kind of algorithms I should use for filling the data structure, and also afterwards for 'analysing' the problems.

Answer 1

You can just use NDepend, it analyzes your assemblies and detects dependency cycles.

If you really want to do this yourself, I'd use QuickGraph to model the dependency graphs, it also includes graph algorithms, like topological sort.