Opened 11 years ago

Closed 8 years ago

#8952 closed enhancement (fixed)

Odd Girth

Reported by: ncohen Owned by: jason, ncohen, rlm
Priority: major Milestone: sage-5.6
Component: graph theory Keywords:
Cc: rbeezer Merged in: sage-5.6.beta0
Authors: Jernej Azarija Reviewers: Rob Beezer, Nathann Cohen
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by 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

Attachments (4)

trac_8952_odd_girth.patch (2.8 KB) - added by azi 9 years ago.
Patch performing the ticket request
trac_8952_odd_girth_second.patch (7.9 KB) - added by azi 9 years ago.
Second patch implementing the requested comments
trac_8952_odd_girth-bugfix.patch (1.8 KB) - added by ncohen 9 years ago.
trac_8952_odd_girth_consolidated.patch (3.4 KB) - added by jdemeyer 8 years ago.

Download all attachments as: .zip

Change History (43)

comment:1 Changed 11 years ago by ncohen

  • Status changed from new to needs_work

comment:2 Changed 9 years ago by kini

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

comment:3 Changed 9 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 9 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 9 years ago by azi

Patch performing the ticket request

comment:5 Changed 9 years ago by azi

  • Cc rbeezer added
  • 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 9 years ago by azi (previous) (diff)

comment:6 Changed 9 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 9 years ago by rbeezer

  • Status changed from needs_review to needs_work

Changed 9 years ago by azi

Second patch implementing the requested comments

comment:8 Changed 9 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 9 years ago by azi

  • Status changed from needs_work to needs_review

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

comment:13 Changed 9 years ago by azi

  • Description modified (diff)

comment:14 Changed 9 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 9 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: Changed 9 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 9 years ago by kini

Apply trac_8952_odd_girth_consolidated.patch trac_8952_odd_girth-bugfix.patch

comment:18 in reply to: ↑ 16 Changed 9 years ago by 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.

comment:19 Changed 9 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 9 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 9 years ago by ncohen

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

Changed 9 years ago by ncohen

comment:22 Changed 9 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 9 years ago by ncohen

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

Nathann

comment:24 Changed 9 years ago by ncohen

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

Nathann

comment:25 Changed 9 years ago by azi

Looks good to me!

comment:26 Changed 9 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

Changed 8 years ago by jdemeyer

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.