Planet SoC

Yesterday, 10 July, was the due date for the second
milestone of my work on DebGraph. I am happy to report that
we are roughly two weeks ahead of schedule, so meeting this
milestone was not a cause for worry.

We now have support for the following graph operators:

• Difference

• Intersection
• Filter (by properties)
• Find Cycles (via Tarjan’s
  algorithm)

• Find Dependencies
• Find Reverse Dependencies
• Symmetric Difference (XOR)
• Union

The next milestone includes the development of a high-level
language (or integration with an existing extension
language) that streamlines the construction of complex
queries using the operators listed above. We can build
arbitrarily complex queries using the C++ operators, but
dealing with the static typing and compiler toolchain can be
very clunky. As such, I have spent the past week working on

The overall situation (admittedly a bit of a stretch):



(The soil depends on the chicken to keep it fertilized.
Work with me here.)

There are an infinitude of cycles that could be extracted
from this, but we’re only interested in the set of
shortest-length cycles.

Exhibit A:

Exhibit B:

And the classic philosophical gem, Exhibit C:

The GNU C library (packaged as libc6 in
Debian) is the bedrock of a lot of code. What are the
packages that it depends on? (Yo, DebGraph!)

Original
image [997 kB]

libc6 is one of the well-connected vertices in the
lower-left corner (third quadrant, if you like). For graphs
like this one, we would like DebGraph to identify dependency
cycles (loops). For example, libc6 depends on
libgcc1, which in turn depends on libc6.
This can be seen in the graph above by applying some careful
scrutiny, but why not let the computer work its magic for
us? (To be continued.)

As a bonus, who depends on arping 2.05-2 for i386?

The roadmap for DebGraph outlines three sets of graph
operators: essential, useful, and
exotic. Naturally, each successive set extends the
previous set’s functionality, and in many cases the
complexity of the work performed by the operators increases
accordingly.

Over the weekend, I wrapped up work on the
essential operators and separated the unit test
suite into its own subdirectory and executable. Having a
few simple operators around means that we can do basic queries:

• Show me all 3dchess packages.
  
  

• Show me all all libc6 packages.
  

Last week I bought a Netgear WG511 wireless adapter for my
laptop, intending to replace the archaic prism2-based
adapter that didn’t support WPA and barely worked. Initial
searches indicated success in making it work with Linux, so
I wasn’t worried.

It turns out that there are at least three different
versions of this card, each with a different chipset, and
the only clear delineation is the “Made in X” label on the
adapter, where X is either “China” or “Taiwan”. My WG511
was made in China and has a Marvell chipset. Among other
things, this means that I’m forced to use
ndiswrapper and the Windows 2000 drivers. (The
adapters made in Taiwan are natively supported by the
prism54 driver included with the Linux kernel.) Okay,
fine, I thought. It’s not ideal, but the adapter is
popular enough that maybe development of a native
Marvell
driver is
underway.

This summer, I’m working on DebGraph
(for Debian, as part of GSoC) with Robert Lemmen. Below is a
brief description of where we’re headed.

DebGraph is a tool that provides a simple, intuitive
interface to the Debian package graph. The package graph
contains information about packages (name, version,
description, etc), their dependencies, and other useful
details. By providing an easy way to interact with this
graph, DebGraph enables useful analyses that can identify
interesting or problematic constellations.

As an example, it is helpful for the Debian QA team to track
cyclic dependencies (that is, packages that [in]directly
depend on themselves). Such dependency cycles can be
symptoms of package problems, and therefore it is important