Re: tsort 6.9, incorrect output

[Guillaume Bailey]

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

   Here's a simple clarified example:

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

   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
EOF


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

References

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

Guillaume_Bailey.vcf
Description: Vcard