Opened 8 years ago

Closed 7 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 ncohen)

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)

trac_11584.patch (20.4 KB) - added by ncohen 7 years ago.
trac_11584-doc.patch (3.5 KB) - added by ncohen 7 years ago.

Download all attachments as: .zip

Change History (16)

comment:1 Changed 8 years ago by ncohen

  • Status changed from new to needs_review

comment:2 follow-up: Changed 7 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 7 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 7 years ago by lsampaio

  • Type changed from PLEASE CHANGE to enhancement

comment:5 Changed 7 years ago by ncohen

  • Component changed from combinatorics to graph theory

(rebased)

Changed 7 years ago by ncohen

comment:6 Changed 7 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
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 7 years ago by ncohen

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

What about this ? :-)

Nathann

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

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

Nathann

comment:10 Changed 7 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 ;-)

Changed 7 years ago by ncohen

comment:11 Changed 7 years ago by ncohen

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

Nathann

comment:12 Changed 7 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 7 years ago by ncohen

Thank you for reviewing it :-)

Nathann

comment:14 Changed 7 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.