[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: RPG@SAIL.STANFORD.EDU*Subject*: Re: Last-Visited Preorder*From*: Danny Bobrow <Bobrow.pa@Xerox.COM>*Date*: 29 Jan 87 09:11 PST*Cc*: common-lisp-object-system@SAIL.STANFORD.EDU*In-reply-to*: Dick Gabriel <RPG@SAIL.STANFORD.EDU>'s message of 28 Jan 87 19:22 PST*Sender*: 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

- Prev by Date:
**Re: Progress is Our Most Important Problem** - Next by Date:
**changes made to documentation** - Previous by thread:
**Last-Visited Preorder** - Next by thread:
**Progress is Our Most Important Problem** - Index(es):