On Wed, Oct 31, 2007 at 12:23:37AM +0100, Thomas Schilling wrote:
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)?
No. (1,2 with (1,2) and (1,2) as edges, fex) Stefan