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: |
Description (last modified by )
Add a function to compute odd girth of a graph G.
Apply:
Attachments (4)
Change History (43)
comment:1 Changed 11 years ago by
- Status changed from new to needs_work
comment:2 Changed 8 years ago by
comment:3 Changed 8 years ago by
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
Haha, OK :) I found this ticket because someone asked about it on IRC and wants to work on it. Good luck with your flat!
comment:5 Changed 8 years ago by
- 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.
comment:6 Changed 8 years ago by
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
- Status changed from needs_review to needs_work
comment:8 Changed 8 years ago by
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
- Status changed from needs_work to needs_review
comment:10 Changed 8 years ago by
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
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
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 8 years ago by
- Description modified (diff)
comment:14 Changed 8 years ago by
- 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 -
- 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 <URL-to-consolidated-patch> (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 "<A possible new message for patch summary goes here>"
- hg export qtip > <file-name-for-revised-patch>
- 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
(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
- 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
Apply trac_8952_odd_girth_consolidated.patch trac_8952_odd_girth-bugfix.patch
comment:18 in reply to: ↑ 16 Changed 8 years ago by
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 8 years ago by
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
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
(just updated the patch so that is_odd_hole_free uses this function too !!!)
Changed 8 years ago by
comment:22 Changed 8 years ago by
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
Well I guess you can if you think the patch is ready :-)
Nathann
comment:24 Changed 8 years ago by
Ahem. Does everybody here agree that this patch should be merged ?
Nathann
comment:25 Changed 8 years ago by
Looks good to me!
comment:26 Changed 8 years ago by
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
- Status changed from needs_review to positive_review
Okayyyyyyyyyyyyyyyyyy.................. :-P
Nathann
comment:28 Changed 8 years ago by
I am sorry. I completely overlooked the "set it to positive_review" part.
comment:29 Changed 8 years ago by
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
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
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
- Reviewers set to Jernej Azarija
comment:33 Changed 8 years ago by
Oooh ok! I suppose you will add yourself to the list right?
comment:34 Changed 8 years ago by
- Reviewers changed from Jernej Azarija to Nathann Cohen, Jernej Azarija
comment:35 Changed 8 years ago by
- 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
- 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
AHahah. If that's the law, then...:-)
Nathann
Changed 8 years ago by
comment:38 Changed 8 years ago by
Rebased to sage-5.5.rc0.
comment:39 Changed 8 years ago by
- Merged in set to sage-5.6.beta0
- Resolution set to fixed
- Status changed from positive_review to closed
What needs work here exactly? There's no patch on this ticket.