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.