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: sage-6.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 jmantysalo

  • Branch set to u/jmantysalo/graphs__missing_error_check_for_depth_first_search______distance_0_

comment:2 Changed 5 years ago by jmantysalo

  • Authors set to Jori Mäntysalo
  • Cc ncohen added
  • Commit set to ec0e5b3167db96d936ed1f70bb8dbbcb19201895

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:

354f061Added check for arguments in [depth|breadth]_first_search().
ec0e5b3Forget that start-parameter can be list.

comment:3 Changed 5 years ago by ncohen

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 corner-case. 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 follow-up: Changed 5 years ago by 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?

Nathann

comment:5 Changed 5 years ago by jmantysalo

Fix might collide with #19227, so let's hold this one after much more important bug is corrected.

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

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 corner-case

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 sage-devel?

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

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 sage-devel?

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 git

  • Commit changed from ec0e5b3167db96d936ed1f70bb8dbbcb19201895 to f2df1bb599f96726b5247cd454f3d800dd99d480

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

f2df1bbAdded a check for bfs parameters.

comment:9 Changed 5 years ago by jmantysalo

  • 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 follow-up: Changed 5 years ago by ncohen

Add a 'a' before 'nonnegative integer' and it can go.

comment:11 Changed 5 years ago by git

  • Commit changed from f2df1bb599f96726b5247cd454f3d800dd99d480 to f90f5158b4ea9357da42e3d0e96448650178bc6d

Branch pushed to git repo; I updated commit sha1. New commits:

f90f515Typo. Added 'a'.

comment:12 in reply to: ↑ 10 Changed 5 years ago by jmantysalo

  • 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:13 Changed 5 years ago by vbraun

  • Status changed from positive_review to needs_work

Reviewer name

comment:14 Changed 5 years ago by ncohen

  • Reviewers set to Nathann Cohen
  • Status changed from needs_work to positive_review

comment:15 Changed 5 years ago by jmantysalo

  • Milestone changed from sage-6.9 to sage-6.10

comment:16 Changed 5 years ago by vbraun

  • 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
Note: See TracTickets for help on using tickets.