Summary

wrong sorting example for topological-sort

Metadata

Attachments

Description

As found by "WJ" on comp.lang.scheme:

 (topological-sort
  '((i am)
    (not trying)
    (confuse the)
    (am trying)
    (trying to)
    (am not)
    (trying the)
    (to confuse)
    (the issue))
   eq?)
 
  ===>
 (not i am trying to confuse the issue)
 
 
 The correct output is:
 
 (i am not trying to confuse the issue)

Changes and comments

[2015-04-13 21:34:05 UTC] syn wrote:

This happens because the dependencies of `am` are defined twice, one of them clobbering the others. I think we have three options:

1. Throw an error in that case 2. Document it as undefined behavior 3. Concatenate the dependencies

What do you think would be the most reasonable thing?

[2015-04-13 23:20:56 UTC] syn attached 0001-Fix-1185-Normalize-DAG-passed-to-topological-sort-so.patch (description=Here's the patch implementing option 3 as discussed on IRC.)

[2016-08-25 21:40:27 UTC] sjamaan set difficulty to easy

[2021-04-11 21:25:56 UTC] felix changed status from new to closed

[2021-04-11 21:25:56 UTC] felix set resolution to fixed

[2021-04-11 21:25:56 UTC] felix wrote:

Pushed in b175ce65fe17c0887ed89f070dc4c16ef95d51f9. Note that I had to change one test result which may be a user-visible change, which I consider acceptable as the new order seems more natural.

[2021-04-12 08:48:05 UTC] sjamaan changed milestone from someday to 5.3

[2021-04-17 13:54:35 UTC] mario wrote:

This fix exposed issues in some eggs:

I'm documenting the status of eggs here so that we don't duplicate work.