From mboxrd@z Thu Jan 1 00:00:00 1970 Path: main.gmane.org!not-for-mail From: prj@po.cwru.edu (Paul Jarc) Newsgroups: gmane.lisp.guile.user Subject: Re: sorting by a partial order Date: Wed, 30 Oct 2002 12:12:45 -0500 Organization: What did you have in mind? A short, blunt, human pyramid? Sender: guile-user-admin@gnu.org Message-ID: References: <200210300634.g9U6Yj401336@fcs9.free-comp-shop.com> NNTP-Posting-Host: main.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: main.gmane.org 1036001978 3628 80.91.224.249 (30 Oct 2002 18:19:38 GMT) X-Complaints-To: usenet@main.gmane.org NNTP-Posting-Date: Wed, 30 Oct 2002 18:19:38 +0000 (UTC) Return-path: Original-Received: from monty-python.gnu.org ([199.232.76.173]) by main.gmane.org with esmtp (Exim 3.35 #1 (Debian)) id 186xRG-0000w5-00 for ; Wed, 30 Oct 2002 19:19:34 +0100 Original-Received: from localhost ([127.0.0.1] helo=monty-python.gnu.org) by monty-python.gnu.org with esmtp (Exim 4.10) id 186xQJ-0004xU-00; Wed, 30 Oct 2002 13:18:35 -0500 Original-Received: from list by monty-python.gnu.org with tmda-scanned (Exim 4.10) id 186wOh-0000fe-00 for guile-user@gnu.org; Wed, 30 Oct 2002 12:12:51 -0500 Original-Received: from mail by monty-python.gnu.org with spam-scanned (Exim 4.10) id 186wOd-0000b4-00 for guile-user@gnu.org; Wed, 30 Oct 2002 12:12:49 -0500 Original-Received: from multivac.student.cwru.edu ([129.22.96.25] helo=multivac.cwru.edu) by monty-python.gnu.org with smtp (Exim 4.10) id 186wOc-0000Zu-00 for guile-user@gnu.org; Wed, 30 Oct 2002 12:12:46 -0500 Original-Received: (qmail 28622 invoked by uid 500); 30 Oct 2002 17:13:08 -0000 Original-To: guile-user@gnu.org In-Reply-To: <200210300634.g9U6Yj401336@fcs9.free-comp-shop.com> (Keith Wright's message of "Wed, 30 Oct 2002 01:34:45 -0500") Mail-Copies-To: nobody Mail-Followup-To: guile-user@gnu.org Original-Lines: 40 User-Agent: Gnus/5.090008 (Oort Gnus v0.08) Emacs/21.2 (i686-pc-linux-gnu) Errors-To: guile-user-admin@gnu.org X-BeenThere: guile-user@gnu.org X-Mailman-Version: 2.0.11 Precedence: bulk List-Help: List-Post: List-Subscribe: , List-Id: General Guile related discussions List-Unsubscribe: , List-Archive: Xref: main.gmane.org gmane.lisp.guile.user:1307 X-Report-Spam: http://spam.gmane.org/gmane.lisp.guile.user:1307 Keith Wright wrote: > I don't know what you have been reading, but Paul's use of "poset" Too bad I didn't actually use that word. :) Sorry for the confusion. Maybe it would have been clearer if I explained that my relation means "B depends on A", so in the result A must precede B. This is for a program similar to make. > Knuth, Art of Computer Programming Vol 1, Fundamental Algorithms, 2.2.3 > calls this a topological sort. Thanks, I'll have a look at that. > The algoriths are short, the problem is the form in which the data > is presented and how you need the answer. I can put the data in any form that's convenient while gathering it. For the answer, I need to be able to iterate through all the items in a valid order. Or iterate through them in an arbitrary order, and inserting the result of processing each item at a proper spot into a sorted list, but I guess that amounts to the same thing. > Knuth's algorithm does the topological sort on any set of pairs > which generates the partial order as its transitive closure. Ok, that's almost how I have it right now. Although it's not quite a set of pairs - I have a hash table storing the dependencies, whose keys are items and whose values are smaller hash tables. The keys in a smaller hash table are items which are the dependencies of thecorresponding key in the large hash table. But I can change that if it turns out not to be convenient. > You do need to be able to store a table of size proportional to the > number of pairs of item related by <= and to loop through all items, > is that a problem? Not if it gives a right answer. :) paul _______________________________________________ Guile-user mailing list Guile-user@gnu.org http://mail.gnu.org/mailman/listinfo/guile-user