I've been working on a new implementation of an algorithm to compute the genus of graphs. Throughout the process, I've been bound by the chains of backwards compatibility. As I've attempted to finish off the patch, I've found some deeply unsettling details in the current implementation. I'd like to hear from somebody (anybody) who computes the genus of graphs with Sage, or cares about this sort of thing in general.
Currently, the following features exist within Sage: * computing the minimal/maximal genus for connected graphs * computing the minimal/maximal genus for connected graphs respecting a boundary (ordered or unordered) * computing the genus of graph with a combinatorial embedding supplied by the user where we define the maximal genus as the maximum obtained by a combinatorial embedding. The following are completely broken, or **built on hypotheses that are almost certainly false**: * computing anything about combinatorial embeddings of graphs with more than one parallel edge or loop (we can accept up to 1 extra edge due to a rounding error) * computing the maximal genus for graphs respecting a boundary (this includes a conspicuously incorrect doctest) * computing anything about combinatorial embeddings of directed graphs * computing the genus of an empty graph (har har) Also, what does work (simple connected graphs) is so slow, it makes my eyes bleed. I'd like to remove anything referring to the "maximal" genus of a graph. It seems to have been implemented purely because it was easy to do so. I could also be convinced that we should keep this feature, and raise a NotImplementedError where the implementation is senseless. Also, I might like to make it possible to compute the genus of multigraphs and looped graphs. Part of the difficulty in this is that embeddings are represented with the assumption that graphs are simple, so this would result in a change that appears backwards incompatible -- however, I believe that the only thing lost would be non-simple graphs, where an incorrect answer was given anyway. Alternately, I'd be happy to never compute anything about these graphs -- the only reason *not* to think about embeddings of simple graphs is that the max genus goes up with extra parallel edges. More reason not to support the max genus. Issues to vote on: 1) Max Genus: a [ ] Remove every reference to maximal genus b [ ] Raise NotImplementedError for max genus computations that are not supported c [ ] Delay everything indefinitely until somebody cares enough to make max genus work while respecting embeddings (I probably won't do this) 2) Looped Multigraphs: a [ ] Break backwards compatibility in some cases b [ ] Raise NotImplementedError on anything involving embeddings of multigraphs (note, we could still compute the minimal genus with this option) For your consideration, my currently-existing code is about ten thousand times faster for simple graphs, and is working very well. My votes are: 1) a 2) b Thanks, --tom -- To post to this group, send email to sage-support@googlegroups.com To unsubscribe from this group, send email to sage-support+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-support URL: http://www.sagemath.org
