Re: Is the CPAN river always a DAG?

On Tue, 27 Mar 2018, James E Keenan wrote:

> Date: Tue, 27 Mar 2018 15:17:59 +0200
> From: James E Keenan <[email protected]>
> To: [email protected]
> Subject: Is the CPAN river always a DAG?
> 
> A few weeks ago I made a presentation to the Philadelphia Perlmongers 
> (http://thenceforward.net/perl/talks/phlpm20180312/index.html) on the subject 
> "Testing CPAN against the Perl 5 Core Distribution:  Where Do We Stand?".  In 
> that presentation, I sketched the concept of the CPAN river and described it 
> as a directed acyclic graph (DAG) 
> (http://thenceforward.net/perl/talks/phlpm20180312/slide017.html), using one 
> of Neil Bower's images to make that point.
>
> In the discussion afterwards, a prominent former COBOL programmer suggested 
> that there was nothing to exclude the possibility of circular dependencies 
> among CPAN distributions.  A could depend on B, which depends on C, which 
> depends on A.  If so, we would have a cyclic graph. Wouldn't that undermine 
> the concept of the CPAN river, he asked.
>
> Since all I know about DAGs I got from reading Wikipedia and the 
> documentation to Jarkko's Graph.pm module, I didn't have a good response.  So 
> I promised to ask the question here.
>
> * Can CPAN be cyclic?

   Yes ; considered as a graph, CPAN has points (modules),
   and links from point A to point B iff A uses B.
   Given a set of modules, any graph is possible.

   It is not hard to find a cycles, if (at least one) exists ;
   but if you find a cycle, it is (a priori) not clear how to break it.

> * If so, then does that mean that, when we speak of CPAN as a river, we are 
> *imposing* DAG-ness on it by means of the algorithm(s) with which we 
> calculate the river (e.g., https://github.com/dagolden/zzz-index-cpan-meta)?

   You can always make a DAG of CPAN, by leaving out links
   (dependencies) or points (modules).
   It is not so easy to find a minimal set of links to leave out.

> Jim Keenan

   Regards,

   Henk Penning

------------------------------------------------------------   _
Henk P. Penning, ICT-beta                 R Uithof MG-403    _/ \_
Faculty of Science, Utrecht University    T +31 30 253 4106 / \_/ \
Leuvenlaan 4, 3584CE Utrecht, NL          F +31 30 253 4553 \_/ \_/
http://www.staff.science.uu.nl/~penni101/ M [email protected]     \_/