Opened 9 years ago

Closed 8 years ago

# DegreeSequences class !

Reported by: Owned by: ncohen sage-combinat major sage-5.0 graph theory nthiery, mvngu, rmiller sage-5.0.beta11 Nathann Cohen David Coudert N/A

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:

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

• Status changed from new to needs_review

### comment:2 follow-up: ↓ 3 Changed 9 years ago by kcrisman

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:

    def DegreeSequence(self, deg_sequence):
"""
Returns a graph with the given degree sequence. Raises a NetworkX
error if the proposed degree sequence cannot be that of a graph.

Graph returned is the one returned by the Havel-Hakimi algorithm,
which constructs a simple graph by connecting vertices of highest
degree to other vertices of highest degree, resorting the remaining
vertices by degree and repeating the process. See Theorem 1.4 in
[1].

        import networkx
return graph.Graph(networkx.havel_hakimi_graph([int(i) for i in deg_sequence])


It would be great to be able to return all graphs created by this, at least it seems that way to me...

### comment:3 in reply to: ↑ 2 Changed 9 years ago by ncohen

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 9 years ago by lsampaio

• Type changed from PLEASE CHANGE to enhancement

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

• Component changed from combinatorics to graph theory

(rebased)

### comment:6 Changed 8 years ago by dcoudert

• 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
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 8 years ago by ncohen

• Description modified (diff)
• Status changed from needs_work to needs_review

What about this ? :-)

Nathann

### comment:8 Changed 8 years ago by dcoudert

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 8 years ago by ncohen

OOoops... Yep, it comes from the sage_free I added ^^;

Nathann

### comment:10 Changed 8 years ago by dcoudert

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

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

I do not stand these laptop keywords... Sorry 'bout that :-p

Nathann

### comment:12 Changed 8 years ago by dcoudert

• Status changed from needs_review to positive_review

For me the patch is now in good shape. Nice work Nathann.

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

Thank you for reviewing it :-)

Nathann

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

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