[Top][All Lists]

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

Re: tsort 6.9, incorrect output

From: Guillaume Bailey
Subject: Re: tsort 6.9, incorrect output
Date: Thu, 24 Apr 2008 16:30:23 -0500
User-agent: Thunderbird (X11/20080213)

   Ah, I see now. I suggest a different example in the info page, since:
     * the example doesn't prevent my misunderstanding (it evaluates the same
       either way)
     * topological sorts are part of graph theory; I was trying to give a
       topological ordering to a 'dot' graph file, by simply removing the '->'
       arrows. There's a superficial similarity between the example and a dot

   Here's a simple clarified example:

        For example
          tsort <<EOF
          c d
          e f
          b d c e
     will be evaluated as the partial order pairs:
          (a, b)
          (c, d)
          (e, f)
          (b, d)
          (c, e)
     and will produce the output

   Jim Meyering wrote:

Guillaume Bailey [1]<address@hidden> wrote:

I have an example of the latest tsort producing invalid output. The

6.9 is over two years old.
The latest coreutils release is coreutils-6.11.

output clearly disobeys the partial ordering 'i k a h g j', because
a' precedes both 'i' and 'k'. There may be other errors.


address@hidden toolDependencies]$ tsort << EOF

b k
b m
k m f
i b f
i k a h g j
b g c
h c
g d
h d
h e
h j l
c l

Thanks for the report, but you have misunderstood
tsort's input format.  From "info tsort",

       `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.

Note the "as pairs of strings".
The placement of newline characters is irrelevant.
So the input above is equivalent to this:

  b k b m k m f i b f i k a h g j b g c h c g d h d h e h j l c l

and this:

  b k
  b m
  k m
  f i
  b f
  i k
  a h
  g j
  b g
  c h
  c g
  d h
  d h
  e h
  j l
  c l


        Guillaume Bailey
        Software Engineer II
        Lymba Corporation
        1701 N. Collins Blvd. Ste. 3000
        Richardson, TX 75080
        Phone: +1 972 680 0800 ext. 105
        Fax:   +1 972 680 0808
        Cell:  +1 214 502 5664
        AIM:   GuillaumeLCC
        MSN:   address@hidden


   1. mailto:address@hidden
   2. mailto:address@hidden
   3. mailto:address@hidden

Attachment: Guillaume_Bailey.vcf
Description: Vcard

reply via email to

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