Opened 10 years ago

Closed 10 years ago

#5932 closed defect (fixed)

[with patch, positive review] graphs.RandomRegular(3,10) often returns a graph on 0 vertices

Reported by: was Owned by: rlm
Priority: major Milestone: sage-4.1.1
Component: graph theory Keywords:
Cc: Merged in: sage-4.1.1.alpha0
Authors: Robert Miller Reviewers: Jason Grout
Report Upstream: Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description

The docstring for graphs.RandomRegular? says

Returns a random d-regular graph on n vertices, or returns False on
failure.

However, try calling it a few times with input 3,10 and with probability about 25% you'll get back an empty graph!:

sage: graphs.RandomRegular(3,10)
Graph on 0 vertices

sage: [len(graphs.RandomRegular(3,10)) for _ in range(1000)].count(0)
232

Attachments (1)

trac_5932.patch (1.3 KB) - added by rlm 10 years ago.

Download all attachments as: .zip

Change History (5)

comment:1 Changed 10 years ago by rlm

This is a bug in NetworkX. Their docstring says:

Definition:     networkx.random_regular_graph(d, n, seed=None)
Source:
def random_regular_graph(d, n, seed=None):
    """Return a random regular graph of n nodes each with degree d, G_{n,d}.
    Return False if unsuccessful.

comment:2 Changed 10 years ago by rlm

  • Summary changed from graphs.RandomRegular(3,10) often returns a graph on 0 vertices to [with patch, needs review] graphs.RandomRegular(3,10) often returns a graph on 0 vertices

Changed 10 years ago by rlm

comment:3 Changed 10 years ago by jason

  • Authors set to Robert Miller
  • Reviewers set to Jason Grout
  • Summary changed from [with patch, needs review] graphs.RandomRegular(3,10) often returns a graph on 0 vertices to [with patch, positive review] graphs.RandomRegular(3,10) often returns a graph on 0 vertices

The fix looks correct, the file passes doctests, and everything looks great!

comment:4 Changed 10 years ago by mvngu

  • Merged in set to sage-4.1.1.alpha0
  • Resolution set to fixed
  • Status changed from new to closed
Note: See TracTickets for help on using tickets.