proptotype of make style dep stuff

[Stefan O'Rear]

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
-------------- 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/75e77f67/attachment.bin