On Tue, 2007-10-30 at 16:04 -0700, Stefan O'Rear wrote:
On Tue, Oct 30, 2007 at 10:45:34PM +0000, Duncan Coutts wrote:
On Fri, 2007-10-26 at 10:48 +0000, Duncan Coutts wrote:
So what's next...
We want to write some specifications
Spencer, Lennart, Thomas and I had a joint hacking session in which we made some progress on this issue today. Specifically we can now generate random dep graphs for use in QuickCheck tests. For example:
http://haskell.org/~duncan/cabal/foo.svg
We can tune the size and 'density' of these graphs. As you can see we get cycles in the graphs. We'll have to filter out cycles. Any suggestions on a simple way to do that? It's ok to depend on Data.Graph for this kind of test code.
It is a well known result in the theory of graphs that any directed graph admits a topological ordering. Thus, you could simply arrange to only generate edges from nodes to previously-created nodes. Although this would change the distribution of shapes somewhat.
Wouldn't that mean we can only get trees (instead of DAGs)?