Opened 6 years ago

Closed 6 years ago

#14980 closed enhancement (fixed)

graph_generators, some more clean up

Reported by: eisermbi Owned by:
Priority: major Milestone: sage-5.12
Component: graph theory Keywords:
Cc: dcoudert, ncohen Merged in: sage-5.12.beta5
Authors: Birk Eisermann Reviewers: Nathann Cohen
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by jdemeyer)

While adding some graph generators I found some confusing things which I like to improve with this patch first.

  • Why are Butterfly, Krackhardt Kite, Barbell graph listed under "Basic Structures" while Peterson Graph and CompleteGraph? are not? Maybe the term "basic structures" is subjective and everyone has a different opinion about basic...
  • What is a "small graph"? A graph with a small number of vertices, alright? E.g. 13 vertices on http://www.graphclasses.org/smallgraphs.html In general not much more than 15 or 20 vertices. Can "Balaban11Cage()" with 112 vertices, "CameronGraph?()" with 231 vertices, "Tutte12Cage()" with 126 vertices be called "small graphs"??

Overview of modifications on the files 'sage/graphs/graph_generators.py' and 'sage/graphs/generators/*'.

Part 1

  • "Small Graphs" (also called "named graphs" previously): Added documentation: "A small graph is just a single graph and has no parameter influencing the number of edges or vertices."
  • Families of Graphs: Added documentation: "A family of graph is an infinite set of graphs which can be indexed by fixed number of parameters, e.g. two parameters."
  • Pseudofractal graphs: The graph "DorogovtsevGoltsevMendesGraph?" seems to be a quite special graph family. Does it need its own section? I completely moved it to Families now.

Part 2

  • "Platonic Solids" is a subsection of "Small graphs". This section is ordered by number of vertices now.
  • "Chessboard graphs" is a subsection of "Families".
  • RandomGNP returns graph, hence, "n" -- number of nodes of the graph (not: digraph)
  • benzenoids is replaced by fusenes in __append_to_doc.

Part 3 (not to be applied anymore)

Part 4

  • "Basic structures": Actually these graphs could be listed in the other classes. Three not so basic graphs are moved: "BarbellGraph?", "WheelGraph?" to families and "BuckyGraph?" to small graphs. The example at the beginning of the module is expanded.

Part 5

  • replaces ... by ....: in doctests and removes some empty "....:" lines after loops;
  • replaces graph.Graph(......) by Graph(......).

Apply:

(The 'part3' patch is *NOT* to be applied)

Attachments (6)

trac_14980-part3_miscellaneous.patch (29.9 KB) - added by eisermbi 6 years ago.
trac_14980-part1_docu.patch (7.9 KB) - added by eisermbi 6 years ago.
trac_14980-part2_docu.patch (23.0 KB) - added by eisermbi 6 years ago.
trac_14980-part4_basic.patch (45.2 KB) - added by eisermbi 6 years ago.
trac_14980-part5_doctests.patch (47.9 KB) - added by eisermbi 6 years ago.
trac_14980-part5_doctests_noemptylines.patch (47.3 KB) - added by jdemeyer 6 years ago.

Download all attachments as: .zip

Change History (19)

Changed 6 years ago by eisermbi

comment:1 Changed 6 years ago by eisermbi

  • Status changed from new to needs_review

comment:2 follow-up: Changed 6 years ago by ncohen

  • Status changed from needs_review to needs_info

Helloooooooooooooooooooo !!!

If I remember correctly, this "small graph" has also been called "named graphs" or "unique graphs" through time, none of which was satisfying. Because some named graphs are actually families, because "unique" has a mathematical meaning too... But it was meant to indicate that the constructor takes no parameter, indeed. "small" here means "bounded-size", I guess :-)

To me complete graphs should belong to the basic structures, Petersen not. Well, that's just my opinion on the matter.

Part 1: It all makes sense to me. Individual graphs is a nice name too, btw. This being said, do these names really appear in Sage ? That's the module's name of course but users get those graphs through graphs.<tab>, so it's not that bad either. Not that it shouln't be changed if you think it's wrong of course.

Part 2:

  • Why did you remove the index in chessboard.py ? An index is niiiiiiiiiice :-P Plus this module will not change much, so it's not very hard to keep updated.
  • You changed the order of methods in the Platonic Solids, but the append_to_doc method reorders them according to the alphabetical order :-P
  • What do you mean by "chessboard graphs are now a subsection of families" ?
  • Bad formatting of Random GNP : could you open a ticket for that and add me in cc ?

Part 3:

  • Why on earth wouldn't fullerenes, trees, line_graph_forbidden_subgraphs and cospectral_graphs be families of graphs ? O_O
  • If these are not moves to miscellaneous.py, this module doesn't have any meaning if it just contains the world map. Actually, I created an independent file for this graph because it takes sooooooooooo much Python code to build.

Part 4: Wow. This patch is a bit hard to read.

First, it seems from your message that after this patch is applied some method may be defined in two files, and we just don't do that. We'd be sure to fix a bug in one without fixing the other. Unless you imported one into the other file, in which case my reason for opposing this change is different :

First, I don't get your main argument : how can moving methods around in these files change anything for the users, when he can get them all through graphs.<something> ? These constructors have only been split because Jeroen didn't want the graph_generators file to grow too large, and the users do not even have to know that they exist. Is it just because of the index in graph_generators.py ?

Overall:

  • You fixed typoes in sage.graphs.graph_generators in some places, but could you change it to :mod:`sage.graphs.graph_generators` instead ?

So far I agree with the first 3 parts, short of this question of things which you don't think are graph families. Tell me what you think ! ;-)

Nathann

comment:3 in reply to: ↑ 2 ; follow-up: Changed 6 years ago by eisermbi

Thanks for your comment!

Replying to ncohen:

[...]

Part 1: It all makes sense to me. Individual graphs is a nice name too, btw. This being said, do these names really appear in Sage ? That's the module's name of course but users get those graphs through graphs.<tab>, so it's not that bad either.

Since a good name is not so easy to find, let us stick with the name and just add the description. That makes it clear enough.

Part 2:

  • Why did you remove the index in chessboard.py ? An index is niiiiiiiiiice :-P Plus this module will not change much, so it's not very hard to keep updated.

Sure, I did not want to remove any index. But I am curious which index you are refering to. I thought

__append_to_doc(["BishopGraph", "KingGraph", "KnightGraph",
     "QueenGraph", "RookGraph"])

in the file "graph_generators.py" does this job nowadays. Is there another index??

  • You changed the order of methods in the Platonic Solids, but the append_to_doc method reorders them according to the alphabetical order :-P

Hmmm... Looking at the definition def __append_to_doc(methods): I cannot see that methods is reordered alphabetically nor is the output (HTML documentation) sorted alphabetically. I get

  TetrahedralGraph   HexahedralGraph     DodecahedralGraph
  OctahedralGraph    IcosahedralGraph

which is ordered by the number of vertices (not alphabetically). I think it is working...

  • What do you mean by "chessboard graphs are now a subsection of families" ?

In the documentation I changed the level of the heading of chessboard graphs. Now it looks like "Chessboard graphs" is a subsection of "Families of graphs". Similar with "Platonic solids".

  • Bad formatting of Random GNP : could you open a ticket for that and add me in cc ?

Done, #15009.

Part 3:

  • Why on earth wouldn't fullerenes, trees, line_graph_forbidden_subgraphs and cospectral_graphs be families of graphs ? O_O

Yes, they are families of graphs. What I wanted to say is that they do not return a single graph but a list of graphs or graph iterators. Especially, the function cospectral_graphs made me wonder since it differs from the others in the return type - a list of lists of graphs. Is a "family" (list) the same as "family of sets" (list of lists)? ;-) Actually these function can be distinguished from the others because their names start with small letters. Hence, leaving them under "Families" is okay.

  • If these are not moves to miscellaneous.py, this module doesn't have any meaning if it just contains the world map. Actually, I created an independent file for this graph because it takes sooooooooooo much Python code to build.

I see. I think it is easier to lookup a file when the section title is similar to the filename, e.g. "Random graphs" <-> "random.py", "Miscellaneous" <-> "miscellaneous.py". And the file would also be open for new graphs other than world maps. That is my reasoning.

Part 4: Wow. This patch is a bit hard to read.

First, it seems from your message that after this patch is applied some method may be defined in two files, and we just don't do that. We'd be sure to fix a bug in one without fixing the other. Unless you imported one into the other file, in which case my reason for opposing this change is different :

No, I took each function and put it either in families.py or small.py (never both!). My statement about "double listing" graphs might have been confusing. I only was referring to the documentation not the source code. I moved the source code of graphs considered as basic into their corresponding sections and listed the graph names only a second time under "Basic structures" in the reference documentation. That is all.

First, I don't get your main argument : how can moving methods around in these files change anything for the users, when he can get them all through graphs.<something> ? These constructors have only been split because Jeroen didn't want the graph_generators file to grow too large, and the users do not even have to know that they exist. Is it just because of the index in graph_generators.py ?

Partly, yes. At the moment to check whether a graph exists one also needs to look at "Basic structures" because a graph might be listed there instead of its corresponding section. Not so bad either. So I can drop this part if the change is too complicated... Let me know.

Overall:

  • You fixed typoes in sage.graphs.graph_generators in some places, but could you change it to :mod:`sage.graphs.graph_generators` instead ?

Sure, I can.

So far I agree with the first 3 parts, short of this question of things which you don't think are graph families. Tell me what you think ! ;-)

Nathann

After the remaining points are clarified I will update the patch. :-)

Birk

comment:4 in reply to: ↑ 3 ; follow-up: Changed 6 years ago by ncohen

Helloooooooo !!

Part 1:

Since a good name is not so easy to find, let us stick with the name and just add the description. That makes it clear enough.

"And just add the description" ? Sorry, I don't get your meaning ^^;

Part 2:

Sure, I did not want to remove any index. But I am curious which index you are refering to. I thought

__append_to_doc(["BishopGraph", "KingGraph", "KnightGraph",
     "QueenGraph", "RookGraph"])

in the file "graph_generators.py" does this job nowadays. Is there another index??

Right right, but there was another index in the chessboard.py file which your patch removes. And it's not thaaaaaaaaaat useful, but I still don't see why you want to remove it. It can only help to have an index of the methods in each module.

  • You changed the order of methods in the Platonic Solids, but the append_to_doc method reorders them according to the alphabetical order :-P

which is ordered by the number of vertices (not alphabetically). I think it is working...

SOrryyyyyyyyyyyy ! I was convinced that I have made this method sort its input before building the table. I just re-read the code and it isn't so, you were right and there is nothing wrong with that.

  • What do you mean by "chessboard graphs are now a subsection of families" ?

In the documentation I changed the level of the heading of chessboard graphs. Now it looks like "Chessboard graphs" is a subsection of "Families of graphs". Similar with "Platonic solids".

I don't get this either : none of your patches touch a .rst file O_o

Part 3:

  • Why on earth wouldn't fullerenes, trees, line_graph_forbidden_subgraphs and cospectral_graphs be families of graphs ? O_O

Hence, leaving them under "Families" is okay.

Cool ! ;-)

I see. I think it is easier to lookup a file when the section title is similar to the filename, e.g. "Random graphs" <-> "random.py", "Miscellaneous" <-> "miscellaneous.py". And the file would also be open for new graphs other than world maps. That is my reasoning.

Well... It is true, but if there is only one method there anyway, perhaps we can at least wait for another method before renaming the file... :-P

No, I took each function and put it either in families.py or small.py (never both!). My statement about "double listing" graphs might have been confusing. I only was referring to the documentation not the source code. I moved the source code of graphs considered as basic into their corresponding sections and listed the graph names only a second time under "Basic structures" in the reference documentation. That is all.

Well, now you are the one adding the name of a graph to a section of the doc while the method itself is not defined in the module corresponding to the doc section :-P

Partly, yes. At the moment to check whether a graph exists one also needs to look at "Basic structures" because a graph might be listed there instead of its corresponding section. Not so bad either. So I can drop this part if the change is too complicated... Let me know.

Well.. I hope that the name of most constructors can be guessed through tab completion only, and from the doc page with a Ctrl + F.

Perhaps we could move some of them from Basic Structures to small graphs, though... As for some you are right to say that one would not immediately go look at the "basic structures" to find them. Like Claw graph, or House graph, or Diamond... Wheel could very well go to families, by the way.

Well, the problem with this section is that it was made to split a big file in two, and there is no clear reason why some graphs should be there and not somewhere else... ^^;

Thank you very much for your work on these files :-)

Nathann

Changed 6 years ago by eisermbi

Changed 6 years ago by eisermbi

Changed 6 years ago by eisermbi

comment:5 in reply to: ↑ 4 ; follow-up: Changed 6 years ago by eisermbi

  • Authors set to Birk Eisermann
  • Description modified (diff)
  • Status changed from needs_info to needs_review

Hello!

Part 1:

Since a good name is not so easy to find, let us stick with the name and just add the description. That makes it clear enough.

"And just add the description" ? Sorry, I don't get your meaning ^^;

In other words, I added some text (short explaination) to the docstring of the file graph_generators.py (after the headings "Small Graphs" and "Families"). That is all - no change of name.

Part 2:

Sure, I did not want to remove any index. But I am curious which index you are refering to. I thought

__append_to_doc(["BishopGraph", "KingGraph", "KnightGraph",
     "QueenGraph", "RookGraph"])

in the file "graph_generators.py" does this job nowadays. Is there another index??

Right right, but there was another index in the chessboard.py file which your patch removes. And it's not thaaaaaaaaaat useful, but I still don't see why you want to remove it. It can only help to have an index of the methods in each module.

Previously, the file graph_generators.py contained all definitions and a big index. After the splitting of this file most definitions are put into several other files. The big index is still kept there. I thought to remove

- :meth:`BishopGraph <GraphGenerators.BishopGraph>`
- :meth:`KingGraph <GraphGenerators.KingGraph>`
   ...

from the file chessboard.py because

  • I think it is a left over from the split and replaced by __append_to_doc;
  • No other file under sage.graphs.generators, e.g. random.py, contains such an index;
  • I do not know how to display this index other than by opening the file in a text editor;

Now I will leave it there but I have not understood your reasoning....

  • What do you mean by "chessboard graphs are now a subsection of families" ?

In the documentation I changed the level of the heading of chessboard graphs. Now it looks like "Chessboard graphs" is a subsection of "Families of graphs". Similar with "Platonic solids".

I don't get this either : none of your patches touch a .rst file O_o

Looking at the docstring of graph_generators.py there is the heading "* * Families of Graphs * *" and I formatted the other heading as "* Chessboard Graphs *" (note the number of stars). Hence, it looks like a subsection of "Families of Graphs".

Part 3:

I think it is easier to lookup a file when the section title is similar to the filename, e.g. "Random graphs" <-> "random.py", [...]

Well... It is true, but if there is only one method there anyway, perhaps we can at least wait for another method before renaming the file... :-P

Okay, let's wait for that.

Part 4:

No, I took each function and put it either in families.py or small.py (never both!). My statement about "double listing" graphs might have been confusing. I only was referring to the documentation not the source code. I moved the source code of graphs considered as basic into their corresponding sections and listed the graph names only a second time under "Basic structures" in the reference documentation. That is all.

Well, now you are the one adding the name of a graph to a section of the doc while the method itself is not defined in the module corresponding to the doc section :-P

True! I had thought of dissolving the section "basic structures", but the section can show users not familiar with graph theory what we consider as basic graphs... ;-)

Perhaps we could move some of them from Basic Structures to small graphs, though... As for some you are right to say that one would not immediately go look at the "basic structures" to find them. Like Claw graph, or House graph, or Diamond... Wheel could very well go to families, by the way.

Okay, I moved "Barbell-", "Bucky-", "WheelGraph?" to other sections.

... there is no clear reason why some graphs should be there and not somewhere else... ^^;

That is the point. Given a (mathematical) definition of some sort of graph it seems easier to tell whether it is just a single graph or whether a parameter or two are involved (i.e., a family of graphs) or whether a graph is derived from a complex data structure (i.e., from a geometric representation). In contrast it is more subjective to judge whether a graph is basic.

The patch is updated (based on 5.12beta1; part 3 is not applied anymore).

Birk

comment:6 in reply to: ↑ 5 Changed 6 years ago by ncohen

  • Description modified (diff)
  • Reviewers set to Nathann Cohen
  • Status changed from needs_review to positive_review

Hellooooooo !!

In other words, I added some text (short explaination) to the docstring of the file graph_generators.py (after the headings "Small Graphs" and "Families"). That is all - no change of name.

Oh. Okayyyyy !

Previously, the file graph_generators.py contained all definitions and a big index. After the splitting of this file most definitions are put into several other files. The big index is still kept there. I thought to remove

- :meth:`BishopGraph <GraphGenerators.BishopGraph>`
- :meth:`KingGraph <GraphGenerators.KingGraph>`
   ...

from the file chessboard.py because

  • I think it is a left over from the split and replaced by __append_to_doc;
  • No other file under sage.graphs.generators, e.g. random.py, contains such an index;
  • I do not know how to display this index other than by opening the file in a text editor;

Hmmmmm.. Well, those methods were never in the big graph_generators file, but I thought that it appeared in the doc index independently... Well, no big deal :-)

Looking at the docstring of graph_generators.py there is the heading "* * Families of Graphs * *" and I formatted the other heading as "* Chessboard Graphs *" (note the number of stars). Hence, it looks like a subsection of "Families of Graphs".

Okayokay !

Okay, I moved "Barbell-", "Bucky-", "WheelGraph?" to other sections.

Cool.

That is the point. Given a (mathematical) definition of some sort of graph it seems easier to tell whether it is just a single graph or whether a parameter or two are involved (i.e., a family of graphs) or whether a graph is derived from a complex data structure (i.e., from a geometric representation). In contrast it is more subjective to judge whether a graph is basic.

Aahahah. Well, I think that it is easier to look for the graph's name inside of this page than reading the formal definition of each category, by just looking at it or with a CTRL+F but well. Can't hurt. When you're going to this page you just look for one thing in particular, and I guess that nobody would use more than ten entries in this list very often ;-)

Thank you for this patch ! I just applied it, passes the graph/ tests and compiled the doc and everything seems nice.

Nathann

Apply trac_14980-part1_docu.patch, trac_14980-part2_docu.patch, trac_14980-part4_basic.patch

comment:7 follow-up: Changed 6 years ago by jdemeyer

Since you're cleaning up a lot anyway, how about changing ... to ....: in doctests?

comment:8 Changed 6 years ago by eisermbi

  • Status changed from positive_review to needs_work

Changed 6 years ago by eisermbi

comment:9 in reply to: ↑ 7 Changed 6 years ago by eisermbi

  • Description modified (diff)
  • Status changed from needs_work to needs_review

Replying to jdemeyer:

Since you're cleaning up a lot anyway, how about changing ... to ....: in doctests?

Okay, I added part 5: trac_14980-part5_doctests.patch.

(1) It improves the formatting of the doctests.

(2) As far as I know, there is no difference between

from sage.graphs.graph import Graph
from sage.graphs import graph

def ........
    import networkx
    g=graph.Graph(.....

and

from sage.graphs.graph import Graph

def ........
    import networkx
    g = Graph(.....

Hence, I replaced the former with the latter. (There were only graph.Graph expressions starting with graph..)

comment:10 follow-up: Changed 6 years ago by ncohen

Helloooooooooooooooooo !!!

This last patch seems ok, but I am no big fan of the empty "....:" lines after a loop. As it is not Suuuuuuch a bad thing, I uploaded another version of your last patch with these lines removed, and you can chose to use it in this ticket instead of the current last patch if you agree. And if you prefer the way it is done right now you can set the ticket to positive_review anyway. Your pick :-)

Have fuuuuuuuuuuuuuuuuuuuun !

Nathann

comment:11 in reply to: ↑ 10 Changed 6 years ago by eisermbi

  • Description modified (diff)
  • Status changed from needs_review to positive_review

I saw these empty lines in the examples, too, and was wondering whether to remove them. Since the examples are short and there is indention, those empty lines hardly improve readability but take up vertical space. Hence, I have chosen your version. Since you have agreed I set the ticket to positive_review.

comment:12 Changed 6 years ago by jdemeyer

  • Description modified (diff)

Changed 6 years ago by jdemeyer

comment:13 Changed 6 years ago by jdemeyer

  • Merged in set to sage-5.12.beta5
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.