I'm having a lovely conversation with myself in the comments for trac #8350 that I want to share. :-)
There are two related problems. 1. The current BipartiteGraph class is incomplete, see trac #1941. I want to use it, so I'm trying to plug some of the holes. In particular, trac #8350 suggests overriding add_vertex() and add_vertices() to properly maintain the bipartition data structures. 2. The current Graph code assumes vertices and edges can be added at will, e.g. the algorithm for is_cirular_planar(). Also, many other methods do not behave as expected for BipartiteGraphs, e.g. union() will return a Graph given two BipartiteGraph's. Problem 1 first. add_vertex() needs to maintain the bipartition sets. When a new vertex is added, it needs to go "left" or "right". The natural solution is to include an extra argument or two in order to specify where the new vertex (vertices) will go. I thought I had a clever solution for problem (2): if a new vertex is added without specifying which partition it belongs to, just change the current object from a BipartiteGraph to a Graph instance. But now I think this is a really bad idea, since calling an arbitrary method that *should not* change the graph. For example, a test like is_circular_planar would suddenly and silently change the class of my object! I considered another option. Why not just wait until an edge is added to figure out whether a node is left or right? Because all the vertices should be in one set or the other at all times. For example, if I add a vertex and then iterate (before adding any edges) over the left and right subsets, the new vertex would be absent! OK, assume we solve (1) by requiring an indication of which partition a vertex belongs in and raising an exception otherwise. What about Graph algorithms that change the graph temporarily or just don't "do the right thing" for BipartiteGraph's? I see a few possibilities. A. Change BipartiteGraph so that it doesn't inherit from Graph. This requires adding a bunch of code to bring the BipartiteGraph functionality to par with Graph. Also, any future methods added to Graph will need to be duplicated (often simply delegated) in BipartiteGraph. PRO: clean separation, BipartiteGraph should always work. CON: BipartiteGraph will likely lag behind Graph in functionality; perhaps small performance loss for delegation. B. Make BipartiteGraph handling an integral part of the Graph class, similar to DiGraph and the '_directed" attribute. This requires a thorough review of the current Graph code to see where bipartite-ness must be taken into account or can be exploited (optional). Also, future methods will need to be aware of the possibility of operating on BipartiteGraphs. PRO: similar to current DiGraph solution; most likely to keep BipartiteGraph and Graph features equal. CON: some Graph methods may break for BipartiteGraph instances; some methods may run a little slower due to extra conditional handling. C. Continue as we do now, i.e. BipartiteGraph is a subclass of Graph and overrides methods when necessary. This requires a thorough review of the current Graph code to see where bipartite-ness must be taken into account or can be exploited (optional). These methods will need overrides in BipartiteGraph. Also, future methods in the Graph class will need this same review. PRO: clean separation; perhaps a little less work initially. CON: future Graph methods most likely to break for BipartiteGraph instances; some duplication of code possible for similar but distinct BipartiteGraph algorithms. SUMMARY: All of the options require a good chunk of work to really finish the BipartiteGraph class. (I will not have time to finish this task soon.) I think option (B) is best: it's similar to the current DiGraph situation; many new Graph methods will "just work" for BipartiteGraph (not constantly playing catch-up); and the BipartiteGraph case is most likely to be noticed, handled and tested by people working on the Graph class -- once someone does the big chunk of work. I suppose since I'm not committing to doing the work, I'm asking for a policy decision so I can fix my pressing problems appropriately. I also volunteer to put comments at the top of graph.py and bipartite_graph.py explaining problem and the policy. :-) Thanks! - Ryan -- 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
