Odd Girth #8952

nathanncohen · 2010-05-12T00:24:22Z

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

Apply:

CC: @rbeezer

Component: graph theory

Author: Jernej Azarija

Reviewer: Rob Beezer, Nathann Cohen

Merged: sage-5.6.beta0

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

kini · 2012-09-25T18:08:05Z

comment:2

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

nathanncohen · 2012-09-25T18:10:14Z

comment:3

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 · 2012-09-25T18:28:28Z

comment:4

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

sagetrac-azi · 2012-09-25T22:20:08Z

Attachment: trac_8952_odd_girth.patch.gz

Patch performing the ticket request

sagetrac-azi · 2012-09-25T22:21:21Z

comment:5

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 · 2012-09-26T02:51:40Z

comment:6

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

sagetrac-azi · 2012-09-26T16:38:33Z

Second patch implementing the requested comments

sagetrac-azi · 2012-09-26T16:39:52Z

comment:8

Attachment: trac_8952_odd_girth_second.patch.gz

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 · 2012-09-26T17:20:50Z

comment:10

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

sagetrac-azi · 2012-09-26T17:45:39Z

comment:11

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

rbeezer · 2012-09-26T19:15:59Z

comment:12

Replying to @sagetrac-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 · 2012-09-30T19:15:33Z

comment:14

"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 -

Start with a clean Sage installation (even if it means installing from source).
Install a system version of Mercurial, or replace "hg" commands with "sage -hg"
hg import (get URL from tiny download icon, not web-view of patch)
hg qpush (to apply patch)
Rebuild sage, edit source, make changes, etc, etc.
hg qrefresh -m ""
hg export qtip >
hg qpop (to move changes out of the way, and get back to original Sage, rebuild, etc)

You can use "hg qnew " 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

nathanncohen · 2012-10-01T13:51:21Z

comment:15

(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)

nathanncohen · 2012-10-02T13:20:31Z

comment:21

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

sagetrac-azi · 2012-10-27T13:23:48Z

comment:22

Attachment: trac_8952_odd_girth-bugfix.patch.gz

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

nathanncohen · 2012-10-27T22:16:24Z

comment:23

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

Nathann

nathanncohen · 2012-11-05T15:48:09Z

comment:24

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

Nathann

sagetrac-azi · 2012-11-05T16:05:01Z

comment:25

Looks good to me!

nathanncohen · 2012-11-05T16:06:26Z

comment:26

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

Nathann

nathanncohen · 2012-11-17T16:36:42Z

comment:27

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

Nathann

sagetrac-azi · 2012-11-17T16:44:26Z

comment:28

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

nathanncohen · 2012-11-17T16:51:41Z

comment:29

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

sagetrac-azi · 2012-11-17T18:35:32Z

comment:30

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?

nathanncohen · 2012-11-17T18:40:27Z

comment:31

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

sagetrac-azi · 2012-11-17T18:48:46Z

Reviewer: Jernej Azarija

sagetrac-azi · 2012-11-17T18:48:46Z

Author: Jernej Azarija

sagetrac-azi · 2012-11-17T18:49:06Z

comment:33

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

kini · 2012-11-17T18:56:13Z

Changed reviewer from Jernej Azarija to Nathann Cohen, Jernej Azarija

kini · 2012-11-17T18:56:13Z

Changed author from Jernej Azarija to Jernej Azarija, Nathann Cohen

nathanncohen · 2012-11-17T19:03:52Z

Changed author from Jernej Azarija, Nathann Cohen to Jernej Azarija

nathanncohen · 2012-11-17T19:03:52Z

comment:35

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

Nathann

nathanncohen · 2012-11-17T19:03:52Z

Changed reviewer from Nathann Cohen, Jernej Azarija to Rob Beezer, Nathann Cohen, Jernej Azarija

kini · 2012-11-17T19:08:35Z

comment:36

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

kini · 2012-11-17T19:08:35Z

Changed reviewer from Rob Beezer, Nathann Cohen, Jernej Azarija to Rob Beezer, Nathann Cohen

nathanncohen · 2012-11-17T19:14:44Z

comment:37

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

Nathann

jdemeyer · 2012-12-16T15:35:44Z

Attachment: trac_8952_odd_girth_consolidated.patch.gz

jdemeyer · 2012-12-16T15:36:02Z

comment:38

Rebased to sage-5.5.rc0.

jdemeyer · 2012-12-18T11:14:28Z

Merged: sage-5.6.beta0

nathanncohen mannequin added this to the sage-5.6 milestone May 12, 2010

nathanncohen mannequin added c: graph theory labels May 12, 2010

nathanncohen mannequin assigned jasongrout, nathanncohen and rlmill May 12, 2010

nathanncohen mannequin added the s: needs work label Jun 6, 2010

sagetrac-azi mannequin added s: needs review and removed s: needs work labels Sep 25, 2012

rbeezer mannequin added s: needs work and removed s: needs review labels Sep 26, 2012

sagetrac-azi mannequin added s: needs review and removed s: needs work labels Sep 26, 2012

This comment has been minimized.

Sign in to view

nathanncohen mannequin added s: positive review and removed s: needs review labels Nov 17, 2012

jdemeyer removed the s: positive review label Dec 18, 2012

jdemeyer closed this as completed Dec 18, 2012

sagetrac-azi mannequin mentioned this issue Feb 9, 2013

Bug in is_perfect #13546

Closed

Odd Girth #8952

Odd Girth #8952

Comments

nathanncohen mannequin commented May 12, 2010

kini commented Sep 25, 2012

nathanncohen mannequin commented Sep 25, 2012

kini commented Sep 25, 2012

sagetrac-azi mannequin commented Sep 25, 2012

sagetrac-azi mannequin commented Sep 25, 2012

rbeezer mannequin commented Sep 26, 2012

sagetrac-azi mannequin commented Sep 26, 2012

sagetrac-azi mannequin commented Sep 26, 2012

rbeezer mannequin commented Sep 26, 2012

sagetrac-azi mannequin commented Sep 26, 2012

rbeezer mannequin commented Sep 26, 2012

This comment has been minimized.

rbeezer mannequin commented Sep 30, 2012

This comment has been minimized.

nathanncohen mannequin commented Oct 1, 2012

This comment has been minimized.

nathanncohen mannequin commented Oct 2, 2012

sagetrac-azi mannequin commented Oct 27, 2012

nathanncohen mannequin commented Oct 27, 2012

nathanncohen mannequin commented Nov 5, 2012

sagetrac-azi mannequin commented Nov 5, 2012

nathanncohen mannequin commented Nov 5, 2012

nathanncohen mannequin commented Nov 17, 2012

sagetrac-azi mannequin commented Nov 17, 2012

nathanncohen mannequin commented Nov 17, 2012

sagetrac-azi mannequin commented Nov 17, 2012

nathanncohen mannequin commented Nov 17, 2012

sagetrac-azi mannequin commented Nov 17, 2012

sagetrac-azi mannequin commented Nov 17, 2012

sagetrac-azi mannequin commented Nov 17, 2012

kini commented Nov 17, 2012

kini commented Nov 17, 2012

nathanncohen mannequin commented Nov 17, 2012

nathanncohen mannequin commented Nov 17, 2012

nathanncohen mannequin commented Nov 17, 2012

kini commented Nov 17, 2012

kini commented Nov 17, 2012

nathanncohen mannequin commented Nov 17, 2012

jdemeyer commented Dec 16, 2012

jdemeyer commented Dec 16, 2012

jdemeyer commented Dec 18, 2012