Hello Nathann!
On 07/06/2012 08:06 PM, Nathann Cohen wrote:
> 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).
Ahaahah. So no labels anymore ? :-p
Well, I am not familiar with labels yet - not sure about that... Focus
was on the two arguments of the constructor, BipartiteGraph(k,l).
> 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.
Well, at least "BipartiteGraph" would ensure that the graph is
Bipartite, and not "preserves the first bipartition it found" :-p
Documentation is very nice sometimes, but you expect something from
BipartiteGraph when you read the class' name that really is *not* what
the class does.
For several implementations (other than sage), the partition is fixed
from the beginning. Then there is no time problem with checking the
bipartiteness while adding edges.
At the very least -- with such a name -- I think that
the BipartiteGraph constructor should take a mandatory "bipartition"
argument, so that the user necessarily knows that the class is
"bipartition-based", and that there is something more to BipartiteGraph
objects than a bipartite graph.
Even if we let this "bipartition" argument be set to "auto" (nondefault
value) so that the output of bipartite_sets is automatically computed.
Yes, there should be such an argument.
> Can you or someone else explain the details? What is exactly the
> problem? Is it about storing the large amount of graphs somewhere?
Nono, it happens when you want to use graphs as dictionary keys. I mean
-- stupid case -- you have a graph G , several graphs h_list = [h1, h2,
h3, ...] and you would like to store how many times h_list[i] occurs in
G. Well, having a dictionary such that occurrences[hi] =
numer_of_occurrence_of_hi_in_G makes sense, but that would only work if
hi is hashable (and hence immutable), otherwise Python will refuse to
work for you.
In Sage-combinat they have fancier situations -- they want to define
graphs whose vertices are graphs. Edge labels too. Crazy guys ! :-p
I see. So it is about utilizing Python constructs better. Okay...
I have seen them store objects for which the memory cost
of pointers and object stucture was around 3 times the amount of data
stored by the object.
...
In this world any graph algorithm has its own class. Its output has its
own class. A shortest path is not a list, it is a ShortestPath object.
An edge is not an pair of values, it is an Edge object. Or perhaps even
an Edge<EdgeFactory> object, I do not remember.
Anyway I saw all that, and I felt scared, threatened, and insecure O_O;;;
Yes, I have seen that as well. And I do not like that as well! I am just
thinking about some basic rules from which - in my opinion - many of us
could benefit. But that is just words, concrete examples will follow...
> 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.
I feel insulted at your hint that I have a terrible eyesight.
Would I admit it (and it is very hard to make me admit anything), I
would indeed go see an ophthalmologist, but I would obviously steer away
from a schizophrenic madman (Graph class) that believes he is sometimes
an ophtalmologist (backend), a chiropractor (GraphAlgorithms), a Zoo
Guard (GraphExport) or an indian sorcerer (GraphBasicOperations)
Oh, very sorry! I should have chosen my original example: a washing
machine that can also dry and iron... Now I hope your washing machine is
not broken ;-)
> Similar, it is for classes. If one class focuses only one responsibility,
> the functionality of that class is much easier to understand.
Well, the Graph class is not very complicated. It just has one thousand
methods that apply to graphs. But at least you never wonder in which
file they may be (except for the GenericGraph stuff. except for the
backends stuff....), you can call any function from wherever you are
without worrying of anything.
Having about 10 different graph classes will not kill you, will it?
Because I saw about 30+ .py and .pyx files in the sage/graphs directory!
I think instead of "linking/importing" from graph.py to several other
files is not easier to read either. So separating a few methods could
make the whole easier to understand...
You do not have to know a class design with 10 files to contribute either.
Is it not like that at the moment?
I mean... Classes are sometimes useful, but if we just create 10 of them
that all inherit each other we just have the same as before, written in
a more complicated way. Importing from modules looks easier to me,
whether it is done manually or automatically [2]
I thinking neither of inheriting nor of importing....
> 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
Come oooon. You can dig as many "responsibilities" as you may like,
depending on what you do with them !
- Checking properties
- Solving optimization problems
- Compute graph decompositions
- Compute statistics
Okay, I should make that clearer.
1) non-mathematical stuff: representing graphs in a different format
(e.g. in files / on screen), e.g. sparse6_string, write_to_eps
2a) mathematical stuff: running algorithm on graphs, e.g. vertex_cover,
coloring, is_bipartite, geometric-layout
2b) mixed stuff: creation of new objects out of current ones, e.g.
to_directed, union, kronecker_product
3) storing and manipulating graphs, e.g. add_edge, delete_vertex
Most of your examples will fall in category 2, but none in category 3.
But more importantly, if you can achieve to build boxes that would split
all the current graph functions into subgroups, it is much harder to
change that later on when you add stuff to existing boxes. That's the
cost of abstraction, you must be ready to change the view you have on
things anytime, and that's not easily done when it comes to code and
changing those boxes breaks Sage in many places.
I like not to have any boxes. Of course when you do that you look like a
retarded peasant, of course everything is pretty basic and obvious and
everything.
But everybody understand how it works, you easily know what you deal
with, and you do not get bitten later on by the abstractions you built.
I do not want many boxes. As above shown, there are three! Yes, if there
are too many boxes then in future restructuring becomes hard. But if
there are no boxes, we can get in trouble with file size and if we
randomly split the files, users will waste time in searching where
things are and get confused...
> 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)
Yep, by the way users often complain that we have no easy way to
import/export graphs, and with all NetworkX methods lying around all we
have to do is to call it to do the job in our stead. I think I wrote
that patch a looong time ago, but it must have been lost since :-p
OK, my post is on the way...
Of course, that's only my advice. Nobody should ever take it seriously,
for if there exists a great way to split all our files in an
object-oriented way I will be saying two days later that C is nothing
but old garbage, and that OOP is the only proper way to write code.
Let me try - of course, you can say if you find it lousy ;-)
And by the way for the next two months all graph patches will come and
go without any interruption from me, and a lot can happen during that
time :-)
Okay, that is kind of a pity at this moment, but anyway, have a good
time! :-)
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
