proptotype of make style dep stuff

[Stefan O'Rear]

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.

Stefan
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
Url : http://www.haskell.org/pipermail/cabal-devel/attachments/20071030/63e947fc/attachment.bin