Add optional distance in BFS

[sagetrac-foosterhof]

There is no way to get the edge distance with a custom neighbor function.

breadth_first_search() does not report distance, and shortest_paths() does not give the option to specify a neighbor function.

CC: @sagetrac-Rudi

Component: graph theory

Keywords: breadth first search distance

Author: Florian Oosterhof

Branch/Commit: 0087e5b

Reviewer: Frédéric Chapoton

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

[nathanncohen]

comment:1

I do not understand your problem, but do you know g.distance(by_weight=True) ? A BFS with a distance on the edges is called "Dijkstra's algorithm", and it is implemented in Sage.

Nathann

[sagetrac-foosterhof]

Branch: u/foosterhof/ticket/16470

[sagetrac-foosterhof]

comment:3

I need BFS to report the distance as well, the minimum number of edges/arcs to be traversed for every vertex. The shortest_paths method implements this, but it does not have any option to specify a neighbor function, which is possible in the breadth_first_search method.

My commit is a small modification that does implement this.

---

New commits:

c0dd8ff

Added optional argument (default False) to report distance along with vertex

[sagetrac-foosterhof]

Upstream: Reported upstream. No feedback yet.

[sagetrac-foosterhof]

Commit: c0dd8ff

[fchapoton]

Changed commit from c0dd8ff to 0087e5b

[fchapoton]

Changed branch from u/foosterhof/ticket/16470 to public/16470

[fchapoton]

comment:5

I have made a review commit. I still need to check that the doc builds, otherwise thinks look good to me.

Can you have a look at my changes, and see if you agree with them ? They are mostly typographical.

---

New commits:

94262d9	Merge branch 'u/foosterhof/ticket/16470' of trac.sagemath.org:sage into 16470
0087e5b	trac #16470 reviewer's patch

[fchapoton]

Reviewer: Frédéric Chapoton

[fchapoton]

comment:6

Please put your real name in the author field of the ticket.

[fchapoton]

Changed upstream from Reported upstream. No feedback yet. to none

[fchapoton]

comment:8

Looks good to me. You can set a positive review on my behalf if you agree with my small typographical changes. And please add your real name in the author field.

[sagetrac-Rudi]

comment:9

Thank you for reviewing.

The author of this patch was my student Florian Oosterhof, who worked on this code as a part of his bachelor thesis. I'm not sure if he is still active on the sage trac, so I added his name in the author field on his behalf.

[sagetrac-Rudi]

Author: Florian Oosterhof

[vbraun]

Changed branch from public/16470 to 0087e5b