I've added an implementation of my new quadratic-time partial cube recognition algorithm to PADS, replacing a theoretically-slower algorithm for the same purpose that was already there.

The labeling phase of the algorithm, as described in my new paper, is recursive, possibly with Ω(n) levels of recursion, and Python doesn't necessarily handle deep recursion well, so I replaced that part of the algorithm with an iterative version using union-find to keep track of the edge equivalences. I also added some new modules: Medium.py handles the media-theoretic side of the algorithm (the part where we find shortest paths between all pairs of vertices), and BFS.py is a new breadth first search routine (I previously had LexBFS.py, which generates a breadth first traversal order of the vertices in a somewhat complicated way, but in this algorithm I needed the sequence of subgraphs connecting each BFS level to the next level). I also checked in a module I'd written some time ago: GrayGraph, a description of the Gray Graph, a cubic bipartite graph that looks a lot like a partial cube but isn't (so making an interesting test case for my new code).

The implementation ended up being rather more complex than I was hoping: including unit tests, comments, etc., Medium and PartialCube together now have 588 lines. The unit tests were very helpful in shaking the bugs out of the Medium side of the implementation, and (though surprisingly to me the PartialCube side worked correctly the first time) in making me confident of the correctness of that part as well.

I have a new paper on arxiv today, Recognizing Partial Cubes in Quadratic Time. The previous time bound (for an n-vertex m-edge graph) was O(mn); this paper improves it to O(n²) via a combination of bit-parallelism and a fast all-pairs shortest path algorithm I'd previously written about.

Although the new paper is written mostly in the terminology of graph theory, in order to make sense of the shortest path part I needed to import some terminology from media theory, a way of looking at structures equivalent to partial cubes in terms more closely related to finite state machines. Media theory was initially developed by my UCI colleague in social science, Jean-Claude Falmagne, for applications including modeling voter preferences and states of knowledge of human learners; I've been working with Falmagne and Sergei Ovchinnikov on a monograph describing this theory. I have to view this new result as a success for the media theoretic viewpoint, as I think that viewpoint was crucial in coming up with the shortest path component of the algorithm.

(The previous paper, "Algorithms for media", has a mildly convoluted history, by the way: after failing to interest my fellow algorithms researchers in its results, I presented it at a mathematical social sciences conference, the International Conference on Ordinal and Symbolic Data Analysis (OSDA), held at UCI in 2003, but that conference didn't have a proceedings; instead, there was a special issue of a journal devoted to the papers from the conference, to which it was submitted and duly accepted. But then the journal's editor died, and the complications from the resulting backlog have led to a situation where it may be another two years before the special issue actually appears...)

Probably a lot of people know about the tricks in HAKMEM for counting the number of nonzero bits in a machine word. And that in practice it's probably best to avoid multiplication, and either repeatedly remove the lowest nonzero bit with x &= x-1 (if few nonzeros are expected, as in bitboard chess programs) or do a table lookup on longer blocks of bits.

So what follows is not likely to be especially useful.

( Read more... )