Opened 10 years ago
Closed 9 years ago
#11584 closed enhancement (fixed)
DegreeSequences class !
Reported by: | ncohen | Owned by: | sage-combinat |
---|---|---|---|
Priority: | major | Milestone: | sage-5.0 |
Component: | graph theory | Keywords: | |
Cc: | nthiery, mvngu, rmiller | Merged in: | sage-5.0.beta11 |
Authors: | Nathann Cohen | Reviewers: | David Coudert |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
This patch implements the DegreeSequence?
class which lets the user check whether a given integer sequence is indeed a degree sequence, and more importantly build the list of all degree sequences of length n.
I originally wrote this code because I attempted to test a conjecture on "all graphs up to isomorphism", to notice later that there actually was a *large* number of them. There actually was a nice upper bound on what I wanted to measure which only depended on the degree sequence, and here I am.
While it is already hard to enumerate all the graphs on 10 elements, with this code I was able to enumerate the degree sequences on up to 23 vertices (it has been running on the case 24 for two days now) :-D
I also spent a scary amount of time on the documentation, so as to explain how everything works. Let's make Sage's reference manual a math book :-D
Nathann
APPLY:
Attachments (2)
Change History (16)
comment:1 Changed 10 years ago by
- Status changed from new to needs_review
comment:2 follow-up: ↓ 3 Changed 10 years ago by
comment:3 in reply to: ↑ 2 Changed 10 years ago by
It would be great to be able to return all graphs created by this, at least it seems that way to me...
I couldn't agree more, but I have no idea how for the moment :-)
Nathann
comment:4 Changed 10 years ago by
- Type changed from PLEASE CHANGE to enhancement
Changed 9 years ago by
comment:6 Changed 9 years ago by
- Reviewers set to David Coudert
- Status changed from needs_review to needs_work
Hi Nathann,
I tried the patch on sage-5.0.beta8.
- Installation OK
- functionality OK (I can play with degree sequences and generate graphs,...)
- long tests (sage -t --verbose --long -force_lib sage/combinat/degree_sequences.pyx) OK
- docbuild OK
However, I have some minor comments:
- In the html doc, one
min
should be replaced with a\min
63 .. MATH:: 64 \sum_{j\leq i}d_j \leq j(j-1) + \sum_{j>i}min(d_j,i) 65
- The inline doc is rather limited and doesn't look nice.
sage: DegreeSequences? Type: classobj String Form: sage.combinat.degree_sequences.DegreeSequences Namespace: Interactive Loaded File: /path-to-sage/sage-5.0.beta8/local/lib/python2.7/site-packages/sage/combinat/degree_sequences.so Source File: /path-to-sage/sage-5.0.beta8/devel/sage/sage/combinat/degree_sequences.so Docstring: Constructor TEST: sage: DegreeSequences(6) Degree sequences on 6 elements Constructor information: Definition: DegreeSequences(self, n) Docstring: Constructor TEST: sage: DegreeSequences(6) Degree sequences on 6 elements sage:
As soon as these minor comments are addressed, I think the patch will be ready to go.
Best,
D.
comment:7 Changed 9 years ago by
- Description modified (diff)
- Status changed from needs_work to needs_review
What about this ? :-)
Nathann
comment:8 Changed 9 years ago by
Something goes freaky wrong with the extra patch: doctest crash, functionality crash...
sage: DS = DegreeSequences(6) sage: for d in DS: print d .... sage: for d in DS: print d ... [5, 5, 5, 5, 4, 4] [5, 5, 5, 5, 5, 5] *** glibc detected *** python: malloc(): smallbin double linked list corrupted: 0x0b7cd2a8 ***
I have no idea where the problem comes from :(
comment:9 Changed 9 years ago by
OOoops... Yep, it comes from the sage_free I added ^^;
Nathann
comment:10 Changed 9 years ago by
The patch is OK (docbuild, install, long tests,...) and the message is much better now.
Please change For moe information
with For more information
, and then the patch will be perfect ;-)
Changed 9 years ago by
comment:11 Changed 9 years ago by
I do not stand these laptop keywords... Sorry 'bout that :-p
Nathann
comment:12 Changed 9 years ago by
- Status changed from needs_review to positive_review
For me the patch is now in good shape. Nice work Nathann.
comment:13 Changed 9 years ago by
Thank you for reviewing it :-)
Nathann
comment:14 Changed 9 years ago by
- Merged in set to sage-5.0.beta11
- Resolution set to fixed
- Status changed from positive_review to closed
Interesting. A long time ago I was hoping one could have Sage create more than one graph from a given degree sequence. Currently we just have H-H in one way:
It would be great to be able to return all graphs created by this, at least it seems that way to me...