The Polish and Further Planning

I am currently working on getting my two pull requests into master. Right now, the efforts have been concentrated on the first pull request, concerned with diagram layout. Among the minor fixes, there came a number of more important changes, which I am going to shortly describe in this post, before I get to my further plans.

Among the changes worth mentioning are some updates to the choice of internal data structures of DiagramGrid. Previously, FiniteSet was used to store any sets. Following my mentor’s suggestion, though, I have refactored the code to only use FiniteSet when something needs to be stored in Basic.args. On all other occasions, the built-ins set and frozenset are used, depending on whether a mutable set or an immutable hashable container is needed.

The other change bearing no fundamental importance but still worth mentioning is the transition to storing undirected edges as two-element frozenset‘s. Previously, edges were stored as two-element tuples which caused a bit of hassle in what concerned recognizing the equality of (A, B) and (B, A). The choice of frozenset has brought in more elegant code. In terms of performance, I do not think that this transition has had a really important impact, since I didn’t really keep performance in mind when writing other parts of the code anyway. (I am mainly referring to the construction of the skeleton of the diagram and splitting it into triangles.)will l

Among more significant improvements, I will list the support for disconnected diagrams, one-object diagrams, and, the pinnacle, graceful handling of the situations when growing a pseudopod fails. Before you start thinking abut who the hell would need disconnected or one-object diagrams, I will remind/introduce the process and the necessity of pseudopods in diagram layout (Hey, that did sound like rubbish, did it :-D )

The layout algorithm essentially considers the slightly augmented underlying undirected graph of the diagram and splits it into as many triangles as it can. Then it tries to sort those triangles according to some rather heuristic (i.e., arbitrary) priority metric, picks them one by one, in this order, and tries to place them on the plane, edge to edge. The strategy being pure greedy, at some point in time it may happen that there are still triangles, but there are no free edges on the plane to which they could be attached. In this situation, the algorithm attempts to attach one of the remaining triangles by a vertex, that is, it tries to find such a vertex already in the plane, which also belongs to one of the remaining triangles. Finally, the algorithm adds an edge of the found triangle to the plane and restarts the process of picking triangles and attaching them by edges. This new added edge is referred to as pseudopod.

Now, what happens when a pseudopod cannot be grown? Initially, I was under the impression that it is rather hard to construct such a diagram. However, it turned out to be rather easy. Consider the set of objects \{A\}\cup\{A_i\mid 1\leq i\leq 10\} and the set of morphisms \{f_i:A\rightarrow A_i\mid 1\leq i\leq 10\}. DiagramGrid will lay out the first 8 of the A_i quite all right: as one would expect, A gets to be the center of a 3×3 square, whose borders consist of the 8 A_i‘s. However, the last two A_i‘s condition the situation when there are triangles left, but no pseudopods can be grown.

In an attempt to address this problem, I have considered various possible strategies, and have chosen the following one. When no pseudopod can be grown, take the set of all objects that have not yet been placed and construct from them a subdiagram of the diagram to plot. Lay that diagram out recursively and then attach the resulting grid to the initial diagram.

One important remark is due here. This strategy is a “oh, gosh, things have gone very bad” strategy, in that is is applied only when all other approaches have failed and in that it does not really guarantee the nice look of the final diagram. However, it does provide a graceful handling of the specific situations and I do believe that the output is still going to look acceptable.

While the idea itself is rather simple, it is necessary to pay attention to what subtleties it actually brings around. First of all, the subdiagram constructed from the remaining objects is not necessarily connected. That’s easy to see even in the example I have shown in the previous paragraphs. Furthermore, the constructed diagrams do not necessarily have non-loop morphisms! (By abuse of graph theoretic terminology, I call a morphism with the same domain and codomain a loop morphism). That is, addressing pseudopod extension failures brings about the necessity to handle disconnected diagrams and one-object diagrams.

There is not much to say about the support of disconnected diagrams and one-object diagrams, but that I have implemented support for these two cases as well. The latter case is handled trivially, while the former case employs standard depth-first search of the underlying undirected graph and separate layout of the connected components. The components are currently dumbly positioned side by side, in a line, and a comment in the source code evokes the possibility of using groups to get a different layout. I’m open to suggestions of further improvements in this area, though.

It’s time to speak about my plans. I have spent more than initially expected on handling pseudopod growth failures. This means that there are still some suggestions by my mentor waiting to get fixed (I haven’t read them yet; hopefully, nothing fundamental there :-D ). Further, I absolutely must fix the problem with the sort key of FiniteSet. I have been talking about fixing it for about two weeks already, and it doesn’t seem to require that much effort. It is essential that this fix be done, though, since, without it, tests in the categories module fail half of the time. Finally, I will fix how morphisms are currently pretty printed by removing the use of wide Unicode symbols. These activities will not hopefully take me more than 2 days, at the very most.

Next comes the other exciting part of my project, deciding the commutativity of diagrams. I have provided the general idea of the algorithm in my proposal. Given that I am currently about two weeks behind the schedule in my proposal, and that I will still need to spend time on getting the code in the pull requests up to snuff, I’m really feeling very wary about planning my own time. However, since deciding the algorithm for deciding the commutativity of diagrams I describe in the proposals seems to be rather straightforward, I think I will have at least a basic working version of it two weeks from now, that is, by August 5. Allowing another week as buffer time and yet another week for merging the corresponding pull request, I do expect to be in time for the firm pencils-down date.

One last remark to make is that after the official end of the GSoC timeframe, I will still have at least one week of rather spare time (I actually expect to have about 2.5 to 3 weeks of time), which means that I will bring the code to a sufficiently polished state despite any possible lags.

About these ads

2 responses to “The Polish and Further Planning

  1. Hey,

    good to read of your progress this early on a sunday ;). I don’t really have anything to add, except that (AFAICT) my remaining comments are not going to fundamentally change your code :).

    • I’ll try to keep my blog post arriving on time from now on, really really :-)

      That’s great, about the comments :-) I’ll be addressing them in a moment.

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