Hello everyone! Here are my answers to these problems. Feel free to comment!
@ Nathann 1) Some history : the BipartiteGraph class. > > > Try the following : >> sage: BipartiteGraph(graphs.CompleteBipartiteGraph(3,3)).complement() >> > Why does the graph complement G make a copy the graph itself and then changes the edges? I think "G = copy(self)" is the root of problem. The graph and its complement are too different: in general, properties like bipartitness, connectedness, coloring, shortest paths, ... are destroyed as well as all labelings on edges. Instead the function complement has to be defined in Graph and in DiGraph and needs to create a new Graph or DiGraph object... For the moment, I will not suggest to change it because there are other fundamental things to discuss... :-) > Try that : >> >> sage: BipartiteGraph(graphs.CompleteBipartiteGraph(3,3)).independent_set() >> > There should real be no error with this!! > Basically all graphs functions would need to be rewritten to work with >> BipartiteGraph. The only sane design choice would be for BipartiteGraph >> *not* to inherit Graph methods, but of course it would be pretty empty and >> all methods would need to be copied anyway. >> > No, there should be absolutely no need to rewrite a function to run on a subclass of the class Graph. Is there something wrong with the design??? I will go into details later (see Step 2 - whatsoever that is for now). > sage: g = BipartiteGraph(5) >> > To me, BipartiteGraph(n) does not make sense. It is a graph without edges. Trying to find out to which partition class vertex 0 belongs to (G=BipartiteGraph(3); G.<tab>) I was struck by this immense list of more than 270 functions. I found that G.Bipartition() will do the job. Surprisingly (or not) all vertices belong to one class and the other is empty. For me, BipartiteGraph(k,l) would be more natural (maybe with the convertion that the first partition class contains vertices 0,1,...,k-1, and the second class k,k+1,...,k+l-1). sage: g = BipartiteGraph(5) >> sage: g.add_edge(0,1) >> > It just needs to be well documented that adding an edge is only possible between different partition class. I agree with how it is now. If you want to add random edges then you need to use the class Graph() and check with is_bipartite every time you add an edge. I said it several times, but for me this class should be removed. It is not >> just bad from the computational point of view, but it also creates problems >> that new users have no idea how to cope with, because what the methods do >> is not what they have in mind. >> > Later I will comment on whether it makes sense to remove the BipartiteGraph class (please wait for Step 2 or later...) > 2) Immutable graphs : storing the graph's properties >> > > The most natural question, now : what about the a) and b) options from the >> BipartiteGraph class ? Should they inherit all methods, or none ? >> My personal advice is clear --> absolutely none. Unless somebody can >> think of a way to avoid all the problems we had with BipartiteGraph. Hence >> immutable graphs would only be used for "storage purposes", and the >> combinat guys already (repeatedly) asked for such a thing, as they >> sometimes need their graphs to be hashable (and to store them in sets, or >> as dictionary keys). It also happened to me recently, and I had to store >> spar6_string instead. > > Can you or someone else explain the details? What is exactly the problem? Is it about storing the large amount of graphs somewhere? > I also wrote some kind of static graph structure myself -- low level ones >> -- because you can perform some optimizations when you know from the start >> that the graph will not be modified. Having a static graph structure thus >> is a way to have a faster data structure, which we use for instance to >> compute distances between all pairs of vertices [4]. >> In particular, the purpose of these speedups is to save the time it takes >> to call has_edge, or to iterate over the neighbors of a graph. >> > In dead, different graph implementations should be possible... > In particular, it is totally unthinkable that graphs you actually want to >> compute things on could be immutable. We already lose time compared to >> networkX for stupid things like add/remove edges, there is no way on earth >> that add_edge would copy the whole thing. >> > Not sure about immutable, but time loss because of copying the whole graph does not make sense! 3) Splitting the files >> > I would not care so much about the size of the files if the code in them is in a good shape.... ;-) ---------------------------------------- @ Dima > IMHO it's a problem of the Graph class itself. There should be no add_edge > or remove_edge there at all. > All this mutability stuff must be done elsewhere. (In a subclass > DurtyMutableGraph, if you wish) > > Somehow I agree that many algorithms do not change the graph and therefore, the graph classes could be immutable. But should a Graph class really have no add_edge / remove_edge? That looks strange to me since I expect those to be the most natural operations on it. Have a look at what others described as standard operations on graphs: https://en.wikipedia.org/wiki/Graph_%28data_structure%29 But we probably have the same idea: the methods like add_edge/remove_edge and the algorithms have to be separated somehow (wait for Step 2 ;-) ) ---------------------------------------- For the long term plan, my major critics is about the violation of the "single responsibility principle" of object oriented programming (OOP). This important principle of object oriented programming (OOP) states that a class should have only *one* responsibility (see also https://en.wikipedia.org/wiki/Single_responsibility_principle). I want to give you some analogy with the real world. If one had a serious problem with his eyes, would he like to go to a doctor who is a dentist and a surgeon and an eye specialist at the same time? - No. He probably would like to seek advice from someone who focuses only on eye problems because of deeper knowledge about this problem and better chances of cure. Similar, it is for classes. If one class focuses only one responsibility, the functionality of that class is much easier to understand. Now let us look at the classes of graph theory. How many responsibilities does the class Graph() have? 1) representing graphs in files, e.g. sparse6_string, write_to_eps 2) running algorithm on graphs, e.g. vertex_cover, coloring, is_bipartite, 3) transformation to other classes, e.g. to_directed 4) drawing/layout, e.g. show3d 5) creating new graph objects, e.g. union, kronecker_product 6) storing and manipulating graphs, e.g. add_edge, delete_vertex *Six* responsibilities?!?! O_o In a different project I have used similar classes. Some contained well 300 methods and several responsibilities. In this way it gets difficult - unnecessary difficult - to work with and the maintenance becomes a problem... So let me turn my previous experience into some advice and with some discussion we can make it even better!! I will break down things into steps and post them separate. - import / export of graphs (modifications in graph theory, Step 1) - algorithms on graphs (modifications in graph theory, Step 2) (- and probably more are coming...) Any comments are welcome... or wait for the next posts ;-) Have fun! Birk -- -- 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
