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

What you want to do is called "Topological sorting". Wikipedia has a good overview:

http://en.wikipedia.org/wiki/Topological_sort

Answer 2

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.

Answer 3

I don't mind having it mutable internally then transformed to immutable at the end.

You may well find it easier to use immutable data structures throughout. In particular, you can easily represent a graph as a Map from source nodes to sets of destination nodes. For a topological sort, you want efficient access to the source nodes of a destination node so you may want to augment your graph with another Map going in the opposite direction.

I just implemented this in F# and the topological sort is just 12 lines of code... :-)