Elaboration on the Non-intuitiveness of New Flavors Algorithm...

[David A. Moon <Moon@STONY-BROOK.SCRC.Symbolics.COM>]

I agree with your [Dick's] analysis of the behavior of the New Flavors
algorithm.  This funny behavior when multiple passes are required is the
same thing that has been bothering me.  The New Flavors algorithm produces
an "intuitive" result in many cases, but in this complex case it loses.

I think we are likely to support some variant of the Gabriel or Bobrow
proposed algorithms instead; so far the Bobrow one seems to produce the
most consistently intuitive results.  I fixed its performance problem
that I mentioned yesterday by changing compute-must-precedes-closure;
in place of
  (pushnew precede closure)
  (walk precede (cons element path))
do
  (unless (member precede closure)
    (push precede closure)
    (walk precede (cons element path)))
The case that I gave up on after waiting a minute takes 0.23 seconds
now, just about the same as the others (although Bobrow conses 3 times
as much).  None of the algorithms I've been comparing have been coded
with speed paramount.  I don't know whether the Bobrow algorithm is easy
to explain, though.

I also tried a variant of the Bobrow algorithm where the initial
elimination of duplicates preserves the first occurrence of each
class instead of the last.  It's interesting but not really better.

I don't think any topological sort tie-breaker based on non-local
considerations such as preorder or postorder treewalk is going to
produce intuitive results in all cases, because intuition depends on
local considerations.  I've been trying various tie-breakers but
no good results yet.  The advantage of the Bobrow algorithm is that
it is preorder when that works, and when it doesn't, it moves things
the minimum distance required to make them work.  It usually produces
the same result as the Gabriel-postorder algorithm, but
here is an example that shows that the last-visit disambiguation of
topological sort is not the same as the Bobrow-Kiczales algorithm.

(DEFCLASS A (B C D E F))
(DEFCLASS B (F X))
(DEFCLASS C (F Y))
(DEFCLASS D (F X))
(DEFCLASS E ())
(DEFCLASS F ())
(DEFCLASS X ())
(DEFCLASS Y ())

Flavors, Gabriel-pre, Bobrow produce A B C D E F X Y
Gabriel-post produces A B C D E F Y X
It's hard to say which is intuitive in this case, so I mention this
example only to show that Bobrow and Gabriel-post are not equivalent.

I want to continue thinking about a better tie-breaker for
topological sort.