Opened 5 years ago
Closed 5 years ago
#19227 closed defect (fixed)
Graphs: DFS and broken distanceparameter
Reported by:  jmantysalo  Owned by:  

Priority:  major  Milestone:  sage6.9 
Component:  graph theory  Keywords:  
Cc:  ncohen, vbraun  Merged in:  
Authors:  Jori Mäntysalo  Reviewers:  David Coudert 
Report Upstream:  N/A  Work issues:  
Branch:  cceb140 (Commits)  Commit:  cceb14033885476d6f8d4a48692108d01962c839 
Dependencies:  Stopgaps: 
Description (last modified by )
This bug is visible at least on normal 64bit Linux machine running selfcompiled Sage. This is architechturedependent if you have for example both integers and strings as vertices.
G = DiGraph({1:[2,10],2:[3],3:[4],4:[5],5:[6],10:[4]}) list(G.depth_first_search(1, distance=3))
This could output also 5
as it is three jumps from 1: 1>10>4>5
. It is not outputted because 4
is already marked as seen vertex for 1>2>3>4
.
Change History (19)
comment:1 Changed 5 years ago by
comment:2 Changed 5 years ago by
 Branch set to u/jmantysalo/graphs__dfs_and_broken_distance_parameter
comment:3 Changed 5 years ago by
 Commit set to 89b7490bec7e28f1c63bb81603eeab69fefb4e65
 Description modified (diff)
 Status changed from new to needs_review
I had to delete and modify some examples. Otherwise this just gives deprecation warning.
New commits:
89b7490  Deprecation of distanceparameter on depth_first_search().

comment:4 followup: ↓ 5 Changed 5 years ago by
Err.. Given that it is is broken, that the output is architecturedependent, and that people may have a misleading idea about what it does, why don't we just remove it? Volker repeats often enough that "we don't need to deprecate bugs". I only hope that in this case we agree that it is a bug (which isn't always the case when Volker uses that argument).
Nathann
comment:5 in reply to: ↑ 4 Changed 5 years ago by
 Cc vbraun added
Replying to ncohen:
Err.. Given that it is is broken, that the output is architecturedependent, and that people may have a misleading idea about what it does, why don't we just remove it? Volker repeats often enough that "we don't need to deprecate bugs". I only hope that in this case we agree that it is a bug (which isn't always the case when Volker uses that argument).
Vbraun added to CC.
I am not exactly sure what counts as a bug and what not. See #18944.
I think that somebody might have code that uses this, maybe even working code (i.e. using DFS with distance
only for trees). Can we give deprecation warning AND raise and exception? Then the user would at least know what has happened and why the code does not work any more.
Volker, #19197 contains some discussion about this; that is where Nathann saw this bug.
comment:6 followups: ↓ 7 ↓ 8 Changed 5 years ago by
Hello,
the behavior of the G.depth_first_search(1, distance=3)
is not machine dependent but it depends on the labels of the vertices which define an ordering between vertices. So if you relabel 10>1
and 1>10
in your example, you will get different result.
I don't see a bug here, I see a definition problem: what are we expecting?
If we are not able to provide a clear definition of the expected behavior of the distance
parameter, we should not have it in DFS.
David.
comment:7 in reply to: ↑ 6 Changed 5 years ago by
Replying to dcoudert:
the behavior of the
G.depth_first_search(1, distance=3)
is not machine dependent but it depends on the labels of the vertices which define an ordering between vertices.
So if you have labels 42
and 'hello!'
, it is machinedependent.
comment:8 in reply to: ↑ 6 Changed 5 years ago by
I don't see a bug here, I see a definition problem: what are we expecting? If we are not able to provide a clear definition of the expected behavior of the
distance
parameter, we should not have it in DFS.
I agree with that, the fact that it is architecturedependent is merely a way to show that we will never find a clear explanation of what can be expected.
The other reason is that this being named 'distance' is very misleading.
Nathann
comment:9 Changed 5 years ago by
Now I agree that not only we don't have a proper definition, but also that the result is machinedependent.
on my mac:
sage: 42>'hello!' True
on a linux desktop I have
sage: 42>'hello!' False
Could you:
 add your name as author
 change in the ticket description,
This should output
>This could output
.  To show that the DFS can go backward, you could provide a simpler (and machineindependent) example, instead of this of
sorted([d_in.next(), d_in.next(), d_in.next()])
:sage: D = digraphs.Path(10) sage: list(D.depth_first_search(5, neighbors=D.neighbors_in)) [5, 4, 3, 2, 1, 0] sage: list(D.depth_first_search(5, neighbors=D.neighbors_out)) [5, 6, 7, 8, 9]
Thanks. David.
comment:10 Changed 5 years ago by
 Description modified (diff)
 Status changed from needs_review to needs_work
I can make a better example later, when I am on faster computer.
But is plain path a good example? It won't show any difference between depth_first_search()
and breadth_first_search()
.
Of course you can also do this; we can crossreview our codes.
comment:11 followup: ↓ 12 Changed 5 years ago by
Could this be ok?
sage: D = digraphs.Path(10) sage: D.add_path([22,23,24,5]) sage: D.add_path([5,33,34,35]) sage: list(D.depth_first_search(5, neighbors=D.neighbors_in)) [5, 4, 3, 2, 1, 0, 24, 23, 22] sage: list(D.breadth_first_search(5, neighbors=D.neighbors_in)) [5, 24, 4, 23, 3, 22, 2, 1, 0] sage: list(D.depth_first_search(5, neighbors=D.neighbors_out)) [5, 6, 7, 8, 9, 33, 34, 35] sage: list(D.breadth_first_search(5, neighbors=D.neighbors_out)) [5, 33, 6, 34, 7, 35, 8, 9]
comment:12 in reply to: ↑ 11 ; followup: ↓ 13 Changed 5 years ago by
Replying to dcoudert:
Could this be ok?
Seems good example to me. Nathann is a specialist in graphs, so maybe I'll also wait to see if he sees something wrong with that.
comment:13 in reply to: ↑ 12 ; followup: ↓ 14 Changed 5 years ago by
Seems good example to me. Nathann is a specialist in graphs, so maybe I'll also wait to see if he sees something wrong with that.
Err. Well. David is the head of the team in which I work these days. I have not followed your recent exchanges on the possible outputs of the faulty command, but if you need the reassurance of a graph specialist you needn't look further.
Nathann
comment:14 in reply to: ↑ 13 Changed 5 years ago by
Replying to ncohen:
Err. Well. David is the head of the team in which I work these days. I have not followed your recent exchanges on the possible outputs of the faulty command, but if you need the reassurance of a graph specialist you needn't look further.
OK. Let's say "specialist in graph theory with SageMath" :=)
. Anyways, I will add that example. (Assuming I got this compiled... had to say make distclean
, something has gone wrong when make
was interrupted.)
comment:15 Changed 5 years ago by
 Commit changed from 89b7490bec7e28f1c63bb81603eeab69fefb4e65 to cceb14033885476d6f8d4a48692108d01962c839
Branch pushed to git repo; I updated commit sha1. New commits:
cceb140  Added better example.

comment:16 followup: ↓ 17 Changed 5 years ago by
Don't forget to set the ticket to needs review
when ready.
David.
comment:17 in reply to: ↑ 16 Changed 5 years ago by
 Status changed from needs_work to needs_review
Replying to dcoudert:
Don't forget to set the ticket to
needs review
when ready.
Now it is, compiles and tests passed and html manual builds. (Got ImportError
from Config
?? Recompiled everything.)
comment:18 Changed 5 years ago by
 Reviewers set to David Coudert
 Status changed from needs_review to positive_review
For me the patch is good to go. Thanks, David.
comment:19 Changed 5 years ago by
 Branch changed from u/jmantysalo/graphs__dfs_and_broken_distance_parameter to cceb14033885476d6f8d4a48692108d01962c839
 Resolution set to fixed
 Status changed from positive_review to closed
Accidentally I tested what happens if I remove
distance
frombreadth_first_search
. Nothing: all doctests, except the function's own, were successfull. Hencebreadth()
inlattices.py
is first one to use the parameter.It also seems that
distance
atdepth_first_search()
is unused. I am running doctests, but plain grep shows no matches. Hence I guess we can just deprecate this.