This is an interesting post. A few informal comments below. On Fri, Feb 26, 2010 at 12:05 PM, Ryan Hinton <iob...@email.com> wrote: > 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!
Agreed, this is not the solution. > > 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. It seems you are suggesting that there should be 2 ways to add a vertex to a bipartite graph. Either add_vertex with a required parameter specifying which vertex set to add it to, or using add_edge? I don't see a problem off-hand. > > 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. I personally favor this as it seems to me (and I definitely could be wrong) that the code will be more readable in this case. If every method in graph.py must test if the graph is bipartite or not, that makes it more difficult read and more difficult to debug, IMHO. > > PRO: clean separation, BipartiteGraph should always work. CON: > BipartiteGraph will likely lag behind Graph in functionality; perhaps > small performance loss for delegation. > ... > > 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. :-) Hopefully, others will reply who know more about the graph theory code structure thank I do. > > 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 > -- 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
