I haven’t posted in quite some time, because I have been totally absorbed by implementing the functionality to lay out diagrams. I am painfully close to having finished it; however, I’ve been that close to it for a couple days already, and that’s something which drives me crazy 
OK, it’s time to take a general look over what has been done. In the end, I will describe my short-term further plans a bit.
First of all, the goal. When you want to lay out a (commutative) diagram, you should really aim at grid layout. This is how people normally typeset diagrams in articles, and this is the thing the semblance of which I would be happy to achieve. The resulting grid layout is one of the traits of diagrams which make the task of automatically drawing them different from the task of automatically drawing a graph. The other specific feature is that, when you get a diagram, you can (and you should) actually throw away those morphisms which are not really interesting. In the following sections, I will try to describe the philosophy behind the functionality I have implemented, for each bit in part.
The first stage of the algorithm is to remove the uninteresting morphisms. At this stage, those composite morphisms which have no properties are discarded; identity morphisms without properties are discarded as well. In fact, this corresponds pretty well to how people draw diagrams. This first stage ends by merging the premises and the conclusions of the diagram into a single container. This is because, at drawing, the distinction between premises and conclusions is not important at all, since all interesting morphisms should make their way into the final picture.
At the second stage, the algorithm abstracts morphisms away, in favour of unoriented edges between objects. The code builds the so-called skeleton of the diagram (that’s an ad-hoc name). The skeleton is a graph which has all objects of the diagram as vertices. Between two vertices of the skeleton there is an undirected edge, if these objects are connected by an (interesting) morphism. Notice how we discard the direction of the connection. After all edges corresponding to morphisms have been added, the skeleton is further completed in the following way. An edge is added between any two objects 
The next stage is the first key stage of the algorithm. The skeleton is tesselated into triangles, which will eventually be used to get as many right angles in the layout as possible. Here is when the dummy edges come into play. Their presence assures that the diagram can be completely split into triangles. For those who have read my proposal, I will remark that all the stages of diagram analysis I described after laying out the triangles are actually unnecessary, namely because of these dummy edges, which guarantee that we have sufficiently many triangles. Yet, dummy edges are indeed dummy, in the sense that most of them will not appear in the final diagram. This makes the triangles we find in the skeleton unevenly interesting to us. Triangles which have more than one dummy edge are totally extra, because they would distract the attention of the code from triangles with more meaningful edges and would mess things up, generally. Therefore, such triangles are immediately dropped.
Once the “triangulating” stage is complete, the core of the algorithm comes into play. Basically, the idea is to pick one of the triangles, pick one of its edges and put it on a grid, horizontally, remembering that it is in the fringe. Then, iteratively, “weld” interesting triangles to the fringe, eventually placing all objects of the diagram on the grid. This part is the trickiest part of the whole algorithm, so prepare to hear a talk about a lot of magic
Any triangle is placed on the grid as a right-angled triangle, with the perpendicular edges being horizontal and vertical. This assures that we keep “quite” close to the desired grid layout. Whenever a triangle is placed on the grid, the objects which form its vertices are recorded as already placed. Then, those triangles which only contain objects which have already been placed (uninteresting triangles) are dropped. That is, once the places of some objects are decided, those objects are never considered again. This may constitute a point of future improvement, of course, because objects are often drawn in several copies to make the diagram look clearer.
When placing the triangle on the grid, the code attempts to assure that as many interesting (not dummy) edges as possible will be drawn horizontally or vertically. There is some dark magic in the code which detects such situations, but I hope that after following the trail of comments and just reading the code itself, the whole thing should become rather clear.
Now, since the algorithm is essentially greedy, there can be situations when all edges to which the remaining triangles could have been welded, have already been positioned inside the structure and it is now impossible to find the welding edge. In this case, the algorithm attempts to attach a triangle to the existing structure by a vertex only. If such a possibility is found, an edge (the pseudopod) of the triangle is placed as vertically (or horizontally) as possible and then the welding process can be continued, since there already is a welding edge.
Let’s now focus on what happens to the fringe. When a new triangle is welded, the two new edges are added to the fringe. No edges are deleted however, because the welding edge might still have some free space to its other part. Edges are deleted from the fringe only when they are detected as possible welding edges, but when the algorithm finds that there is no space around them actually. I have considered several possibilities of correcting the fringe on different occasions; my conclusions so far have been that it’s not generally worth it, performance-wise. This question however should be better investigated, including doing some complexity analysis.
You might have noticed that I do not in any way treat the situation when a pseudopod cannot be grown. I have not encountered such situations during the testing yet, so I decided not to attempt to handle them before I have actually seen an example. Taking into consideration that I am going to work with diagrams rather intensively later, if such situations are possible, I will indeed run into them. I must confess that I haven’t considered the problem theoretically yet, though
The description of the essential parts of the algorithm is complete here, so I’m passing over to the overview of the remaining problems and further short-term plans.
Tom Bachmann, my mentor, has suggested that I describe the steps of the algorithm in the docs which come with the source code. I will do this shortly. I believe it is essential to write such documentation as soon as possible, despite the abundant (hopefully) comments in the code.
My immediately next task is, however, producing the actual Xy-pic code. I expect that getting this done at a basic level shouldn’t be hard. However, drawing longer morphisms and avoiding intersections for as much as possible may prove a rather hard task to achieve.
Oh, and the almost forgotten conclusion: I now essentially have the core of the automatic diagram plotting functionality, since laying out objects is the most difficult part of the affair.
