Opened 11 years ago

Closed 8 years ago

# Odd Girth

Reported by: Owned by: ncohen jason, ncohen, rlm major sage-5.6 graph theory rbeezer sage-5.6.beta0 Jernej Azarija Rob Beezer, Nathann Cohen N/A

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

Apply:

### comment:1 Changed 11 years ago by ncohen

• Status changed from new to needs_work

### comment:2 Changed 8 years ago by kini

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

### comment:3 Changed 8 years ago by 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

### comment:4 Changed 8 years ago by 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!

### Changed 8 years ago by azi

Patch performing the ticket request

### comment:5 Changed 8 years ago by azi

• Status changed from needs_work to needs_review

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.

Last edited 8 years ago by azi (previous) (diff)

### comment:6 Changed 8 years ago by 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

### comment:7 Changed 8 years ago by rbeezer

• Status changed from needs_review to needs_work

### Changed 8 years ago by azi

Second patch implementing the requested comments

### comment:8 Changed 8 years ago by 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.

### comment:9 Changed 8 years ago by azi

• Status changed from needs_work to needs_review

### comment:10 Changed 8 years ago by 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

### comment:11 follow-up: ↓ 12 Changed 8 years ago by azi

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

### comment:12 in reply to: ↑ 11 Changed 8 years ago by rbeezer

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

### comment:13 Changed 8 years ago by azi

• Description modified (diff)

### comment:14 Changed 8 years ago by rbeezer

• Description modified (diff)

"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

### comment:15 Changed 8 years ago by 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)

### comment:16 follow-up: ↓ 18 Changed 8 years ago by ncohen

• Description modified (diff)

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

### comment:17 Changed 8 years ago by kini

Apply trac_8952_odd_girth_consolidated.patch trac_8952_odd_girth-bugfix.patch

### comment:18 in reply to: ↑ 16 Changed 8 years ago by rbeezer

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.

### comment:19 Changed 8 years ago by 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

### comment:20 Changed 8 years ago by 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

### comment:21 Changed 8 years ago by ncohen

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

### comment:22 Changed 8 years ago by azi

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

### comment:23 Changed 8 years ago by ncohen

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

Nathann

### comment:24 Changed 8 years ago by ncohen

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

Nathann

### comment:25 Changed 8 years ago by azi

Looks good to me!

### comment:26 Changed 8 years ago by ncohen

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

Nathann

### comment:27 Changed 8 years ago by ncohen

• Status changed from needs_review to positive_review

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

Nathann

### comment:28 Changed 8 years ago by azi

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

### comment:29 Changed 8 years ago by 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

### comment:30 Changed 8 years ago by 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?

### comment:31 Changed 8 years ago by 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

### comment:32 Changed 8 years ago by azi

• Authors set to Jernej Azarija
• Reviewers set to Jernej Azarija

### comment:33 Changed 8 years ago by azi

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

### comment:34 Changed 8 years ago by kini

• Authors changed from Jernej Azarija to Jernej Azarija, Nathann Cohen
• Reviewers changed from Jernej Azarija to Nathann Cohen, Jernej Azarija

### comment:35 Changed 8 years ago by ncohen

• Authors changed from Jernej Azarija, Nathann Cohen to Jernej Azarija
• Reviewers changed from Nathann Cohen, Jernej Azarija to Rob Beezer, Nathann Cohen, Jernej Azarija

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

Nathann

### comment:36 Changed 8 years ago by kini

• Reviewers changed from Rob Beezer, Nathann Cohen, Jernej Azarija to Rob Beezer, Nathann Cohen

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

### comment:37 Changed 8 years ago by ncohen

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

Nathann

### comment:38 Changed 8 years ago by jdemeyer

Rebased to sage-5.5.rc0.

### comment:39 Changed 8 years ago by jdemeyer

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