Opened 3 years ago

Closed 20 months ago

#27636 closed enhancement (fixed)

Return edges from Depth_First_Search

Reported by: gh-JhaPrajjwal Owned by:
Priority: minor Milestone: sage-9.1
Component: graph theory Keywords:
Cc: Merged in:
Authors: Sagnik Dey Reviewers: David Coudert
Report Upstream: N/A Work issues:
Branch: f480fd0 (Commits, GitHub, GitLab) Commit: f480fd0c0426ef9dbdb02f128ff702c260763880
Dependencies: Stopgaps:

Status badges

Description

There is no current way to get edges from the depth_first_search traversal of the graph.
Add an extra parameter 'get_edges' to return the edges from the depth_first_search.

Change History (37)

comment:1 follow-up: Changed 2 years ago by gh-Rithesh17

Can anyone tell me the importance of this requirement?

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

Replying to gh-Rithesh17:

Can anyone tell me the importance of this requirement?

Hello, I have already worked on this for BFS(https://trac.sagemath.org/ticket/18855#comment:1) and that ticket is now closed. So, it would be good to implement a similar thing for DFS.

Last edited 2 years ago by gh-JhaPrajjwal (previous) (diff)

comment:3 Changed 2 years ago by embray

  • Milestone sage-8.8 deleted

As the Sage-8.8 release milestone is pending, we should delete the sage-8.8 milestone for tickets that are not actively being worked on or that still require significant work to move forward. If you feel that this ticket should be included in the next Sage release at the soonest please set its milestone to the next release milestone (sage-8.9).

comment:4 Changed 21 months ago by gh-akshat1136

I am willing to work on this ticket.

I think, one way to implement this is to use a list of visited nodes(in the same sequence in which they were visited) to get the connecting node for the edge. Or is there a better way?

Should I do git trac checkout 27636 to start?

comment:5 Changed 21 months ago by gh-akshat1136

  • Status changed from new to needs_info

comment:6 Changed 21 months ago by dcoudert

Look at http://doc.sagemath.org/html/en/developer/manual_git.html#pushing-your-changes-to-a-ticket for more details on how to start creating branches.

comment:7 Changed 21 months ago by gh-akshat1136

  • Branch set to u/gh-akshat1136/return_edges_from_depth_first_search

comment:8 Changed 21 months ago by gh-akshat1136

  • Commit set to 1a4a3210e34d59eb75478510d45d33f9efdc0a91
  • Status changed from needs_info to needs_review

I have made the required changes to get edges as output and committed it. And added the test as well.

comment:9 follow-up: Changed 21 months ago by dcoudert

  • Status changed from needs_review to needs_work

The method you propose is not good: instead of a linear time algorithm, you propose a quadratic time algorithm.

I suggest to distinguish 2 cases, the aloe one that reports vertices, and the new one to report edges. Then, for edges, instead of adding vertices to the queue, you add edges (with root to leaf orientation). Then, you yield an edge after a pop and add out edges to the queue.

- (default ``False``)
+ (default: ``False``)

comment:10 Changed 20 months ago by gh-SagnikDey92

  • Branch changed from u/gh-akshat1136/return_edges_from_depth_first_search to u/gh-SagnikDey92/return_edges_from_depth_first_search

comment:11 in reply to: ↑ 9 Changed 20 months ago by gh-SagnikDey92

  • Commit changed from 1a4a3210e34d59eb75478510d45d33f9efdc0a91 to 2b7f6e1016d10d980195147b0a7134820dc68153

Replying to dcoudert:

Then, for edges, instead of adding vertices to the queue, you add edges (with root to leaf orientation). Then, you yield an edge after a pop and add out edges to the queue.

Implemented this. Please review.


New commits:

a179f9aadded edges parameter in dfs
5284000Merge branch 'u/gh-akshat1136/return_edges_from_depth_first_search' of git://trac.sagemath.org/sage into t/27636/return_edges_from_depth_first_search
2b7f6e1Made the DFS edge returning routine linear from quadratic by separating the cases where vertices and edges are returned

comment:12 follow-up: Changed 20 months ago by dcoudert

  • a : is missing
    -        - ``edges`` -- boolean (default ``False``); whether to return the edges
    +        - ``edges`` -- boolean (default: ``False``); whether to return the edges
    
  • excessive indentation.
    +                        if distance is None or d < distance:
    +                                for w in neighbors(v):
    +                                    if w not in seen:
    +                                        queue.append((w, d + 1))
    
  • an error to fix
    sage: G = digraphs.Circuit(10)
    sage: list(G.depth_first_search([0], edges=True))
    [(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 7), (7, 8), (8, 9)]
    sage: list(G.depth_first_search([0, 5], edges=True))
    ---------------------------------------------------------------------------
    ValueError                                Traceback (most recent call last)
    <ipython-input-3-7e9a0ee8fcbe> in <module>()
    ----> 1 list(G.depth_first_search([Integer(0), Integer(5)], edges=True))
    
    /Users/dcoudert/sage/local/lib/python3.7/site-packages/sage/graphs/generic_graph.py in depth_first_search(self, start, ignore_direction, distance, neighbors, edges)
      17812                 queue.append((None, v, d))
      17813                 while queue:
    > 17814                     v, w, d = queue.pop()
      17815                     if w not in seen:
      17816                         if v is not None:
    
    ValueError: not enough values to unpack (expected 3, got 2)
    
  • and also
    sage: list(G.depth_first_search([], edges=False))
    []
    sage: list(G.depth_first_search([], edges=True))
    ---------------------------------------------------------------------------
    IndexError                                Traceback (most recent call last)
    <ipython-input-5-bd352d9e6783> in <module>()
    ----> 1 list(G.depth_first_search([], edges=True))
    
    /Users/dcoudert/sage/local/lib/python3.7/site-packages/sage/graphs/generic_graph.py in depth_first_search(self, start, ignore_direction, distance, neighbors, edges)
      17809 
      17810             else:
    > 17811                 v, d = queue.pop()
      17812                 queue.append((None, v, d))
      17813                 while queue:
    
    IndexError: pop from empty list
    

comment:13 Changed 20 months ago by git

  • Commit changed from 2b7f6e1016d10d980195147b0a7134820dc68153 to 8aa0a709f8bc354e661d8bd65b1f0b645814d458

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

8aa0a70Made minor changes to documentation for uniformity. Fixed errors related to DFS with number of starting vertices not equal to one.

comment:14 in reply to: ↑ 12 Changed 20 months ago by gh-SagnikDey92

Replying to dcoudert:

  • a : is missing
    -        - ``edges`` -- boolean (default ``False``); whether to return the edges
    +        - ``edges`` -- boolean (default: ``False``); whether to return the edges
    

I've corrected this and in several other places as well.

  • excessive indentation.
    +                        if distance is None or d < distance:
    +                                for w in neighbors(v):
    +                                    if w not in seen:
    +                                        queue.append((w, d + 1))
    

Fixed

  • an error to fix
    sage: G = digraphs.Circuit(10)
    sage: list(G.depth_first_search([0], edges=True))
    [(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 7), (7, 8), (8, 9)]
    sage: list(G.depth_first_search([0, 5], edges=True))
    ---------------------------------------------------------------------------
    ValueError                                Traceback (most recent call last)
    <ipython-input-3-7e9a0ee8fcbe> in <module>()
    ----> 1 list(G.depth_first_search([Integer(0), Integer(5)], edges=True))
    
    /Users/dcoudert/sage/local/lib/python3.7/site-packages/sage/graphs/generic_graph.py in depth_first_search(self, start, ignore_direction, distance, neighbors, edges)
      17812                 queue.append((None, v, d))
      17813                 while queue:
    > 17814                     v, w, d = queue.pop()
      17815                     if w not in seen:
      17816                         if v is not None:
    
    ValueError: not enough values to unpack (expected 3, got 2)
    

fixed

  • and also
    sage: list(G.depth_first_search([], edges=False))
    []
    sage: list(G.depth_first_search([], edges=True))
    ---------------------------------------------------------------------------
    IndexError                                Traceback (most recent call last)
    <ipython-input-5-bd352d9e6783> in <module>()
    ----> 1 list(G.depth_first_search([], edges=True))
    
    /Users/dcoudert/sage/local/lib/python3.7/site-packages/sage/graphs/generic_graph.py in depth_first_search(self, start, ignore_direction, distance, neighbors, edges)
      17809 
      17810             else:
    > 17811                 v, d = queue.pop()
      17812                 queue.append((None, v, d))
      17813                 while queue:
    
    IndexError: pop from empty list
    

fixed Please review

comment:15 Changed 20 months ago by dcoudert

In general, it is better to not touch parts of the code that have nothing to do with the method you are currently modifying. This is to avoid possible conflicts with other tickets. A better approach is to open a dedicated ticket.

Also, you have done partial corrections only like

-        -  ``quotient_matrix`` - (default False) if True, and
+        -  ``quotient_matrix`` - (default: ``False``) if True, and

a better formatting is

+        -  ``quotient_matrix`` -- (default: ``False``); if ``True``, and

Next, a simpler version could be

-                for i in range(len(queue)):
-                    v, d = queue[i]
-                    queue[i] = (None, v, d)
+                queue = [(None, v, d) for v, d in queue]

comment:16 Changed 20 months ago by gh-SagnikDey92

Ok. I'll remove the changes I made to other function documentations and add the simplification you mentioned. Should I open a ticket regarding making the documentation in this file uniform?

comment:17 Changed 20 months ago by gh-SagnikDey92

New commits:

8aa0a70Made minor changes to documentation for uniformity. Fixed errors related to DFS with number of starting vertices not equal to one.

comment:18 Changed 20 months ago by gh-SagnikDey92

New commits:

8aa0a70Made minor changes to documentation for uniformity. Fixed errors related to DFS with number of starting vertices not equal to one.

comment:19 Changed 20 months ago by git

  • Commit changed from 8aa0a709f8bc354e661d8bd65b1f0b645814d458 to 7f13e031a585292ec72faa129d2d79aff415aae8

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

7f13e03Fixed errors related to DFS with number of starting vertices not equal to one. Made minor change to documentation of depth_first_search function to maintain uniformity

comment:20 Changed 20 months ago by gh-SagnikDey92

Sorry about the forced push. Since I wanted to remove the changes made to documentation of other functions, I wanted to revert that and a sage devel forum earlier said to use a force push. Please review

comment:21 Changed 20 months ago by dcoudert

  • you can open a new ticket to unify the documentation. I suggest to name the ticket pep8 cleaning in generic_graph.py (part 15), as we already had several tickets to clean this file. See e.g., #26680, #26679.
  • in this ticket, add the tests of #comment:12 to show that all cases have been considered.

comment:22 Changed 20 months ago by git

  • Commit changed from 7f13e031a585292ec72faa129d2d79aff415aae8 to 04fe5a3f01de8e6976eb25793c212eb026849105

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

04fe5a3Added new tests to demonstrate working in all cases.

comment:23 Changed 20 months ago by gh-SagnikDey92

I've added the tests but I've found a potential bug:

sage: D = DiGraph({1: [2, 3], 3: [4, 6], 4: [6], 5: [4, 7], 6: [7]})
sage: list(D.depth_first_search(1, edges=True))
[(1, 3), (3, 6), (6, 7), (3, 4), (1, 2)]
sage: list(D.depth_first_search([1, 5], edges=True))
[(1, 3), (3, 6), (6, 7), (3, 4), (1, 2)]

Obviously 5 is not getting printed since there is no edge involving 5 even though it is visited. Should't we still somehow indicate that 5 was visited? If so how? As in please suggest some appropriate output for that case and I'll make the necessary changes.

comment:24 follow-up: Changed 20 months ago by dcoudert

What you observed is a normal behavior, so it's OK I guess. The exemple of #comment:12 is with a circuit of order 10, so we should get edges starting from 5. Add this one.

comment:25 in reply to: ↑ 24 Changed 20 months ago by gh-SagnikDey92

Replying to dcoudert:

What you observed is a normal behavior, so it's OK I guess. The exemple of #comment:12 is with a circuit of order 10, so we should get edges starting from 5. Add this one.

I added it in my local repository but I don't see how the output between starting from [0] or from [0, 5] should be any different? It is a circuit so the DFS from 0 just covers every vertex. For checking this case, shouldn't I make a graph with two disjoint trees for a DFS?

Last edited 20 months ago by gh-SagnikDey92 (previous) (diff)

comment:26 follow-up: Changed 20 months ago by dcoudert

Right, you can take G = DiGraph([(0, 1), (1, 2), (3, 4), (4, 5)]), so 2 disjoint paths and start from [0] and [0, 3].

comment:27 Changed 20 months ago by git

  • Commit changed from 04fe5a3f01de8e6976eb25793c212eb026849105 to 31aa806fa7a548a598aa7b270bfd6b589c3a9e81

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

31aa806Added new tests to demonstrate working in all cases.

comment:28 in reply to: ↑ 26 Changed 20 months ago by gh-SagnikDey92

Replying to dcoudert:

Right, you can take G = DiGraph([(0, 1), (1, 2), (3, 4), (4, 5)]), so 2 disjoint paths and start from [0] and [0, 3].

Done. Please review.

comment:29 Changed 20 months ago by dcoudert

  • Milestone set to sage-9.1
  • Reviewers set to David Coudert
  • Status changed from needs_work to positive_review

Please add your full name in the authors field

comment:30 Changed 20 months ago by vbraun

  • Status changed from positive_review to needs_work

comment:31 Changed 20 months ago by gh-SagnikDey92

  • Authors set to Sagnik Dey

I'm not sure why the status changed to needs work again after positive review. Is it because of the author name adding? Or do I need to run all doctests on this before sending PR?

edit: I'll try rebasing with current develop because I got an issue in another ticket.

Last edited 20 months ago by gh-SagnikDey92 (previous) (diff)

comment:32 Changed 20 months ago by gh-SagnikDey92

I just rebased it and ran doctests in src/sage again. 3 error cropped up which I don;t think is related to my change really. Can you please confirm what this is:

File "src/sage/rings/padics/padic_lattice_element.py", line 19, in sage.rings.padics.padic_lattice_element
Failed example:
    R = ZpLF(2) # py3
Expected:
    doctest:...: FutureWarning: This class/method/function is marked as experimental. It, its functionality or its interface might change without a formal deprecation.
    See http://trac.sagemath.org/23505 for details.
Got:
    <BLANKLINE>
**********************************************************************
File "src/sage/rings/padics/padic_lattice_element.py", line 25, in sage.rings.padics.padic_lattice_element
Failed example:
    R = QpLC(2) # py3
Expected:
    doctest:...: FutureWarning: This class/method/function is marked as experimental. It, its functionality or its interface might change without a formal deprecation.
    See http://trac.sagemath.org/23505 for details.
Got:
    <BLANKLINE>
**********************************************************************
File "src/sage/rings/padics/padic_lattice_element.py", line 31, in sage.rings.padics.padic_lattice_element
Failed example:
    R = QpLF(2) # py3
Expected:
    doctest:...: FutureWarning: This class/method/function is marked as experimental. It, its functionality or its interface might change without a formal deprecation.
    See http://trac.sagemath.org/23505 for details.
Got:
    <BLANKLINE>
**********************************************************************
1 item had failures:
   3 of   5 in sage.rings.padics.padic_lattice_element
    [270 tests, 3 failures, 0.61 s]
----------------------------------------------------------------------
sage -t --warn-long 68.1 src/sage/rings/padics/padic_lattice_element.py  # 3 doctests failed
----------------------------------------------------------------------
Total time for all tests: 0.8 seconds
    cpu time: 0.6 seconds
    cumulative wall time: 0.6 seconds

comment:33 Changed 20 months ago by git

  • Commit changed from 31aa806fa7a548a598aa7b270bfd6b589c3a9e81 to f480fd0c0426ef9dbdb02f128ff702c260763880

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

b5e28e1added edges parameter in dfs
7510d95Made the DFS edge returning routine linear from quadratic by separating the cases where vertices and edges are returned
3f2756eFixed errors related to DFS with number of starting vertices not equal to one. Made minor change to documentation of depth_first_search function to maintain uniformity
f480fd0Added new tests to demonstrate working in all cases.

comment:34 follow-up: Changed 20 months ago by dcoudert

  • Status changed from needs_work to needs_review

The error reported in #comment:32 has nothing to do with this ticket. I have it when testing the develop branch of 9.1.beta6. You can open a new ticket to fix it (check first that no ticket has already been open for this purpose), and we will send a message on sage-devel.

I'm setting this ticket to needs review to check if the patchbot reports something.

comment:35 in reply to: ↑ 34 Changed 20 months ago by gh-SagnikDey92

Replying to dcoudert:

The error reported in #comment:32 has nothing to do with this ticket. I have it when testing the develop branch of 9.1.beta6. You can open a new ticket to fix it (check first that no ticket has already been open for this purpose), and we will send a message on sage-devel.

I'm setting this ticket to needs review to check if the patchbot reports something.

I created a new ticket #29272 since I couldn't find any other ticket referencing this (I searched by keyword). Also, I think the patchbot has finished the testing.

comment:36 Changed 20 months ago by dcoudert

  • Status changed from needs_review to positive_review

LGTM

comment:37 Changed 20 months ago by vbraun

  • Branch changed from u/gh-SagnikDey92/return_edges_from_depth_first_search to f480fd0c0426ef9dbdb02f128ff702c260763880
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.