#14980: graph_generators, some more clean up
----------------------------------+----------------------------
Reporter: eisermbi | Owner:
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-5.12
Component: graph theory | Resolution:
Keywords: | Merged in:
Authors: Birk Eisermann | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
Dependencies: | Stopgaps:
----------------------------------+----------------------------
Changes (by {'newvalue': u'Birk Eisermann', 'oldvalue': ''}):
* status: needs_info => needs_review
* author: => Birk Eisermann
Old description:
> 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.
>
> * HararyGraph is a family of graphs.
>
> Note that some graphs in this section are not really small! Actually, I'd
> find
> it better to called the section "individual graphs" (as on
> https://en.wikipedia.org/wiki/Gallery_of_named_graphs) or stick with the
> previous
> term "named graphs". (The renaming to "small graphs" happened in #13862.
> Sorry, I do not know the reason...)
>
> 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'')
>
> Note, the formatting of the references in html (of RandomGNP) looks odd?!
> Don't know what is wrong or how to correct this...
>
> Part 3
> * creating "Miscellaneous" section and renaming "world_map.py" to
> "miscellaneous.py"
>
> * `cospectral_graphs`, `line_graph_forbidden_subgraphs`, `fullerences`,
> `trees`
> are not single graphs nor families of graphs; moving them in
> "Miscellaneous";
>
> (Alternatively, one might leave them directly under "Graph Generators"
> without any section header the functions `canaug_traverse_edge`,
> `canaug_traverse_vert`, `check_aut`, `check_aut_edge`...)
>
> Part 4
> * Basic structures / "Some Commonly Used Graph": Actually these graphs
> can be listed in the other classes. Hence, I moved them to their
> corresponding section but sometimes left copies in this section, renamed
> to "commonly used graph generators".
>
> That is,
> "BarbellGraph", "CircularLadderGraph", "CycleGraph",
> "CompleteBipartiteGraph",
> "CompleteGraph", "CompleteMultipartiteGraph", "Grid2dGraph",
> "GridGraph",
> "PathGraph", "LadderGraph", "StarGraph", "ToroidalGrid2dGraph",
> "Toroidal6RegularGrid2dGraph", "WheelGraph" are families of graphs.
>
> "BuckyBall", "BullGraph", "ButterflyGraph", "ClawGraph",
> "DiamondGraph",
> "EmptyGraph", "HouseGraph", "HouseXGraph", "KrackhardtKiteGraph",
> "LollipopGraph"
> are "small graphs" ("named graphs").
>
> In other words, the most important graphs/graph families can be
> ''double listed''
> to make it easier to find them. Yes, "most important graphs" is, of
> course,
> subjective but these graphs are now double listed anyway. I would
> choose graphs
> that are important to new users of SAGE.
>
> Alternatively, this section might be removed completely and the example
> above might be expanded... (Maybe this would the better solution.)
>
> * removal of file "basic.py" (some kind of deprecation needed?)
New description:
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.
* HararyGraph is a family of graphs.
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'')
* NEW: {{{benzenoids}}} is replaced by {{{fusenes}}} in
{{{__append_to_doc}}}.
Part 3 (not 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.
----
'''Apply:'''
- [attachment:trac_14980-part1_docu.patch]
- [attachment:trac_14980-part2_docu.patch]
- [attachment:trac_14980-part4_basic.patch]
--
Comment:
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
--
Ticket URL: <http://trac.sagemath.org/ticket/14980#comment:5>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/groups/opt_out.
