Hello! It's great that Sage is part of GSoC.
I'm a CompSci student at Charles University in Prague. I already (in last few months) submitted some patches that fixed ~dozen of minor flaws of Sage graph library: see tickets #10135, #12325, #9786 for example. Most of them are already merged. This year I'm finishing my bachelor thesis -- it is concerned with surreal numbers and contains some results obtained through Sage with CGT code I will submit to Sage as soon as possible. This is not what I want to work on during summer, though. == Idea == I'm interested in BipartiteGraph class. It's a problematic one: see ticket #10081 for some criticism. I would like to make things right, and not just for this one class, but, with your help, make a system for various properties like planarity, chordality, ... to behave in a user-friendly way: > plangraph = PlanarGraph(); plangraph Planar graph on 0 vertices > plangraph.add_edge(1,2); plangraph Planar graph on 2 vertices > for c in Combinations(range(3, 8),2): plangraph.add_edge(c[0], c[1]) Exception: addition of edge (6, 7) breaks following property: planarity > show(plangraph) [Some fitting visualization. Well, this is simple for planar graph, but IntervalGraph or BipartiteGraph could be drawn in nice way.] I already discussed this idea with Nathann Cohen few months ago -- he was very kind to devote me a few minutes. If I understand his opinion correctly, he thinks that there is little value in keeping graph properties during computations and if such a thing is necessary, a programmer can do this for her own more efficiently (she can choose precisely where re-testing is necessary). Also, he finds lack of control of partitions in bipartite graph impractical. I agree that this is probably true for a scientist who uses Sage with good knowledge of programming and math, but I would love to see this environment in education more. In last two years, I work on a project for educating Czech high-school students algorithmization. (ksp.mff.cuni.cz) I also participated in a preparation of "Introduction to discrete mathematics" lecture at my university. I can say these (clever) beginners are very uncertain and that every external assurance like "yes, you can be sure that this graph is bipartite whole time" helps them a lot. So, I'm looking for a solution that would be easily avoidable for advanced users and helpful for new ones. Advanced user, if he wants, can profit from the framework greatly by creating his own invariants he wants to hold during computation. There is another reason I would like to see this work: I think that Sage graph library should contain online algorithms for fast decisions like "is this graph still planar, if I add this edge?". This would make a good environment for such additions. == How to do this? == I have thought about this a lot. Still, I don't have any ideal solution, so I am looking forward for your suggestions. This is the best I figured out: There is just one instantiable class, Graph. It posses method assert_property(...) that register a new property that graph have to follow henceforth after every edge/vertex addition/deletion. "Property" is just a name and a couple of functions of specific online algorithm that Graph calls whenever it is updated. There is also a method that removes assertion, and, of course, list of asserted properties. For each graph class there is a (P|C)ython class that contains implementation of (online) algorithm deciding whether property still holds. Every method that works on specific graphs (bipartite_complement) can rely on assured property, or, if the desired property is not assured, do test using "is_something" method from the mentioned class. User could bypass this check with "check" argument that is already presented in some methods. Systematic addition of this argument to methods would be a great improvement for advanced users. Creating of new, let's say, planar graph like in example above would require creating a helper function that 1) create regular graph 2) register desired property using assert_property 3) re-set standard drawing method to "bipartite"/"interval"/... . == Remarks == * It is obvious that it is not wise to squeeze all imaginable properties into such framework. Only several well-known properties deserve such attention. * The whole thing can be faster if we turn off online checks for the time methods from Sage library runs. There is no use for a user if she knows where in the run of our algorithm property breaks as she doesn't know details of our implementation. It is only interesting to know that "the result of Graph.complement() is not bipartite anymore". Moreover, such mechanism would allow to do invalid operations inside our methods without an exception if the result is correct. * Documentation should clearly state that this assertions can hurt performance. So, thanks for your attention! Please, respond: what do you think about this? Lukas Lansky. -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
