About a week ago, I wrote about doing cross package checks in Lintian.  At that time I had only played with looking up manpages in direct dependencies, which I hope will greatly improve the current binary-without-manpage stats (around 677 packages and 2750ish tags incl. overrides).

Today, I decided to take on another challenge.  Detection of circular dependencies between binary packages (created from the same source).  We already have a little library for building dependency relationships; however I ended up not using it, since it has an important limitation.  It cannot tell how the circular dependencies relate to each other.

Let me demonstrate what I mean with an example.  Suppose we have a couple packages that depend on each other like this:

pkg-core => pkg-A, pkg-D # circle 1: A, B, C pkg-A => pkg-B pkg-B => pkg-C pkg-C => pkg-A

In this case, our current tool will be able to tell that all packages (possibly except root - I did not check) are in a circular relationship. However, we can find better results by pretending we are trying to find Strongly Connected Components (actually that is exactly what we are trying to do here).

So today, I implemented Tarjan's algorithm in Perl to solve this particular issue and committed it to my Lintian branch. If this branch is merged into the Lintian master branch, we can close #316283.