Re: Last-Visited Preorder

[Danny Bobrow <Bobrow.pa@Xerox.COM>]

    If we decide the last-visited preorder is what we want for a
    tiebreaker, then there is a simple linear way to compute it without
    having to wonder whether reversed reversed postorder is the same as
    last-visited preorder.

    For every class you keep track of the in-degree with respect to
    the sublattice of interest; the in-degree is the number of direct
    subclasses of a class. When you walk from the class of interest,
    you keep track of how many times you've visited that class. When
    you have visited it the same number of times as its in-degree, you
    can walk from that class. The exception is the class of interest,
    which you will visit once more than its in-degree (you visit it
    once and its in-degree is 0).


There is a very simple double recursive program that does the same thing
without keeping track of in-degrees.

(DEFUN LAST-VISIT-ORDER (LAMBDA (C)  (LV1 C NIL))

(DEFUN LV1 (C L) 
   (IF (MEMQ C L)
       L
       (LET ((S (DIRECT-SUPERS C)))
            (PUSHNEW C
               (IF (NULL S) L (LV2 S L)))))

(DEFUN LV2 (S L)
   (LV1 (CAR S)
        (IF (NULL (CDR S)) L (LV2 (CDR S) L))))



  danny