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", "luaopen_libdebgraph") libdg() LoadPackages('cache') -- '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 .. " " end print("* " .. comp_nodes) end
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).