DegreeSequences class !

[nathanncohen]

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:

• attachment: trac_11584.patch
• attachment: trac_11584-doc.patch

CC: @nthiery @sagetrac-mvngu

Component: graph theory

Author: Nathann Cohen

Reviewer: David Coudert

Merged: sage-5.0.beta11

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

[kcrisman]

comment:2

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

[nathanncohen]

comment:3

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

[nathanncohen]

comment:5

(rebased)

[dcoudert]

comment:6

Attachment: trac_11584.patch.gz

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.

[dcoudert]

Reviewer: David Coudert

[nathanncohen]

comment:7

What about this ? :-)

Nathann

[dcoudert]

comment:8

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

[nathanncohen]

comment:9

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

Nathann

[dcoudert]

comment:10

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

[nathanncohen]

comment:11

Attachment: trac_11584-doc.patch.gz

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

Nathann

[dcoudert]

comment:12

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

[nathanncohen]

comment:13

Thank you for reviewing it :-)

Nathann

[jdemeyer]

Merged: sage-5.0.beta11