[Top][All Lists]

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

Re: let's beef up the tsort info page

From: Russ Allbery
Subject: Re: let's beef up the tsort info page
Date: Mon, 04 Feb 2002 14:03:41 -0800
User-agent: Gnus/5.090005 (Oort Gnus v0.05) XEmacs/21.4 (Common Lisp, sparc-sun-solaris2.6)

[ Posted and mailed. ]

Dan Jacobson <address@hidden> writes:

> |`tsort': Topological sort
> |=========================
> |
> |   `tsort' performs a topological sort on the given FILE, or standard
> |input if no input file is given or for a FILE of `-'.  Synopsis:

> Topological sort?  sounds kinky.  Wait, I see a sort of
> example/explanation below...

Yeah, that part leaves a bit to be desired.  This bit, on the other hand:

> |     tsort [OPTION] [FILE]
> |
> |   `tsort' reads its input as pairs of strings, separated by blanks,
> |indicating a partial ordering.  The output is a total ordering that
> |corresponds to the given partial ordering.

is sufficient if one understands what a partial order and a total order

A better example would be good, one where a topological sort doesn't
result in the same outcome as a lexicographic sort.

> Conclusion: if you guys were to add a little introduction to what this
> stuff is all about, then maybe many more folks could get a handle on it.

My impression of tsort has always been that if you don't understand the
explanation of what it does, you probably don't need to use it.  It's
relatively rare that one needs to do what tsort does.

Here's an attempt at an explanation:

    tsort takes as input a set of rules that specify partial orders
    between strings.  For those unfamiliar with partial orders, think
    of it as a dependency or constraint on the final output.  For
    example, the following partial order:

        bar foo

    just says "bar has to appear before foo."  tsort comes up with a
    total ordering of all strings that satisfies all of the individual
    partial orderings; in other words, if the above was one of the
    input rules, tsort will make sure that in the output bar will come
    before foo.

    For example, if given:

        foo baz
        bar foo

    tsort will determine that the only allowable total ordering would be:


    since any other ordering would violate one of those partial orders,
    and therefore will output that ordering.

    tsort will warn about and then break cycles in the ordering, such as:

        foo bar
        bar foo

    (which is an impossible-to-satisfy constraint saying that foo must
    appear before bar and bar must appear before foo).

Russ Allbery (address@hidden)             <http://www.eyrie.org/~eagle/>

reply via email to

[Prev in Thread] Current Thread [Next in Thread]