Opened 4 years ago

Closed 4 years ago

#19227 closed defect (fixed)

Graphs: DFS and broken distance-parameter

Reported by: jmantysalo Owned by:
Priority: major Milestone: sage-6.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 jmantysalo)

This bug is visible at least on normal 64-bit Linux machine running self-compiled Sage. This is architechture-dependent 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 4 years ago by jmantysalo

Accidentally I tested what happens if I remove distance from breadth_first_search. Nothing: all doctests, except the function's own, were successfull. Hence breadth() in lattices.py is first one to use the parameter.

It also seems that distance at depth_first_search() is unused. I am running doctests, but plain grep shows no matches. Hence I guess we can just deprecate this.

comment:2 Changed 4 years ago by jmantysalo

  • Branch set to u/jmantysalo/graphs__dfs_and_broken_distance_parameter

comment:3 Changed 4 years ago by jmantysalo

  • 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:

89b7490Deprecation of distance-parameter on depth_first_search().

comment:4 follow-up: Changed 4 years ago by ncohen

Err.. Given that it is is broken, that the output is architecture-dependent, 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 4 years ago by jmantysalo

  • Cc vbraun added

Replying to ncohen:

Err.. Given that it is is broken, that the output is architecture-dependent, 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 follow-ups: Changed 4 years ago by dcoudert

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 4 years ago by jmantysalo

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 machine-dependent.

Last edited 4 years ago by jmantysalo (previous) (diff)

comment:8 in reply to: ↑ 6 Changed 4 years ago by ncohen

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 architecture-dependent 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 4 years ago by dcoudert

Now I agree that not only we don't have a proper definition, but also that the result is machine-dependent.

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 machine-independent) 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 4 years ago by jmantysalo

  • Authors set to Jori Mäntysalo
  • 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 cross-review our codes.

comment:11 follow-up: Changed 4 years ago by dcoudert

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 ; follow-up: Changed 4 years ago by jmantysalo

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

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 4 years ago by jmantysalo

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 4 years ago by git

  • Commit changed from 89b7490bec7e28f1c63bb81603eeab69fefb4e65 to cceb14033885476d6f8d4a48692108d01962c839

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

cceb140Added better example.

comment:16 follow-up: Changed 4 years ago by dcoudert

Don't forget to set the ticket to needs review when ready. David.

comment:17 in reply to: ↑ 16 Changed 4 years ago by jmantysalo

  • 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 4 years ago by dcoudert

  • 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 4 years ago by vbraun

  • Branch changed from u/jmantysalo/graphs__dfs_and_broken_distance_parameter to cceb14033885476d6f8d4a48692108d01962c839
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.