Bug in topological_sort

[andrejv]

There is a bug in topological_sort for digraphs:

sage: D = DiGraph('IR??C?G?OOAOGc@??o')
sage: D.topological_sort()
[0, 1, 4, 9, 6, 7, 5, 8, 3, 2, 1]

A correct answer is returned from networkx:

sage: D.topological_sort(implementation="NetworkX")
[0, 4, 9, 6, 7, 5, 8, 3, 2, 1]

[ncohen]

For the story, I stared at this algorithm for 50 minutes thinking it was returning a wrong ordering (I must have misread the ordering when first checking), to end up convinced that the orderings returned *HAD* to be valid.

Only then I noticed that the problem lied in some vertices being returned twice. The fix was easy : once you have said that a vertex needs to be deactivated *DO NOT CONSIDER IT EVER AGAIN*. The fix lies in the lines :

                # This vertex may have been deactivated since we added it.                                                                                                                                                                    
                if bitset_not_in(activated, u):                                                                                                                                                                                               
                    stack.pop(-1)                                                                                                                                                                                                             
                    continue  

But I modified the code in some other places to make it clearer, and added some documentation. Sorry for that :-) !

Nathann

[jdemeyer]

Milestone sage-4.7.3 deleted

[dcoudert]

I have no problem for installing the patch and for building the documentation.

I did several trials on several randomly generated DAGs, and the results of D.topological_sort() and D.topological_sort(implementation="NetworkX") are the same.

I give a positive review.

Thank you. David.

[ncohen]

Wouhouuuuuu !! Thanks !! So many of my patches are getting reviewed that I should begin to write new ones ! :-D

Nathann