Opened 6 years ago

Closed 5 years ago

#12181 closed defect (fixed)

random_DAG does not terminate on it's default inputs

Reported by: mderickx Owned by: tbd
Priority: major Milestone: sage-5.3
Component: graph theory Keywords: random digraph
Cc: Merged in: sage-5.3.beta2
Authors: Douglas McNeil, Frédéric Chapoton Reviewers: David Coudert
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by chapoton)

Try:

random_DAG(5)

it will run forever!

apply only trac_12181_random_dag-fc.patch

Attachments (1)

trac_12181_random_dag-fc.patch (3.4 KB) - added by chapoton 5 years ago.

Download all attachments as: .zip

Change History (27)

comment:1 in reply to: ↑ description Changed 6 years ago by bbanu

  • Description modified (diff)

Replying to mderickx:

Try:

random_DAG(5)

it will run forever!

comment:2 in reply to: ↑ description Changed 6 years ago by bbanu

  • Description modified (diff)

Replying to mderickx:

Try:

random_DAG(5)

it will run forever!

It appears it is stuck in /local/lib/python2.6/site-packages/sage/sandpiles/sandpile.pyc at

4904 for j in range(i):

-> 4905 if p > random(): This is the same behavior as

random_DAG(5, 0)

It appears p=1/2 from the definition of random_DAG is evaluated to 0 (so there are no possible connections), hence p = 0.5 should fix it.

comment:3 Changed 6 years ago by bbanu

It appears it is stuck in /local/lib/python2.6/site-packages/sage/sandpiles/sandpile.pyc at

4904 for j in range(i):

-> 4905 if p > random():

This is the same behavior as

random_DAG(5, 0)

It appears p=1/2 from the definition of random_DAG is evaluated to 0 (so there are no possible connections), hence p = 0.5 should fix it.

comment:4 Changed 6 years ago by zimmerma

even the following runs forever:

sage: random_DAG(1)

Paul

comment:5 Changed 6 years ago by dsm

  • Status changed from new to needs_review

random_digraph had the same issue (as did, to a lesser degree, one of the positioning dictionaries.) Patch attached.

comment:6 Changed 6 years ago by chapoton

  • Component changed from PLEASE CHANGE to graph theory
  • Keywords random digraph added

comment:7 Changed 6 years ago by chapoton

  • Status changed from needs_review to needs_info

Can you please check what happens, with your patch applied, to the command

sage: random_DAG(5,p=0)

I suspect that the problem is not only the fact that 1/2=0, but also that the program fails when p=0.

comment:8 Changed 6 years ago by chapoton

Indeed, the algorithm is an infinite loop when p=0.

What behaviour should be expected for p=0 ?

Maybe one should add an assumption :

assert p>0 and p<1, "The probability p=%s should satisfy 0<p<1." %p

comment:9 Changed 5 years ago by chapoton

  • Status changed from needs_info to needs_review

comment:10 Changed 5 years ago by chapoton

  • Status changed from needs_review to needs_work

comment:11 Changed 5 years ago by chapoton

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

I have made a modified patch, which checks that p>0.

apply only trac_12181_random_dag-fc.patch

comment:12 Changed 5 years ago by chapoton

  • Milestone changed from sage-5.1 to sage-5.3

comment:13 Changed 5 years ago by chapoton

  • Authors set to dsm, Frédéric Chapoton
  • Milestone changed from sage-5.3 to sage-5.2

comment:14 Changed 5 years ago by chapoton

  • Description modified (diff)

apply only trac_12181_random_dag-fc.2.patch

new patch, with better doc only

comment:15 Changed 5 years ago by dcoudert

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

Hello,

The patch needs further improvements.

1) The test on p should be improved since I can give p=2 without error. For instance,

if p < 0 or p > 1:
   raise ValueError('The parameter p must be in [0..1].')

2) A test is needed for parameter weight_max:

sage: random_DAG(5, .5, -1)
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
...
...
ValueError: empty range for randrange() (1,0, -1)

and

sage: random_DAG(5, .5, .5)
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
...
...
ValueError: non-integer stop for randrange()

3) It should be clearly indicated in the documentation that the function returns a dictionary storing the edges of the DAG.

4) The resulting number of vertices is not n but n+1:

sage: d = DiGraph(random_DAG(5, .5))
sage: d
Digraph on 6 vertices

5) I don't understand why this digraph generator is not part of sage.graphs.digraph_generators.py. The function could have an optional parameter to return a dictionary instead of a digraph if relevant.

comment:16 Changed 5 years ago by chapoton

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

new patch.

I have made all the required changes, except for the last point. It is certainly true that the procedure could be moved, and changed to return a digraph. I would rather let that for another ticket..

apply only trac_12181_random_dag-fc.patch

comment:17 follow-up: Changed 5 years ago by dcoudert

This is much better.

  • The instruction weight_max=ZZ(weight_max) is before the test on weights. Is this what you expect?
    sage: random_DAG(5,.5,1.5)
    ---------------------------------------------------------------------------
    TypeError                                 Traceback (most recent call last)
    ...
    TypeError: Attempt to coerce non-integral RealNumber to Integer
    
  • The output is not only a dictionary but a dictionary of dictionary. You should perhaps add a warning comment since the space requirement for large values of n could be too high. I don't know the usual size of the DAG used in this context.
  • I'm unable to build/find the documentation. Are you able to build it?
  • I agree that moving this function into digraphs_generator could be done as part of another patch. It should in particular have an optional argument allowing to have multiple sinks (and so avoiding the while loop). With current setting, I'm not sure that the average number of arcs is p*n.

comment:18 in reply to: ↑ 17 Changed 5 years ago by chapoton

  • The instruction weight_max=ZZ(weight_max) is before the test on weights. Is this what you expect?
    sage: random_DAG(5,.5,1.5)
    ---------------------------------------------------------------------------
    TypeError                                 Traceback (most recent call last)
    ...
    TypeError: Attempt to coerce non-integral RealNumber to Integer
    

Yes, indeed. Well, this seems to be a reasonable way to ensure that the input is of correct type, as specified in the documentation. The problem is that one should accept both int and Integers as third argument. This is the case with what I have written, which tries to coerce to Integers.

  • The output is not only a dictionary but a dictionary of dictionary. You should perhaps add a warning comment since the space requirement for large values of n could be too high. I don't know the usual size of the DAG used in this context.

Well, a dictionary of dictionaries is a dictionary, isn't it ? And by the way, I have not found any place in the sources of Sage where this procedure is used.

  • I'm unable to build/find the documentation. Are you able to build it?

Sorry, I do not understand this remark. I have only tried the doc in a terminal. Should I try it in the notebook too ? Should I do something else ? Could you pinpoint a specific problem ?

  • I agree that moving this function into digraphs_generator could be done as part of another patch. It should in particular have an optional argument allowing to have multiple sinks (and so avoiding the while loop). With current setting, I'm not sure that the average number of arcs is p*n.

Well, this ticket is here to solve a specific problem, and the rest can be postponed to some other ticket.

comment:19 Changed 5 years ago by chapoton

There is now a mismatch between doc and tests : should we allow p to be equal to 1 or not ?

comment:20 Changed 5 years ago by dcoudert

That's right, you should change the test to

assert 0 < p and p <= 1, "The parameter p must satisfy 0 < p <= 1."

You don't have the change the rest of the code since the random() function returns a value strictly less than 1.

Concerning the documentation. For (almost?) all modules, you can find the functions in the reference manual of sage (http://www.sagemath.org/doc/reference/). Then, when testing a patch, we use the command sage -docbuild reference html to build the reference manual including patch's changes. Same for thematic_tutorials if any.

However, the sandpile model is not included in the reference manual. I have open a new ticket to address this issue (#13342).

So, you have to:

  • change the test on p
  • change the commit message of this patch. It is currently
    #12181 bug in random digraphs with probability zero
    

It should be something like

trac #12181 -- Fix bugs with the input parameters of the random_DAG function

comment:21 Changed 5 years ago by chapoton

Changes done in the new version of the patch

comment:22 Changed 5 years ago by dcoudert

  • Status changed from needs_review to positive_review

For me the patch is OK now.

comment:23 Changed 5 years ago by jdemeyer

  • Authors changed from dsm, Frédéric Chapoton to Douglas McNeil, Frédéric Chapoton
  • Status changed from positive_review to needs_work

I strongly suggest against using assert statements for error checking (bad input should throw ValueError, not AssertionError). Also, add doctests for this bad input.

Changed 5 years ago by chapoton

comment:24 Changed 5 years ago by chapoton

  • Status changed from needs_work to needs_review

New patch, with suggested changes made.

comment:25 Changed 5 years ago by dcoudert

  • Status changed from needs_review to positive_review

For me the patch is fine (install, long tests, etc.).

comment:26 Changed 5 years ago by jdemeyer

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