Add more graph generators

[sagetrac-myurko]

This patch add graph generators for the hyper star, (n,k)-star, n-star, and bubble sort graph.

Component: graph theory

Author: Michael Yurko

Reviewer: Jason Grout, Minh Van Nguyen

Merged: Sage 4.1.2.alpha4

Issue created by migration from https://trac.sagemath.org/ticket/6859

[sagetrac-myurko]

Attachment: trac_6859.patch.gz

[nathanncohen]

comment:2

Would it be possible to add to the docstrings the definition of what these graphs should be ?

Nathann

[sagetrac-myurko]

comment:3

Sure. I'll add definitions.

[nathanncohen]

comment:4

I do not know if you are aware of it ( I was not until very recently ) but the docstrings are used to generate a very complete documentation accessible through there :

http://www.sagemath.org/doc/reference/graphs.html

This also means that you can use LaTeX in your description if you deem it necessary, and that the formula will be automatically translated into beautiful equations on this page ;-)

Nathann

[sagetrac-myurko]

comment:5

Well, I knew that you can use Latex in docstrings, but I tried not to use it since it is hard to read when introspecting.

[sagetrac-myurko]

Attachment: trac_6859_definitions.patch.gz

Adds definitions of graphs to docstrings

[jasongrout]

comment:7

Very nice.

I'm attaching a patch which optimizes some of the code to use more python things (like swapping), plus fixes a few typos. I think someone needs to review my patch.

[jasongrout]

Attachment: trac-6859-optimize.patch.gz

apply on top of previous patches

[sagetrac-myurko]

comment:8

I obviously can't review the patch, but the swapping certainly looks better. Coding too long in java has made forget some of the nice python idioms.

[jasongrout]

comment:9

Okay, positive review for your patch.

You can review my changes (just make sure that you still get the same graphs). If you okay my changes, change this ticket to "positive review".

[sagetrac-myurko]

comment:10

All the graphs except the n,k star graph worked still. However, it was just a one line fix to keep the v[0] = tmp_bit line inside the for loop (otherwise all the vertices become looped). I've uploaded a one line patch to fix it.

[sagetrac-myurko]

Attachment: trac-6859-optimize-fix.patch.gz

[jasongrout]

comment:11

ah, right. Okay, then, positive review.

[sagetrac-mvngu]

comment:12

The patch trac_6859-ascii-chars.patch uses only ASCII characters for quotation marks and long dashes. Without it, merging trac_6859.patch and building the reference manual would result in the following error:

reading sources... sage/graphs/graph_generators /scratch/mvngu/release/sage-4.1.2.alpha2/local/lib/python2.6/site-packages/Sphinx-0.5.1-py2.6.egg/sphinx/environment.py:543: DeprecationWarning: BaseException.message has been deprecated as of Python 2.6
  raise SphinxError(err.message)
Sphinx error:

[sagetrac-mvngu]

use ASCII characters for quotation marks and long dashes

[sagetrac-mvngu]

Attachment: trac_6859-ascii-chars.patch.gz

Attachment: trac_6859-formatting-issues.patch.gz

proper formatting of lists

[sagetrac-mvngu]

comment:13

The patch trac_6859-formatting-issues.patch fixes formatting of lists. Without it, I get the following warnings when building the reference manual:

WARNING: /scratch/mvngu/release/sage-4.1.2.alpha2/local/lib/python2.6/site-packages/sage/graphs/graph_generators.py:docstring of sage.graphs.graph_generators.GraphGenerators.HyperStarGraph:22: (WARNING/2) Bullet list ends without a blank line; unexpected unindent.
WARNING: /scratch/mvngu/release/sage-4.1.2.alpha2/local/lib/python2.6/site-packages/sage/graphs/graph_generators.py:docstring of sage.graphs.graph_generators.GraphGenerators.NKStarGraph:25: (WARNING/2) Bullet list ends without a blank line; unexpected unindent.
WARNING: /scratch/mvngu/release/sage-4.1.2.alpha2/local/lib/python2.6/site-packages/sage/graphs/graph_generators.py:docstring of sage.graphs.graph_generators.GraphGenerators.NStarGraph:19: (WARNING/2) Bullet list ends without a blank line; unexpected unindent.

[sagetrac-mvngu]

Reviewer: Jason Grout, Minh Van Nguyen

[sagetrac-mvngu]

comment:14

Merged patches in this order:

1. trac_6859.patch
2. trac_6859-ascii-chars.patch
3. trac_6859_definitions.patch
4. trac-6859-optimize.patch
5. trac-6859-optimize-fix.patch
6. trac_6859-formatting-issues.patch

[sagetrac-mvngu]

Author: Michael Yurko

[sagetrac-mvngu]

Merged: Sage 4.1.2.alpha3

[sagetrac-mvngu]

Changed merged from Sage 4.1.2.alpha3 to Sage 4.1.2.alpha4

[sagetrac-mvngu]

comment:15

There is no 4.1.2.alpha3. Sage 4.1.2.alpha3 was William Stein's release for working on making the notebook a standalone package.