The First Tangible

I have the preliminary pleasure to announce the first more or less tangible fruits of my work: some real diagram plots. I will adjourn this part of the show-off until the end of the post, however, so that more people read the whole thing :-)

The work I have done this week belongs to two essentially different classes. In the first half of the week I was still adding new features to the layout functionality; this is mainly about logical groups, which are a way for the user to exercise some control over how the objects are laid out. The idea behind offering the user some control over the layout is that DiagramGrid cannot always guess which placement of objects would be the best for the user, additional input would be very welcome on such occasions. It was important though to require this input in such a way as to demand as little effort as possible on the part of the user.

Take a look at the definition of a pullback. In this diagram, one can easily see that the objects P, X, Y, Z are distinctly separated from the object Q. It is easy to note further that many of universal properties also rely on such semantic grouping of objects. Further yet, in a lot of diagrams, logical groups are easily seen, as it happens in the case of the five lemma. These observations have made me think that allowing logical groups would be a perfect addition to the existing automatic layout functionality.

In the current implementation, the user specifies the logical groups by supplying a set of sets of objects. Thus, in the case of the five lemma, the user can supply the set \{\{A, B, C, D, E\}, \{A', B', C', D', E'\}\} as the description of the groups that can be seen in the diagram. In the case of the pullback, the following set would be a valid specification: \{Q, \{P, X, Y, Z\}\}. Note how it is not necessary to include separate objects in singleton sets.

One more detail on how the groups are handled, about which I am not yet very sure, both in the meaning of utility and test completeness, is that groups can be nested to arbitrary depth. This is because the current procedure of handling groups is as follows: all supplied elements of the supplied set of groups, which are sets, are considered as diagrams in their own right and are laid out. The algorithm does not really look into the structure of such a group before going into recursion. After having laid out each of groups, the current implementation constructs a dummy diagram, starting from the original one in the following way. The new diagram has as objects all objects and groups included in the groups set. If between the objects of any two groups there exists a morphism, it is added to the new diagram. Duplicate morphisms of this kind are essentially omitted for efficiency reasons. This new dummy diagram is laid out. Then, in the resulting grid, the cells (and the respective rows and columns) which correspond to groups are expanded to hold the grids into which the groups have been laid out.

The procedure I describe is rather simple, which makes me believe that it is also robust. Nevertheless, I cannot say I am fully satisfied with how much I have tested it; somewhat pessimistically, I do expect quite a number of bugs.

While logical groups seems to a be rather powerful feature already, it does not help get the layout of the five lemma just like it is usually laid out. Moreover, I noticed that the current algorithm would never lay out a line diagram in a line. To avoid this I have added a hint to the layout functionality which would instruct the usage of a different layout algorithm, and which would result in a more line-like shapes. This algorithm essentially does a depth-first traversal of the underlying undirected graph of the diagram and places the objects according to their distance from the root. Now, since I wanted to see such a layout applied to some logical groups as well (cf. the five lemma), I have implemented the possibility to supply separate layout hints for each group. With these instruments at hand, as well as with the simple hint transpose which instructs the layout engine to eventually flip the grid about its main diagonal, it is possible to give DiagramGrid sufficient information to have the five lemma laid out properly.

While I think that this result is pretty satisfactory, it would of course be way cooler to have DiagramGrid guess such stuff automatically. It is a rather nontrivial task, however. Take the five lemma, again. It can be laid out in a line, and look not that bad. It seems very hard to decide automatic criteria to answer such questions. Yet, I expect that nice results can be achieved by diversifying the controls offered to the user in what concerns the layout.

I am also considering the possibility of a partially manual layout (and, eventually, a fully manual one), by specifying the exact initial positions of some of the objects. I believe this would be very useful in the long run, because it would offer a great deal of control, and wouldn't still require much unnecessary effort on the user side. The implementation of such a thing is however still a matter of the future.

I have finished the first half of the week by documenting the layout algorithm in the source itself, as well writing proper docstrings for DiagramGrid and its methods.

The second half of the week I have spent working on producing actual Xy-pic code. As expected, the most difficult part lied in drawing bent arrows. I have implemented some basic routine to solve this question. The pinnacle of the currently available functionality is shown in the figure.

The automatic plot of a moderately complex diagram

There is a bit of work left, however. First of all, notice how the arrow curving from A_7 to A_8 is too close to the objects it passes by. I plan to solve this by increasing the default amount of curving. Further, nothing will currently be done if another morphism between these two objects is added, which results in ugly overlaps. Yet another important problem is positioning of the labels of the morphisms: some of them are too loose in space and it is hard to understand which arrow they belong to. The label f_{10} is even crossed by the arrow f_7. Unfortunately, I don't expect to solve all of these problems with positioning of morphisms labels, because, in many cases, it would be necessary to know the actual graphical information, which is impossible at the current level of abstraction.

Thus my immediate plans are to fix the problems I have enumerated to as a complete extent as possible, and to then submit the layout functionality and the actual drawing functionality as two pull requests, to facilitate review.

About these ads

6 responses to “The First Tangible

  1. It seems to me that the main elegance in the usual layout of the five lemma is that A lines up with A’, B lines up with B’, and so on. Maybe this concept could somehow be abstracted. Or maybe it’s just necessary to group {A, A’}, {B, B’}, …

    • Yes, that is right, about the elegance. It would be cool if the algorithm could detect that automatically.

      At present, you can achieve the proper layout by grouping {A, B, C, D, E} and {A’, B’, C’, D’, E’} and playing around with layout hints.

      • You mean detect that by the names themselves? I’m not sure if that’s a good idea (it would have to be *very* heuristic and could lead to a lot of false positives and unexpected behavior).

        Or is there some structure in the morphisms that could lead it to that conclusion?

      • I would very much refrain from relying on names at all, and you have stated the reasons. Frankly, I don’t really have any precise approach to get the things like the five lemma laid out totally automatically in the desired way; I’d feel inclined to doubt that such a generic approach existed at all, given the fact that typesetting is very often guided by aesthetics.

        I did muse over strategies like detecting some line-like patterns in the diagram; however, I’m not sure how to do that properly even for the five lemma.

  2. You should not tie your interface design to the implementation. Just because your current algorithm supports arbitrary nesting of logical groups, is it a good idea to expose this in the user interface? In principle, any new algorithm will have to implement this … (though of course we can remove it if there is no release in between).

    • The point is that, at the moment, arbitrary nesting of groups is a side-effect rather than a specially designed feature.

      The way the things work now, I believe a lot of new stuff could be added without having to be wary of recursion. I believe the connection between different levels of recursion is minimal at the moment. On the other hand, getting a feature to work with groups is a nice way to test how it works generically.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s