Opened 6 years ago
Closed 2 years ago
#18855 closed enhancement (fixed)
breadth_first_search return edges
Reported by:  chaoxu  Owned by:  

Priority:  minor  Milestone:  sage8.8 
Component:  graph theory  Keywords:  
Cc:  Merged in:  
Authors:  Prajjwal Jha  Reviewers:  David Coudert 
Report Upstream:  N/A  Work issues:  
Branch:  3e8d151 (Commits, GitHub, GitLab)  Commit:  3e8d1511e98688f5a458698fc8e20bca91e1107c 
Dependencies:  Stopgaps: 
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.
Change History (37)
comment:1 Changed 3 years ago by
comment:2 followup: ↓ 3 Changed 3 years ago by
Say the graph has edges ab, ac, cd, bd, bc
ab\ \  \ \cd
If we do a breadth first search from a
, one of the possible breadth first search trees is
ab\ \ \ \c d
The edges in the tree are ab, ac, bd. The function should return those edges.
comment:3 in reply to: ↑ 2 Changed 3 years ago by
Replying to chaoxu:
Say the graph has edges ab, ac, cd, bd, bc
ab\ \  \ \cd
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 isab\ \ \ \c dThe edges in the tree are ab, ac, bd. The function should return those edges.
comment:4 Changed 3 years ago by
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
 Milestone changed from sage6.8 to sage8.7
Have you read the Sage Developer’s Guide ?
comment:6 Changed 3 years ago by
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
I suggest to return only edges.
To name the parameter may be simple edges
?
comment:8 Changed 3 years ago by
 Branch set to u/ghJhaPrajjwal/18855
comment:9 Changed 3 years ago by
 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
 Status changed from new to needs_review
comment:11 Changed 3 years ago by
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
 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
I am not able to find the merge conflict. I am trying to rebase with trac master but the branch is already upto date. Can you please tell me which branch I need to rebase with?
comment:14 Changed 3 years ago by
You should rebase on the develop branch. It is the most recent branch.
comment:15 Changed 3 years ago by
 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
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
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
 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
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

comment:20 Changed 3 years ago by
Some more comments
 you must document parameter edges
 you must document the fact that some combinations of parameters are not possible like
edges=True
andreport_distance=True
 some spaces are needed for the quality of the code. See http://doc.sagemath.org/html/en/developer/coding_basics.html#pythoncodestyle for more details
 report_distance=False,edges=False): + report_distance=False, edges=False):
 remove
 edges_list = [] 
Have you tested your changes with more graphs / digraphs ?
comment:21 Changed 3 years ago by
 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
Yes I have checked my changes for many graphs including digraphs. Please check the changes.
comment:23 Changed 3 years ago by
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
 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
 Milestone changed from sage8.7 to sage8.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
There are remaining comments which are not formatted in 80 columns mode, for instance
+ Note that parameters ``edges`` and ``report_distance`` cannot be ``True``
Please check.
comment:27 Changed 3 years ago by
 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
I forgot to review the last version.
 We usually use
ValueError
and notException
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
 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
Hello,
for doctests raising errors, the correct way to write it is:
 sage: G = Graph({1:[2,3],2:[4,5],3:[6,7]})  sage: list(G.breadth_first_search(1, report_distance=True, edges=True))  ValueError: parameters edges and report_distance cannot be True simultaneously + sage: G = Graph([(0, 1)]) + sage: list(G.breadth_first_search(1, report_distance=True, edges=True)) + 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
 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 followup: ↓ 33 Changed 3 years ago by
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 ; followup: ↓ 34 Changed 3 years ago by
Replying to ghJhaPrajjwal:
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
Replying to dcoudert:
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
I have not downloaded any database (if it needs to be downloaded explicitly).
Also, no doctests failed related to the modified ticket.
comment:35 Changed 2 years ago by
 Reviewers set to David Coudert
 Status changed from needs_review to positive_review
LGTM.
Please add your full name in the "Authors" field.
comment:36 Changed 2 years ago by
comment:37 Changed 2 years ago by
 Branch changed from u/ghJhaPrajjwal/18855 to 3e8d1511e98688f5a458698fc8e20bca91e1107c
 Resolution set to fixed
 Status changed from positive_review to closed
Can anyone clarify what exactly this enhancement expects? Maybe through an example. I am willing to work on it. Thanks.