Opened 5 years ago
Closed 5 years ago
#19223 closed defect (fixed)
Graphs: missing error check for depth_first_search(..., distance=0)
Reported by:  jmantysalo  Owned by:  

Priority:  minor  Milestone:  sage6.10 
Component:  graph theory  Keywords:  
Cc:  ncohen  Merged in:  
Authors:  Jori Mäntysalo  Reviewers:  Nathann Cohen 
Report Upstream:  N/A  Work issues:  
Branch:  f90f515 (Commits)  Commit:  f90f5158b4ea9357da42e3d0e96448650178bc6d 
Dependencies:  Stopgaps: 
Description
G = Graph({1:[2]}) list(G.depth_first_search('junk', distance=0))
outputs ['junk']
, but it should raise an exception. With distance=1
it works. Same happens with breadth_first_search()
.
Also distance
is not checked and G.depth_first_search(1, distance='junk')
works like distance=None
.
Change History (16)
comment:1 Changed 5 years ago by
 Branch set to u/jmantysalo/graphs__missing_error_check_for_depth_first_search______distance_0_
comment:2 Changed 5 years ago by
 Cc ncohen added
 Commit set to ec0e5b3167db96d936ed1f70bb8dbbcb19201895
comment:3 Changed 5 years ago by
Hello Jori,
What you did is not exactly wrong, but we should really find something better than adding 30 lines of code to deal with a rather stupid cornercase. Though I admit that I do not see one at the moment.
Technically (though that is not the biggest problem here) try to only wrap the smallest amount of line in a try/except. When you write too much in a try/except, you run the risk of catching exceptions raised legitimately by other functions.
Nathann
comment:4 followup: ↓ 6 Changed 5 years ago by
'Another way' may be to do this kind of replacement:
queue=[(v,0) for v in reversed(start)] +queue=[(v,0) for v in reversed(start) if v in self]
The behaviour is a bit different, but well... What do you think?
Nathann
comment:5 Changed 5 years ago by
Fix might collide with #19227, so let's hold this one after much more important bug is corrected.
comment:6 in reply to: ↑ 4 ; followup: ↓ 7 Changed 5 years ago by
Replying to ncohen:
'Another way' may be to do this kind of replacement:
queue=[(v,0) for v in reversed(start)] +queue=[(v,0) for v in reversed(start) if v in self]The behaviour is a bit different, but well... What do you think?
For every case, also to those with distance != 0
? Sounds kind of dangerous.
we should really find something better than adding 30 lines of code to deal with a rather stupid cornercase
Simple. We should have global internal functions for this. Like _check_integer_all()
, _check_integer_nonnegative()
and _check_integer_positive()
. Then also error messages would be consistent.
A topic for sagedevel?
comment:7 in reply to: ↑ 6 Changed 5 years ago by
Simple. We should have global internal functions for this. Like
_check_integer_all()
,_check_integer_nonnegative()
and_check_integer_positive()
. Then also error messages would be consistent.A topic for sagedevel?
Yep. A module somewhere with (fast) functions to check the type of a couple of things would be cool indeed.
Nathann
comment:8 Changed 5 years ago by
 Commit changed from ec0e5b3167db96d936ed1f70bb8dbbcb19201895 to f2df1bb599f96726b5247cd454f3d800dd99d480
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
f2df1bb  Added a check for bfs parameters.

comment:9 Changed 5 years ago by
 Status changed from new to needs_review
As #19227 deprecated distance
on dfs, this only changes bfs. Now there is one more point to detect errors.
comment:10 followup: ↓ 12 Changed 5 years ago by
Add a 'a' before 'nonnegative integer' and it can go.
comment:11 Changed 5 years ago by
 Commit changed from f2df1bb599f96726b5247cd454f3d800dd99d480 to f90f5158b4ea9357da42e3d0e96448650178bc6d
Branch pushed to git repo; I updated commit sha1. New commits:
f90f515  Typo. Added 'a'.

comment:12 in reply to: ↑ 10 Changed 5 years ago by
 Status changed from needs_review to positive_review
Replying to ncohen:
Add a 'a' before 'nonnegative integer' and it can go.
This corrected, tests passed > positive review.
Thanks!
comment:14 Changed 5 years ago by
 Reviewers set to Nathann Cohen
 Status changed from needs_work to positive_review
comment:15 Changed 5 years ago by
 Milestone changed from sage6.9 to sage6.10
comment:16 Changed 5 years ago by
 Branch changed from u/jmantysalo/graphs__missing_error_check_for_depth_first_search______distance_0_ to f90f5158b4ea9357da42e3d0e96448650178bc6d
 Resolution set to fixed
 Status changed from positive_review to closed
Nathann: Can you check
c_graph.pyx
just to make sure I did nothing stupid? I added a check to surface level, and so I had to change one test in the deeper level.New commits:
Added check for arguments in [depthbreadth]_first_search().
Forget that startparameter can be list.