This will be my last post on the topic for now. On Mon, Mar 1, 2010 at 2:45 PM, Ryan Hinton <iob...@email.com> wrote: > Again, the wishful thinking is the assumptions. Here are a few > examples. > > * The copy() method calls the DiGraph and Graph constructors > directly. To get all the same functionality (e.g. copying the _assoc > and _embedding attributes) in a BipartiteGraph override (option C) > would require duplicating the code. Or is there a better way? > > * union(), disjoint_union(), cartesian_product(), tensor_product(), > etc. also create Graph() and DiGraph() objects directly -- similar to > copy(). So they would need to be overridden in BG -- possibly with > the same code/algorithm -- to produce outputs of the correct class.
These are the kind of functions I would suggest adding doctests for the BipartiteGraph case. They clearly behave differently in the BG case, and should be tested in that case. Functions for which there is no major difference might not need BG doctests. > They also use tests like "self._directed and not other._directed" to > make judgements about the *class* of the objects. Shouldn't the > __class__ be tested directly? No, exactly because discussions like these can sometimes change what __class__ the object is, especially in subclassing. > * Algorithms like the one for is_circular_planar() add/remove edges > and vertices from the graph will fail (loudly) once these are > overridden for BipartiteGraph. > > Maybe these are the only cases to worry about: creating objects and > testing the class. Since the implementation (e.g. NetworkX vs. > c_graph) is usually abstracted, most of the algorithms use the > "public" add_edge-style interface. Some do access the _backend member > directly, so this is another red flag to watch for. But the methods I > saw that did this *were* the core methods like add_edge(). Aside from "core" functions (essentially the ones implemented by each backend), things like copy and products, or things which return another graph, I can't think of too many functions this would effect. >> Bugs: > > I neglected to mention my assumption that the code added was free of > bugs for its intended target, i.e. a method in Graph is correct for > Graph instances (though not necessarily BipartiteGraph instances). No new code is bug free. This isn't a law, it's more of a hypothesis, but it's a good one to make. Finding those bugs requires skill, even more so when they are bugs in (apparently) unrelated objects. :-) > True, it might take a long time for the BipartiteGraph class to > stabilize. But apparently nobody is using it now since it's not > complete. In other words, it hasn't stabilized yet using the current > approach. Still, I think this is simply due to lack of time, > interest, and people knowing it existed. (Hopefully the latter is > fixed now. :-) > >> Option B: Basically the same a A. New bugs guaranteed, subtle and a >> long time to fix them all. I think this option is even more prone to >> subtle bugs and endless work than A. Adding new functions to Graph or >> BipartiteGraph will likely introduce bugs, since author and reviewer >> are likely to forget checks all over the place. > > Maybe we're thinking of different things. I don't see that it will > take any more work to add some case checking in the GenericGraph > methods that option (C) would have to override. I guess it could be argued that it's equivalent amounts of work, but option C is cleaner. > Every method signature and documentation would be > duplicated This is what makes this option too ugly to consider, IMHO. Think about the size of the graph modules already! > I don't know that blowing up is optimal, but it's certainly better > than silent failure. :-) And I think it's good enough -- perhaps as > good as we can expect. The case we are considering is when someone adds a Graph method which is incorrect for a BG. This is possible as long as BipartiteGraph is a subclass of Graph. If BipartiteGraph is not a subclass, then you have more or less two copies of most of the graph code (at least as much of it is documentation as actual code). Yuck! If it is a subclass, then mistakes will happen no matter what. I think it's fair to say you can count on mistakes no matter what. If someone adds a Graph method which is incorrect for a BG, then it doesn't matter which option we have taken, since in the one case they weren't aware of BipartiteGraphs, and in the other, they weren't aware of the special handling for ._bipartite. Six or half a dozen, your choice. > Are you suggesting the doctest for each method in generic_graph.py > should also test a BipartiteGraph instance (at least for those that > work without modification)? That starts to sound alot like my > "mixing" option (B), because then the responsibility falls on the > Graph developer. I would love to see more BG's tested directly in > Graph and GenericGraph doctests -- but expecting/requiring the > doctests should produce resistance roughly equal to the resistance you > predicted for option (B). No. I don't really believe in proposing the way things "should" be unless there is also a clear path to making them "be" that way. The way I see it, nobody knows about or uses BG's right now (with a few exceptions, but even you yourself stopped using the class for your research). If someone cares enough about them to develop on them, the development they do should be proportional to their willingness to do the work. In other words, to decree that a specific overhaul is necessary before we can start using BG's adds a very large constant amount of work to any patch someone might write. The result, is that BG's die. The way I see it is this. Researcher X decides to study propery Y of bipartite graphs. In using Sage's BG's to study this phenomenon, X discovers certain flaws in the BG's in Sage, and fixes them. Sorry folks, but everyone has to do this, it's the name of the game. But now that those bugs are fixed, Sage can be successfully used to study Y. Tada! And in the patches, the functionality that X cares about will be thoroughly tested, and will no longer break. The point of doctests! Looking at Sage's integers, I can safely say that no design decision was made to avoid future patches from making mistakes. In fact, few patches to Integers don't break something (unless RWB or someone similar wrote the patch ;-). I think it's a very dangerous idea to make large sweeping changes based on the fact that someone may write a patch and break something. Much better to fix things and make them work, and leave lots of documentation explaining how things work. For example, the reference manual by now should have an extensive section on backends, the different classes, how they play together, typical gotcha's, etc., which anyone getting started on developing graphs should read first. This is the right way to fix the "eventual bug" problem. Then we are free to make our design decisions without worrying about that particular problem. > OK, I'm willing to accept BG as inheriting from Graph. It's unlikely > anyone will write or maintain option (A). Good, we can agree there. > As for your "documentation" solution, I think this is where we > disagree. If I use tab completion and find a method hanging on a > BipartiteGraph instance, I expect it to work. I agree here too. I think that all functions BipartiteGraphs have should work. And this is easy to fix, the way things are right now. If someone adds a patch in the future which introduces a new BipartiteGraph function, that should also work. However, if we were to take the argument to its logical conclusion, no class would subclass from any other class, unless the base class were never used on its own. This is silly. I propose the following: 1. Review the patches you have already made to get BG's closer to fully functional. 2. Finish the issues in #1941, find any other similar issues, and fix them, documenting everything fixed. 3. Carefully document how things are set up in the graph modules, laying out how graph development is done these days. None of these three items is very serious work, and it solves all the problems mentioned on this thread. In fact, if all the work put into this thread had been put into implementing 1, 2 and 3, it would already be finished. I should also mention that there are, in fact, many classes in Sage which don't subclass even though they do satisfy the "is a" relationship, but this is, as far as I know, always due to vast differences in implementation. Since the underlying representation of a BipartiteGraph essentially "is a" (sic) the same as the underlying representation of a Graph, I think the classes should reflect that. -- Robert L. Miller http://www.rlmiller.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
