On Feb 26, 8:03 pm, Robert Miller <r...@rlmiller.org> wrote: > On Fri, Feb 26, 2010 at 9:05 AM, Ryan Hinton <iob...@email.com> wrote: > > ... > > > 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. > > I would strongly suggest this approach, i.e. option (C). As it > currently stands, a BipartiteGraph is essentially a Graph, together > with a bipartition and a few specialized functions. When you add a > vertex to this kind of object, it only stays this kind of object if > you specify which cell of the partition the vertex should go in. If > you don't specify, it should raise an error. Otherwise a Bipartite > Graph becomes something much more spooky and complicated, with "limbo" > vertices etc. Imagine a graph theorist who didn't know internals > trying to make sense of what was going on!
OK, this confirms my default decision for problem (1). > Then for Graph algorithms that don't do the right thing for > BipartiteGraphs, just override them all. If you don't feel like > rewriting all of them, raise NotImplemented errors. Anything in Graphs > that depend on BG's that don't do this properly will loudly and > clearly raise errors and then they can get fixed. It looks like you're also supporting option (C) for solving problem (2): very interesting. Since you wrote most of this code, your opinion is the most important to me. But I personally prefer both other options over (C). Option (A) puts the maintenance responsibility completely on BipartiteGraph developers (a.k.a. users). Option (B) puts the maintenance responsibility on Graph/GenericGraph developers. Option (C) just assumes everything works. A Graph method that do something bad for a BG will *only* complain when someone writes a doctest *in graph.py* for this method *using a BipartiteGraph*. Or when someone writes a doctest in bipartite_graph.py for a method that only appears in graph.py. Or, most likely, when someone starts using a BG and finds that some methods just blow up. I like option (A) because it acknowledges that BipartiteGraph and Graph have important differences. The functionality of BG will lag that of Graph, but explicitly so -- if a method exists for a BG, it should work with high confidence. I like option (B) because it is the similar to the solution for DiGraph: it allows for the important differences to be handled where necessary, and anyone working in graph.py will quickly become aware of the cases that need to be handled. (Notice the surprise of several on this list that BipartiteGraph even existed!) It seems like we should either separate the classes as in (A) so that someone working in graph.py doesn't have to know or worry about bipartite_graph.py, or integrate them as in (B) so Graph and GenericGraph developers are expected to account for (and more likely be aware of) the BipartiteGraph case. Now that I've presented it as a viable option, the wishful thinking of (C) appears unsustainable. > Any of the other approaches listed here seem prone to introduce a lot > of bugs and suck up a lot of developer time, both now and later. I think option (A) gives the fewest bugs, and option (C) the most. I think option (A) implies slightly more work now simply because a large number of one-line methods (with documentation and doctests copied from graph.py) would need to be written. I would put options (B) and (C) as roughly equal work now. Work later comes from changes or additions to graph.py. i. A new method is added. A. A BipartiteGraph user who discovers the new method and wants to use it needs to copy the documentation, make a few small changes to the doctest, and handle the call appropriately (likely 1-line delegation). B. The graph.py developer is expected to handle the bipartite case. C. A BipartiteGraph user discovers the new method and tries to use it. It might work, it might raise an exception, or it might give a wrong answer. ii. The algorithm for an existing method is changed. A. There will be a BipartiteGraph doctest for this same method, so an exception or wrong result will usually be discovered before release. B. Again, the graph.py developer should have included a BipartiteGraph doctest and handled any necessary special cases. C. Existing, correct code using BipartiteGraphs may begin to raise exceptions or silently give wrong results at the next release. Note that a graph.py developer who is *not* aware of the bipartite case reduces to option (C) for both cases. (Aren't outlines fun?) > > 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). > > Back when #1941 was created, this thorough review was done. It may > need to be updated. I think it does. There are lots of methods in graph.py; at least a few need updating that are absent from the current list. > > 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. > > I want to say that the majority of algorithms will be untouched by > this approach, and that using Python's advanced class-handling > capabilities will minimize code duplication. Yes, the majority are unchanged -- writing pass-through methods for these cases is the main disadvantage for option (A). I'm not sure what class-handling capabilities you are referring to, but I'm not a Python expert. I don't see this as a language issue. Python doesn't get in the way, but it certainly doesn't solve the problem. Well, perhaps we could use some of the introspective features of Python in option (A) to indicate when Graph and BipartiteGraph don't have the same set of methods. - 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
