Opened 8 years ago

Closed 7 years ago

#11950 closed defect (fixed)

Bug in topological_sort

Reported by: andrejv Owned by: jason, ncohen, rlm
Priority: major Milestone: sage-4.8
Component: graph theory Keywords:
Cc: Merged in: sage-4.8.alpha5
Authors: Nathann Cohen Reviewers: David Coudert
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description

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]

Attachments (1)

trac_11950.patch (6.1 KB) - added by ncohen 8 years ago.

Download all attachments as: .zip

Change History (7)

comment:1 Changed 8 years ago by ncohen

  • Status changed from new to needs_review

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

Changed 8 years ago by ncohen

comment:2 Changed 8 years ago by jdemeyer

  • Milestone sage-4.7.3 deleted

Milestone sage-4.7.3 deleted

comment:3 Changed 7 years ago by dcoudert

  • Milestone set to sage-4.8
  • Reviewers set to David Coudert
  • Status changed from needs_review to positive_review

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.

comment:4 Changed 7 years ago by ncohen

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

Nathann

comment:5 Changed 7 years ago by jdemeyer

  • Authors set to Nathann Cohen

comment:6 Changed 7 years ago by jdemeyer

  • Merged in set to sage-4.8.alpha5
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.