Opened 6 years ago

Closed 3 years ago

## #18855 closed enhancement (fixed)

Reported by: Owned by: chaoxu minor sage-8.8 graph theory Prajjwal Jha David Coudert N/A 3e8d151 3e8d1511e98688f5a458698fc8e20bca91e1107c

### Description

There is no easy way to get the set of edges in a `breadth_first_search` traversal of the graph. What about an optional parameter so it also return a set of edges of some breadth first search?

Similarly, for the other set of searches too. This is useful if there are information stored on the edges instead of vertices.

### comment:1 Changed 3 years ago by gh-JhaPrajjwal

Can anyone clarify what exactly this enhancement expects? Maybe through an example. I am willing to work on it. Thanks.

### comment:2 follow-up: ↓ 3 Changed 3 years ago by chaoxu

Say the graph has edges ab, ac, cd, bd, bc

```a----b--\
\   |   \
\--c----d
```

If we do a breadth first search from `a`, one of the possible breadth first search trees is

```a----b--\
\       \
\--c    d
```

The edges in the tree are ab, ac, ad. The function should then return the edges ab, ac, cd.

Version 0, edited 3 years ago by chaoxu (next)

### comment:3 in reply to: ↑ 2 Changed 3 years ago by gh-JhaPrajjwal

Say the graph has edges ab, ac, cd, bd, bc

```a----b--\
\   |   \
\--c----d
```

Thank you! I will start working on it.

If we do a breadth first search from `a`, one of the possible breadth first search trees is

```a----b--\
\       \
\--c    d
```

The edges in the tree are ab, ac, bd. The function should return those edges.

### comment:4 Changed 3 years ago by gh-JhaPrajjwal

Hello, I have implemented this, but how do I check my code. I mean how do I build sage again so that my implemented changes can checked by me locally?

### comment:5 Changed 3 years ago by dcoudert

• Milestone changed from sage-6.8 to sage-8.7

Have you read the Sage Developer’s Guide ?

### comment:6 Changed 3 years ago by gh-JhaPrajjwal

Hello, Lets say I use a new parameter get_edges. If I pass get_edges=True, should I only output the edges through the generators or should I output the edges as well as vertices. If we go for the latter option, can you please guide me on how to use 'yield' to output both of them.

### comment:7 Changed 3 years ago by dcoudert

I suggest to return only edges.

To name the parameter may be simple `edges`?

### comment:8 Changed 3 years ago by gh-JhaPrajjwal

• Branch set to u/gh-JhaPrajjwal/18855

### comment:9 Changed 3 years ago by git

• Commit set to 12d38b826f05e21770c4c628e553d639d9956729

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

 ​12d38b8 `added edges parameter in breadth_first_search`

### comment:10 Changed 3 years ago by gh-JhaPrajjwal

• Status changed from new to needs_review

### comment:11 Changed 3 years ago by dcoudert

There is a merge conflict between your branch and the last beta version. To see that, click on the branch name on top of this page.

### comment:12 Changed 3 years ago by git

• Commit changed from 12d38b826f05e21770c4c628e553d639d9956729 to 57149764548eca06df498576e7721e5560710924

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

 ​5714976 `added edges parameter in breadth_first_search`

### comment:13 Changed 3 years ago by gh-JhaPrajjwal

I am not able to find the merge conflict. I am trying to rebase with trac master but the branch is already up-to date. Can you please tell me which branch I need to rebase with?

### comment:14 Changed 3 years ago by dcoudert

You should rebase on the develop branch. It is the most recent branch.

### comment:15 Changed 3 years ago by git

• Commit changed from 57149764548eca06df498576e7721e5560710924 to 1862978a6a262c25957813fbc84921a68bb2dcc6

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

 ​1862978 `added edges parameter in breadth_first_search`

### comment:16 Changed 3 years ago by gh-JhaPrajjwal

Please check and let me know if any more changes needs to be done? Also if the gets merged shall I update the documentation?

### comment:17 Changed 3 years ago by dcoudert

Why are you first building a list of edges and later iterate over that list to yield edges ?

### comment:18 Changed 3 years ago by git

• Commit changed from 1862978a6a262c25957813fbc84921a68bb2dcc6 to b6d17cd2958c9fa399d988d5325c098c42b01b1a

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

 ​b6d17cd `updated:added edges parameter in bfs`

### comment:19 Changed 3 years ago by gh-JhaPrajjwal

Initially I was trying to output both edges and vertices so I was storing it in a list for some reason. But I forgot to change it when I switched to returning only the edges. Made the changes. Please check. Also, if it is correct shall I make a similar ticket for dfs?

New commits:

 ​b6d17cd `updated:added edges parameter in bfs`
Last edited 3 years ago by gh-JhaPrajjwal (previous) (diff)

### comment:20 Changed 3 years ago by dcoudert

• you must document parameter edges
• you must document the fact that some combinations of parameters are not possible like `edges=True` and `report_distance=True`
• remove
```-            edges_list = []
-
```

Have you tested your changes with more graphs / digraphs ?

### comment:21 Changed 3 years ago by git

• Commit changed from b6d17cd2958c9fa399d988d5325c098c42b01b1a to 7ef7e055ee265d76f0dfdba0c1701ad76c9fd962

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

 ​7ef7e05 `updated: added edges parameter in bfs`

### comment:22 Changed 3 years ago by gh-JhaPrajjwal

Yes I have checked my changes for many graphs including digraphs. Please check the changes.

### comment:23 Changed 3 years ago by dcoudert

General remarks: documentation and comments must be formatted in 80 columns mode. Some text editors can be configured to ease this

• I propose an improved version of the text
```-        - ``edges`` -- boolean (default ``False``); if ``True``,
-          returns edges ``(start, end)`` in the breadth_first_search tree instead of vertices, where
-          the direction of edge is from ``start`` node to ``end`` node.
-          If ``False`` only the vertices are reported.
-          Note: ``edges`` and  ``report_distance`` cannot be ``True`` simultaneously.
+        - ``edges`` -- boolean (default ``False``); whether to return the edges
+          of the BFS tree in the order of visit or the vertices (default).
+          Edges are directed in root to leaf orientation of the tree.
+
+          Note that parameters ``edges`` and  ``report_distance`` cannot be ``True``
+          simultaneously.
```
```-        You can get edges in the breadth_first_search tree instead of the vertices using the
-        ``edges`` parameter::
+        You can get edges of the BFS tree instead of the vertices using the
+        ``edges`` parameter::
```
• error message don't start with a capital letter, and don't end with a `.`, unless the message has several sentences.
```-        if (report_distance and edges):
-            raise Exception("The parameters edges and report_distance cannot be True simultaneously.")
+        if report_distance and edges:
+            raise Exception("parameters edges and report_distance cannot be True simultaneously")
```

### comment:24 Changed 3 years ago by git

• Commit changed from 7ef7e055ee265d76f0dfdba0c1701ad76c9fd962 to efa0c7cb91000310ff54587c332ca93362c2001e

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

 ​efa0c7c `updated documentation: added edges parameter in bfs`

### comment:25 Changed 3 years ago by embray

• Milestone changed from sage-8.7 to sage-8.8

Ticket retargeted after milestone closed (if you don't believe this ticket is appropriate for the Sage 8.8 release please retarget manually)

### comment:26 Changed 3 years ago by dcoudert

There are remaining comments which are not formatted in 80 columns mode, for instance

```+          Note that parameters ``edges`` and  ``report_distance`` cannot be ``True``
```

### comment:27 Changed 3 years ago by git

• Commit changed from efa0c7cb91000310ff54587c332ca93362c2001e to a7147555111ce6eb9512d8b778be71e3cea8c1d5

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

 ​a714755 `updated documentation: added edges parameter in bfs`

### comment:28 Changed 3 years ago by dcoudert

I forgot to review the last version.

• We usually use `ValueError` and not `Exception` and I think it is more appropriate here
• in the `TESTS::` block, can you add a test showing that the error is raised in such case
• at the end of the method, you added 2 extra empty lines before `def depth_first_search`. There is no need for that.

### comment:29 Changed 3 years ago by git

• Commit changed from a7147555111ce6eb9512d8b778be71e3cea8c1d5 to aa45b6d50fe8a0e43490f0b1741214af36ead708

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

 ​aa45b6d `minor fixes: added edges parameter in bfs`

### comment:30 Changed 3 years ago by dcoudert

Hello,

for doctests raising errors, the correct way to write it is:

```-            sage: G = Graph({1:[2,3],2:[4,5],3:[6,7]})
-            ValueError: parameters edges and report_distance cannot be True simultaneously
+            sage: G = Graph([(0, 1)])
+            Traceback (most recent call last):
+            ...
+            ValueError: parameters edges and report_distance cannot be True simultaneously
```

Have you checked that your code passes doctests before pushing the last commit ? For instance, you can do `sage -btp --long src/sage/graphs/generic_graph.py` to tests `generic_graph.py` (including doctests marked as long), or `sage -btp --long src/sage/graphs/` to test the full graph module.

### comment:31 Changed 3 years ago by git

• Commit changed from aa45b6d50fe8a0e43490f0b1741214af36ead708 to 3e8d1511e98688f5a458698fc8e20bca91e1107c

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

 ​3e8d151 `minor fixes: added edges parameter in bfs`

### comment:32 follow-up: ↓ 33 Changed 3 years ago by gh-JhaPrajjwal

Hello,

```./sage -t src/sage/graphs/generic_graph.py
```

I used this command and received 4 failed doctests but none of them were related to bfs.

New commits:

 ​3e8d151 `minor fixes: added edges parameter in bfs`

### comment:33 in reply to: ↑ 32 ; follow-up: ↓ 34 Changed 3 years ago by dcoudert

I used this command and received 4 failed doctests but none of them were related to bfs.

Which one ? if you are working with Python2, you should not have any failing doctests except for those related to what is modified in this ticket.

### comment:34 in reply to: ↑ 33 Changed 3 years ago by gh-JhaPrajjwal

Which one ? if you are working with Python2, you should not have any failing doctests except for those related to what is modified in this ticket.

I just checked again, it was actually a single error which is related to

```OperationalError: unable to open database file
```

Also, no doctests failed related to the modified ticket.

### comment:35 Changed 3 years ago by dcoudert

• Reviewers set to David Coudert
• Status changed from needs_review to positive_review

LGTM.