Graphs: DFS and broken distance-parameter

[jm58660]

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.

CC: @nathanncohen @vbraun

Component: graph theory

Author: Jori Mäntysalo

Branch/Commit: cceb140

Reviewer: David Coudert

Issue created by migration from https://trac.sagemath.org/ticket/19227

[jm58660]

comment:1

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.

[jm58660]

Branch: u/jmantysalo/graphs__dfs_and_broken_distance_parameter

[jm58660]

Commit: 89b7490

[jm58660]

comment:3

I had to delete and modify some examples. Otherwise this just gives deprecation warning.

---

New commits:

89b7490

Deprecation of distance-parameter on depth_first_search().

[nathanncohen]

comment:4

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

[jm58660]

comment:5

Replying to @nathanncohen:

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.

[dcoudert]

comment:6

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.

[jm58660]

comment:7

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.

[nathanncohen]

comment:8

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

[dcoudert]

comment:9

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.

[jm58660]

comment:10

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.

[jm58660]

Author: Jori Mäntysalo

[dcoudert]

comment:11

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]

[jm58660]

comment:12

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.

[nathanncohen]

comment:13

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

[jm58660]

comment:14

Replying to @nathanncohen:

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.)

[sagetrac-git]

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

cceb140

Added better example.

[sagetrac-git]

Changed commit from 89b7490 to cceb140

[dcoudert]

comment:16

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

[jm58660]

comment:17

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.)

[dcoudert]

Reviewer: David Coudert

[dcoudert]

comment:18

For me the patch is good to go.
Thanks,
David.

[vbraun]

Changed branch from u/jmantysalo/graphs__dfs_and_broken_distance_parameter to cceb140