Opened 8 years ago

Closed 7 years ago

Last modified 7 years ago

#11099 closed enhancement (fixed)

digraphs.RandomDirectedGNM

Reported by: ncohen Owned by: jason, ncohen, rlm
Priority: major Milestone: sage-4.8
Component: graph theory Keywords:
Cc: Merged in: sage-4.8.alpha0
Authors: Nathann Cohen Reviewers: David Coudert
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description

We have graphs.RandomGNP and graphs.RandomGNM but the GNM version is missing for directed graphs.

This is an implementation which will be faster once the .complement() method of SparseGraph? will have been reimplemented...

Nathann

Attachments (1)

trac_11099.patch (5.6 KB) - added by ncohen 7 years ago.

Download all attachments as: .zip

Change History (14)

comment:1 Changed 8 years ago by ncohen

  • Status changed from new to needs_review

comment:2 Changed 7 years ago by dcoudert

  • Reviewers set to David Coudert
  • Status changed from needs_review to needs_work

The current function works fine. However, it would be suitable to allow the generation of random digraphs with loops (I use such digraphs).

Thanks.

comment:3 Changed 7 years ago by ncohen

  • Status changed from needs_work to needs_review

Hello !

Here is an updated patch, that supports loops. This being said, the custom on Sage's trac server is more to provide a patch yourself if you think a feature you need should be added (and to join the reviewer's patch to the ticket when fitting) :-p

Nathann

comment:4 Changed 7 years ago by ncohen

Ok, by email David told me that he had a more efficient version of this method, using dictionaries to cache the edges and improve the has_edge test.

to David : I hope you will like this new version. While I was at it, I also looked a bit into random number generation, and ... well.. There was some speedup hidden there too :-)

The code comes with its comments.

Nathann

comment:5 follow-up: Changed 7 years ago by ncohen

After a few comments from David by email :

  • There was a weird "80" somewhere in the comments
  • binary only means boolean in linear programs, not in the documentation :-D

Updaaaaaaaaaaated !

Nathann

comment:6 in reply to: ↑ 5 ; follow-up: Changed 7 years ago by dcoudert

Replying to ncohen:

After a few comments from David by email :

  • There was a weird "80" somewhere in the comments
  • binary only means boolean in linear programs, not in the documentation :-D

Updaaaaaaaaaaated !

Nathann

Can you make the updated version available. So far I still see the "binary" instead of "boolean" line 474 and the "80" line 571.

David.

comment:7 in reply to: ↑ 6 Changed 7 years ago by ncohen

Can you make the updated version available.

Stupid me. O_o

Done ! :-D

Changed 7 years ago by ncohen

comment:8 follow-up: Changed 7 years ago by dcoudert

  • Status changed from needs_review to positive_review

The last version of the patch is working fine and definitively faster than the previous versions. The doc is OK.

My review is thus positive.

Thanks Nathann.

comment:9 in reply to: ↑ 8 Changed 7 years ago by ncohen

Thanks Nathann.

Nono, it's me, it's me ! It's a pleasure to code when the patches are reviewed that quickly :-D

Nathann

comment:10 Changed 7 years ago by jdemeyer

  • Milestone changed from sage-4.7.2 to sage-4.7.3

comment:11 Changed 7 years ago by jdemeyer

  • Merged in set to sage-4.7.3.alpha0
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:12 Changed 7 years ago by jdemeyer

  • Milestone sage-4.7.3 deleted

Milestone sage-4.7.3 deleted

comment:13 Changed 7 years ago by jdemeyer

  • Merged in changed from sage-4.7.3.alpha0 to sage-4.8.alpha0
  • Milestone set to sage-4.8
Note: See TracTickets for help on using tickets.