Odd Girth

[ncohen]

Add a function to compute odd girth of a graph G.

Apply:

1. trac_8952_odd_girth_consolidated.patch​
2. trac_8952_odd_girth-bugfix.patch​

[kini]

What needs work here exactly? There's no patch on this ticket.

[ncohen]

Well, nothing actually. I used to use the Trac server as my todo-list, a loooong time ago, so you will find many such tickets in this section ^^;

I am (desperately) looking for a flat in Paris right now, but I should stop sinking and start swimming in a couple of weeks.

I hope that all is well on you side !! :-)

Nathann

[kini]

Haha, OK :) I found this ticket because someone asked about it on IRC and wants to work on it. Good luck with your flat!

[azi]

Patch performing the ticket request

[azi]

Hello!

Attached is the patch that should perform the required task. odd_girth() computes the odd girth of a graph using a property of the characteristic polynomial of the adjacency matrix. Its (theoretic) computational complexity is optimal.

[rbeezer]

Azi,

I took a quick look and it looks promising, especially since characteristic polynomials are quite fast in Sage. I can look closer when I have a bit more time.

For now, documentation needs some work. For example:

Any complete graph on more than 2 vertices contains a triangle and has thus odd girth 3 

	            G = graphs.CompleteGraph(10) 
	            sage: G.odd_girth() 
	            3

needs a double colon after the lead-in sentence (all 3 of your verbatim blocks need this). And your line creating the complete graph needs a sage: preceding it.

Current documentation style needs "INPUT" and "OUTPUT" blocks - look around for examples. They will be pretty simple in this case.

You can catch some of these yourself:

sage -b
sage -docbuild reference html

will rebuild the documentation and you can view the html file for mess-ups with the doc string.

And

sage -t <source file>

will find broken tests.

Rob

[azi]

Second patch implementing the requested comments

[azi]

I have added a patch (hopefully valid) with the commends you requested. There is still one missing warning in building the documentation (Literal block expected; none found." is likely an indentiation problem and/or a problem with a double-colon) which I was not able to spot.

[rbeezer]

Dear Azi,

Your "literal block expected" error is caused by a double-colon after "EXAMPLES". It should be a single, just to be typeset as-is. A double-colon says verbatim (literal) stuff comes next.

The patch looks severely messed-up to me. ;-( I am not all sure how you got it to that state, but I think I can fix it. Are you using clones or Mercurial queues? Queues are much easier to deal with, and easier for iterative changes like this.

Don't try to fix the double-colon until I fix the patch (maybe later today).

Rob

[azi]

The patch was produced using the following guide http://www.sagemath.org/doc/developer/walk_through.html#creating-a-change

[rbeezer]

Replying to azi:

The patch was produced using the following guide http://www.sagemath.org/doc/developer/walk_through.html#creating-a-change

Well, I sort of hope not, since I wrote that guide. ;-) It looks like something wasn't done quite right.

Guide discusses two approaches: clones and queues. I cannot even begin to help if I don't know which approach you are taking. Let me know.

Rob

[rbeezer]

"consolidated" patch has previous work in one (proper) patch - still has azi's name on it, too.

See new "Apply" section in ticket description.

Azi -

1. Start with a clean Sage installation (even if it means installing from source).
2. Install a system version of Mercurial, or replace "hg" commands with "sage -hg"
3. hg import <URL-to-consolidated-patch> (get URL from tiny download icon, not web-view of patch)
4. hg qpush (to apply patch)
5. Rebuild sage, edit source, make changes, etc, etc.
6. hg qrefresh -m "<A possible new message for patch summary goes here>"
7. hg export qtip > <file-name-for-revised-patch>
8. hg qpop (to move changes out of the way, and get back to original Sage, rebuild, etc)

You can use "hg qnew <private-name-for-patch>" to initiate a new project with no interference from previous one. You can easily manage several activities with qpop/qpush, and "hg qpush --move" will allow applying patches out of order. "hg qapplied", "hg qunapplied" are informative. Hope this is helpful.

Rob

[ncohen]

(same patch with the max 80 characters per line that Minh taught me to respect in the Graph files, some links between odd_girth and girth, and some modifications in the doc so that Sphinx gets what it should)

[ncohen]

Ahem...

sage: graphs.CycleGraph(5).odd_girth()
+Infinity

With this additional patch, the functions looks more similar to what page 45 of "Algebraic Graph Theory" seems to say :-)

Nathann

[kini]

Apply trac_8952_odd_girth_consolidated.patch trac_8952_odd_girth-bugfix.patch

[rbeezer]

Replying to ncohen:

With this additional patch, the functions looks more similar to what page 45 of "Algebraic Graph Theory" seems to say :-)

I'd been meaning to suggest stepping by -2, mostly for clarity, and less code. I hadn't realized there was a problem, though! Good catch.

[ncohen]

There is always a problem when a book decides to write \sum_i c_{n-i} x^i instead of \sum_i c_{i} x^i :-P

In the end what do we do with this ticket ? 3 peoples modified the patch already :-D

To me it looks good as it is...

Nathann

[ncohen]

HMmmmmmmm.... I guess I shouldn't put a 's' at the end of "people". And I guess I should have said "persons" instead, by the way :-)

Nathann

[ncohen]

(just updated the patch so that is_odd_hole_free uses this function too !!!)

[azi]

The patch looks good to me. Am I allowed to change the status of the ticket to reflect that?

[ncohen]

Well I guess you can if you think the patch is ready :-)

Nathann

[ncohen]

Ahem. Does everybody here agree that this patch should be merged ?

Nathann

[azi]

Looks good to me!

[ncohen]

Ok, fine then... Could you set it to positive_review ? I'm the last one who added something to the ticket :-)

Nathann

[ncohen]

Okayyyyyyyyyyyyyyyyyy.................. :-P

Nathann

[azi]

I am sorry. I completely overlooked the "set it to positive_review" part.

[ncohen]

No problem. Could you add your name to the list of reviewers/authors ? And if possible to the list in "​http://trac.sagemath.org/sage_trac/wiki" too :-)

Nathann

[azi]

OK. I have added myself to the wiki link. But I can't find the list of reviewers/authors. Do you happen to know where do I find that?

[ncohen]

Ahahaah. It's on this page, on the "Modify Ticket" section. When a ticket is positively reviewed, the list of authors and reviewers has to be filled. I often forget that myself :-)

Nathann

[azi]

Oooh ok! I suppose you will add yourself to the list right?

[ncohen]

Well, I'm not really an author of this ticket, and Rob did some of it too :-)

Nathann

[kini]

If azi is the only author, then he cannot be a reviewer...

[ncohen]

AHahah. If that's the law, then...:-)

Nathann

[jdemeyer]

Rebased to sage-5.5.rc0.