Opened 9 years ago

Closed 9 years ago

#7487 closed enhancement (fixed)

Random Interval Graphs

Reported by: ncohen Owned by: rlm
Priority: major Milestone: sage-4.3
Component: graph theory Keywords:
Cc: Merged in: sage-4.3.alpha1
Authors: Nathann Cohen Reviewers: Mike Hansen
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by ncohen)

This patch definesRandom Interval Graph, as explained in the docstring : 

        An interval graph is built from a list `(a_i,b_i)_{1\leq i \leq n}`                                                                          
        of intervals : to each interval of the list is associated one                                                                                
        vertex, two vertices being adjacent if the two corresponding                                                                                 
        intervals intersect.                                                                                                                         
	                                                                                                                                             
        A random interval graph of order `n` is generated by picking                                                                                 
        random values for the `(a_i,b_j)`, each of the two coordinates                                                                               
        being generated from the uniform distribution on the interval                                                                                
        `[0,1]`.

Attachments (2)

trac_7487.patch​ (2.9 KB) - added by ncohen 9 years ago.
trac_7487-review.patch​ (1.3 KB) - added by mhansen 9 years ago.

Download all attachments as: .zip

Change History (6)

comment:1 Changed 9 years ago by ncohen

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

Changed 9 years ago by ncohen

Changed 9 years ago by mhansen

comment:2 Changed 9 years ago by mhansen

  • Authors set to Nathann Cohen
  • Report Upstream set to N/A
  • Reviewers set to Mike Hansen

The patch looks mostly good to me with the exception of the changes I made.

Tuples already sort based on their first component (then second, etc.). Also, I decreased the size of the example so that the chromatic number didn't take too long to compute.

Could you look at these changes?

comment:3 Changed 9 years ago by ncohen

  • Status changed from needs_review to positive_review

Looks ok ! :-)

I should have thought of directly using sort instead of this lambda-function.. And I forgot that the default behaviour of sort on tuples was to use the lexicographic order, which is perfect in this case.... :-)

If you have some time for reviews ( as you merged an amazing amount of patches today ! ) could you take a look at #6680 or #6679 ? I'd understand if you could not, I know it would take much more time than for others, but these two patches are the real blockers in the graph section...

Thanks !!! :-)

Nathann

comment:4 Changed 9 years ago by mhansen

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