Return edges from Depth_First_Search

[JhaPrajjwal]

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.

Component: graph theory

Author: Sagnik Dey

Branch/Commit: f480fd0

Reviewer: David Coudert

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

[Rithesh17]

comment:1

Can anyone tell me the importance of this requirement?

[JhaPrajjwal]

comment:2

Replying to @Rithesh17:

Can anyone tell me the importance of this requirement?

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

[embray]

comment:3

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).

[akshat1136]

comment:4

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?

[dcoudert]

comment:6

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.

[akshat1136]

Branch: u/gh-akshat1136/return_edges_from_depth_first_search

[akshat1136]

comment:8

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

[akshat1136]

Commit: 1a4a321

[dcoudert]

comment:9

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

[SagnikDey92]

Changed branch from u/gh-akshat1136/return_edges_from_depth_first_search to u/gh-SagnikDey92/return_edges_from_depth_first_search

[SagnikDey92]

comment:11

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:

a179f9a	added edges parameter in dfs
5284000	Merge 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
2b7f6e1	Made the DFS edge returning routine linear from quadratic by separating the cases where vertices and edges are returned

[SagnikDey92]

Changed commit from 1a4a321 to 2b7f6e1

[dcoudert]

comment:12

• 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

[sagetrac-git]

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

8aa0a70

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

[sagetrac-git]

Changed commit from 2b7f6e1 to 8aa0a70

[SagnikDey92]

comment:14

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

[dcoudert]

comment:15

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]

[SagnikDey92]

comment:16

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?

[SagnikDey92]

New commits:

8aa0a70

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

[SagnikDey92]

New commits:

8aa0a70

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

[sagetrac-git]

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

04fe5a3

Added new tests to demonstrate working in all cases.

[SagnikDey92]

comment:23

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.

[dcoudert]

comment:24

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.

[SagnikDey92]

comment:25

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?

[dcoudert]

comment:26

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].

[sagetrac-git]

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

31aa806

Added new tests to demonstrate working in all cases.

[sagetrac-git]

Changed commit from 04fe5a3 to 31aa806

[SagnikDey92]

comment:28

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.

[dcoudert]

Reviewer: David Coudert

[dcoudert]

comment:29

Please add your full name in the authors field

[SagnikDey92]

comment:31

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.

[SagnikDey92]

Author: Sagnik Dey

[SagnikDey92]

comment:32

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

[sagetrac-git]

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

b5e28e1	added edges parameter in dfs
7510d95	Made the DFS edge returning routine linear from quadratic by separating the cases where vertices and edges are returned
3f2756e	Fixed 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
f480fd0	Added new tests to demonstrate working in all cases.

[sagetrac-git]

Changed commit from 31aa806 to f480fd0

[dcoudert]

comment:34

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.

[SagnikDey92]

comment:35

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.

[dcoudert]

comment:36

LGTM

[vbraun]

Changed branch from u/gh-SagnikDey92/return_edges_from_depth_first_search to f480fd0