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 )
Try:
random_DAG(5)
it will run forever!
apply only trac_12181_random_dag-fc.patch
Attachments (1)
Change History (27)
comment:1 in reply to: ↑ description Changed 6 years ago by
- Description modified (diff)
comment:2 in reply to: ↑ description Changed 6 years ago by
- 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
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
even the following runs forever:
sage: random_DAG(1)
Paul
comment:5 Changed 6 years ago by
- 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 5 years ago by
- Component changed from PLEASE CHANGE to graph theory
- Keywords random digraph added
comment:7 Changed 5 years ago by
- 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 5 years ago by
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
- Status changed from needs_info to needs_review
comment:10 Changed 5 years ago by
- Status changed from needs_review to needs_work
comment:11 Changed 5 years ago by
- 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
- Milestone changed from sage-5.1 to sage-5.3
comment:13 Changed 5 years ago by
- Milestone changed from sage-5.3 to sage-5.2
comment:14 Changed 5 years ago by
- 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
- 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
- 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: ↓ 18 Changed 5 years ago by
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
- 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
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
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
Changes done in the new version of the patch
comment:22 Changed 5 years ago by
- Status changed from needs_review to positive_review
For me the patch is OK now.
comment:23 Changed 5 years ago by
- 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
comment:24 Changed 5 years ago by
- Status changed from needs_work to needs_review
New patch, with suggested changes made.
comment:25 Changed 5 years ago by
- 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
- Merged in set to sage-5.3.beta2
- Resolution set to fixed
- Status changed from positive_review to closed
Replying to mderickx: