bug in depth-first searching

[jasongrout]

Here is a bug in the depth-first searching of a graph:

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

It should be [0, 7, 6, 3, 5, 2, 1, 4].

CC: @rlmill

Component: graph theory

Author: Jason Grout

Reviewer: Robert Miller

Merged: Sage 4.1.1.alpha1

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

[jasongrout]

comment:1

I also added a bunch of features to the graph traversal functions and put in a lot more doctests.

[jasongrout]

Author: Jason Grout

[rlmill]

comment:3

I say you remove the

#        for v,d in queue: 
#            seen.add(v) 

in depth_first_search and everything looks good!

[rlmill]

Reviewer: Robert Miller

[jasongrout]

Attachment: trac-6552-graph-traversal.patch.gz

[jasongrout]

comment:4

Good catch! I deleted those two lines and posted an updated patch. Thanks for reviewing this so fast!

[sagetrac-mvngu]

Merged: sage-4.1.1.alpha0

[sagetrac-mvngu]

comment:7

This will have to wait for Sage 4.1.1.alpha1. Apparently, I accidentally closed this as being merged in 4.1.1.alpha0.

[sagetrac-mvngu]

Changed merged from sage-4.1.1.alpha0 to none

[sagetrac-mvngu]

Merged: Sage 4.1.1.alpha1