Re: sorting by a partial order

[Paul Jarc]

Keith Wright <address@hidden> 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