Opened 8 years ago
Closed 8 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)
Change History (7)
comment:1 Changed 8 years ago by
- Status changed from new to needs_review
Changed 8 years ago by
comment:3 Changed 8 years ago by
- 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 8 years ago by
Wouhouuuuuu !! Thanks !! So many of my patches are getting reviewed that I should begin to write new ones ! :-D
Nathann
comment:5 Changed 8 years ago by
comment:6 Changed 8 years ago by
- 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.
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 :
But I modified the code in some other places to make it clearer, and added some documentation. Sorry for that
:-)
!Nathann