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: sage-8.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:

Status badges

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 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: 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, bd. The function should return those edges.

Last edited 3 years ago by chaoxu (previous) (diff)

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

Replying to chaoxu:

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:

12d38b8added 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:

5714976added 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:

1862978added 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:

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

b6d17cdupdated:added edges parameter in bfs
Last edited 3 years ago by gh-JhaPrajjwal (previous) (diff)

comment:20 Changed 3 years ago by dcoudert

Some more comments

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

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

efa0c7cupdated 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`` 

Please check.

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:

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

aa45b6dminor 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]})
-            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 git

  • Commit changed from aa45b6d50fe8a0e43490f0b1741214af36ead708 to 3e8d1511e98688f5a458698fc8e20bca91e1107c

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

3e8d151minor fixes: added edges parameter in bfs

comment:32 follow-up: 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:

3e8d151minor fixes: added edges parameter in bfs

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

Replying to gh-JhaPrajjwal:

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

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 dcoudert

  • 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 gh-JhaPrajjwal

  • Authors set to Prajjwal Jha

comment:37 Changed 2 years ago by vbraun

  • Branch changed from u/gh-JhaPrajjwal/18855 to 3e8d1511e98688f5a458698fc8e20bca91e1107c
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.