Opened 3 years ago

Last modified 15 months ago

#1185 new defect

wrong sorting example for topological-sort

Reported by: ckeen Owned by:
Priority: major Milestone: someday
Component: core libraries Version: 4.9.x
Keywords: Cc:
Estimated difficulty: easy

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)

Attachments (1)

0001-Fix-1185-Normalize-DAG-passed-to-topological-sort-so.patch (1.7 KB) - added by syn 3 years ago.
Here's the patch implementing option 3 as discussed on IRC.

Download all attachments as: .zip

Change History (3)

comment:1 Changed 3 years ago by syn

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?

Changed 3 years ago by syn

Here's the patch implementing option 3 as discussed on IRC.

comment:2 Changed 15 months ago by sjamaan

  • Estimated difficulty set to easy
Note: See TracTickets for help on using tickets.