On Tue, 27 Mar 2018, James E Keenan wrote:
Date: Tue, 27 Mar 2018 15:17:59 +0200
From: James E Keenan <jkee...@pobox.com>
To: cpan-workers@perl.org
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 penn...@uu.nl \_/