Sounds like a good summer of code project?
---- LOOK ITS A SIGNATURE CLICK IF YOU DARE--- http://www.google.com/profiles/zitterbewegung On Fri, Feb 26, 2010 at 11:05 AM, 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! > > 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 > -- 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
