11 Jul 2008 acj   » (Observer)

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 Lua bindings for DebGraph, which will enable us to query the graph of Debian packages from a clean, dynamically typed language. Lua has a powerful C API that exposes the Lua stack and lets us move DebGraph information to and from the Lua interpreter. I'm writing documentation that outlines how to use DebGraph from both C++ and Lua in order to make this work accessible to more folks.

Sneak peak
As an example, we can utilize the FindCycles operator in Lua as follows:

libdg = package.loadlib("./libdebgraph.so",
-- 'g' is the main graph of unstable binary-arm packages
cycles = FindCycles(g)
print("Found " .. #fc .. " cycles")
for comp_key,comp in pairs(cycles) do
    comp_nodes = ""
    for node_key,node in pairs(comp) do
        prop = GetProperty(node, "Package")
        comp_nodes = comp_nodes .. prop .. " "
    print("* " .. comp_nodes)

The above Lua script produces the following result:

reading cache/unstable/main/binary-arm/Packages
Found 61 cycles
* debconf-english debconf-i18n debconf
* perl-modules perl 
* cdebconf fontconfig-config fontconfig gsfonts-x11
libcairo2 libfontconfig1 libgtk2.0-0 libpango1.0-0
libpango1.0-common libxft2 ucf x11-utils xutils

These are the package names in the strongly connected components, shown in alphabetical order.

There is still a lot of work to do before the Lua binding will achieve feature parity with the core library, but we have now laid the foundation (and a brick or two).

Latest blog entries     Older blog entries

New Advogato Features

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

Keep up with the latest Advogato features by reading the Advogato status blog.

If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!