tsort: -: input contains an odd number of tokens
up vote
2
down vote
favorite
coreutils manual says
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. For example
tsort <<EOF
a b c
d
e f
b c d e
EOF
will produce the output
a
b
c
d
e
f
What does "tsort reads its input as pairs of strings" mean, and what requirements does that put on the input?
In the example, does the first line a b c
mean nothing itself, but a
and b
are paired, and so are c
and d
?
Why does this not work?
$ tsort <<EOF
> a b c
> b c d e
> EOF
tsort: -: input contains an odd number of tokens
sort coreutils tsort
add a comment |
up vote
2
down vote
favorite
coreutils manual says
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. For example
tsort <<EOF
a b c
d
e f
b c d e
EOF
will produce the output
a
b
c
d
e
f
What does "tsort reads its input as pairs of strings" mean, and what requirements does that put on the input?
In the example, does the first line a b c
mean nothing itself, but a
and b
are paired, and so are c
and d
?
Why does this not work?
$ tsort <<EOF
> a b c
> b c d e
> EOF
tsort: -: input contains an odd number of tokens
sort coreutils tsort
add a comment |
up vote
2
down vote
favorite
up vote
2
down vote
favorite
coreutils manual says
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. For example
tsort <<EOF
a b c
d
e f
b c d e
EOF
will produce the output
a
b
c
d
e
f
What does "tsort reads its input as pairs of strings" mean, and what requirements does that put on the input?
In the example, does the first line a b c
mean nothing itself, but a
and b
are paired, and so are c
and d
?
Why does this not work?
$ tsort <<EOF
> a b c
> b c d e
> EOF
tsort: -: input contains an odd number of tokens
sort coreutils tsort
coreutils manual says
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. For example
tsort <<EOF
a b c
d
e f
b c d e
EOF
will produce the output
a
b
c
d
e
f
What does "tsort reads its input as pairs of strings" mean, and what requirements does that put on the input?
In the example, does the first line a b c
mean nothing itself, but a
and b
are paired, and so are c
and d
?
Why does this not work?
$ tsort <<EOF
> a b c
> b c d e
> EOF
tsort: -: input contains an odd number of tokens
sort coreutils tsort
sort coreutils tsort
asked Nov 17 at 15:57
Tim
25.2k72243444
25.2k72243444
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
up vote
7
down vote
tsort
does a topological sorting of a directed graph. It gets the graph as pairs of nodes. These constitute a partial ordering of the graph and tsort
gives you a total ordering as the result (there may be more than one total ordering of the graph though, see the documentation for the -f
and -h
options on BSD systems (not available on GNU systems AFAIK)).
Example of a real graph (these are the OpenBSD packages required to build the shells/bash
package on an OpenBSD system):
$ make -C /usr/ports/shells/bash build-dir-depends
shells/bash devel/ccache
shells/bash devel/gettext
devel/gettext devel/ccache
devel/gettext archivers/xz
archivers/xz devel/ccache
devel/gettext converters/libiconv
converters/libiconv devel/ccache
devel/gettext converters/libiconv
A pair, A B
, in this list means "A
is connected to B
" (in that order, since it's a directed graph), and in the particular case shown here it means "A
depends on B
" (converters/libiconv
needs to be built before devel/gettext
because the latter depends on the former).
tsort
takes the the partial ordering of pairs of nodes and returns a list of nodes in a total ordering compatible with that partial ordering:
$ make -C /usr/ports/shells/bash build-dir-depends | tsort -r
devel/ccache
archivers/xz
converters/libiconv
devel/gettext
shells/bash
Here, I've instructed tsort
to reverse the resulting ordering (not possible on GNU systems as -r
is not an option to GNU tsort
), which gives me the order in which the system needs to build the packages while at the same time honouring the dependencies between them (ending up with building the final shells/bash
package).
If tsort
gets an input line
a b c d
then this is the same as
a b
c d
and as
a b c
d
That is, it always reads the nodes of the graph in pairs, no matter whether these are separated by spaces or newlines. The issue with your data,
a b c
b c d e
is that it can't be read as a list of pairs as it contains an odd number of nodes.
add a comment |
up vote
4
down vote
Yes, tsort reads its inputs in pairs separated by any whitespace, including newlines.
So the example from the tsort documentation:
tsort <<EOF
a b c
d
e f
b c d e
EOF
Defines the following pairs of orderings:
- a < b
- c < d
- e < f
- b < c
- d < e
And putting these all together, you get to a ordering of a < b < c < d < e < f, which in this case is a total ordering.
A reading of the source code confirms that, tsort uses readtoken() from gnulib with a set of delimiters comprised by space, tab and newline, in other words, any whitespace.
(My initial interpretation of that tsort example, to answer your other question, was that a line with b c d e
created three implicit pairs, b < c, c < d and d < e, but that's really not the case, all whitespace is interpreted the same, including newlines, and a single pair is read at a time.)
add a comment |
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
7
down vote
tsort
does a topological sorting of a directed graph. It gets the graph as pairs of nodes. These constitute a partial ordering of the graph and tsort
gives you a total ordering as the result (there may be more than one total ordering of the graph though, see the documentation for the -f
and -h
options on BSD systems (not available on GNU systems AFAIK)).
Example of a real graph (these are the OpenBSD packages required to build the shells/bash
package on an OpenBSD system):
$ make -C /usr/ports/shells/bash build-dir-depends
shells/bash devel/ccache
shells/bash devel/gettext
devel/gettext devel/ccache
devel/gettext archivers/xz
archivers/xz devel/ccache
devel/gettext converters/libiconv
converters/libiconv devel/ccache
devel/gettext converters/libiconv
A pair, A B
, in this list means "A
is connected to B
" (in that order, since it's a directed graph), and in the particular case shown here it means "A
depends on B
" (converters/libiconv
needs to be built before devel/gettext
because the latter depends on the former).
tsort
takes the the partial ordering of pairs of nodes and returns a list of nodes in a total ordering compatible with that partial ordering:
$ make -C /usr/ports/shells/bash build-dir-depends | tsort -r
devel/ccache
archivers/xz
converters/libiconv
devel/gettext
shells/bash
Here, I've instructed tsort
to reverse the resulting ordering (not possible on GNU systems as -r
is not an option to GNU tsort
), which gives me the order in which the system needs to build the packages while at the same time honouring the dependencies between them (ending up with building the final shells/bash
package).
If tsort
gets an input line
a b c d
then this is the same as
a b
c d
and as
a b c
d
That is, it always reads the nodes of the graph in pairs, no matter whether these are separated by spaces or newlines. The issue with your data,
a b c
b c d e
is that it can't be read as a list of pairs as it contains an odd number of nodes.
add a comment |
up vote
7
down vote
tsort
does a topological sorting of a directed graph. It gets the graph as pairs of nodes. These constitute a partial ordering of the graph and tsort
gives you a total ordering as the result (there may be more than one total ordering of the graph though, see the documentation for the -f
and -h
options on BSD systems (not available on GNU systems AFAIK)).
Example of a real graph (these are the OpenBSD packages required to build the shells/bash
package on an OpenBSD system):
$ make -C /usr/ports/shells/bash build-dir-depends
shells/bash devel/ccache
shells/bash devel/gettext
devel/gettext devel/ccache
devel/gettext archivers/xz
archivers/xz devel/ccache
devel/gettext converters/libiconv
converters/libiconv devel/ccache
devel/gettext converters/libiconv
A pair, A B
, in this list means "A
is connected to B
" (in that order, since it's a directed graph), and in the particular case shown here it means "A
depends on B
" (converters/libiconv
needs to be built before devel/gettext
because the latter depends on the former).
tsort
takes the the partial ordering of pairs of nodes and returns a list of nodes in a total ordering compatible with that partial ordering:
$ make -C /usr/ports/shells/bash build-dir-depends | tsort -r
devel/ccache
archivers/xz
converters/libiconv
devel/gettext
shells/bash
Here, I've instructed tsort
to reverse the resulting ordering (not possible on GNU systems as -r
is not an option to GNU tsort
), which gives me the order in which the system needs to build the packages while at the same time honouring the dependencies between them (ending up with building the final shells/bash
package).
If tsort
gets an input line
a b c d
then this is the same as
a b
c d
and as
a b c
d
That is, it always reads the nodes of the graph in pairs, no matter whether these are separated by spaces or newlines. The issue with your data,
a b c
b c d e
is that it can't be read as a list of pairs as it contains an odd number of nodes.
add a comment |
up vote
7
down vote
up vote
7
down vote
tsort
does a topological sorting of a directed graph. It gets the graph as pairs of nodes. These constitute a partial ordering of the graph and tsort
gives you a total ordering as the result (there may be more than one total ordering of the graph though, see the documentation for the -f
and -h
options on BSD systems (not available on GNU systems AFAIK)).
Example of a real graph (these are the OpenBSD packages required to build the shells/bash
package on an OpenBSD system):
$ make -C /usr/ports/shells/bash build-dir-depends
shells/bash devel/ccache
shells/bash devel/gettext
devel/gettext devel/ccache
devel/gettext archivers/xz
archivers/xz devel/ccache
devel/gettext converters/libiconv
converters/libiconv devel/ccache
devel/gettext converters/libiconv
A pair, A B
, in this list means "A
is connected to B
" (in that order, since it's a directed graph), and in the particular case shown here it means "A
depends on B
" (converters/libiconv
needs to be built before devel/gettext
because the latter depends on the former).
tsort
takes the the partial ordering of pairs of nodes and returns a list of nodes in a total ordering compatible with that partial ordering:
$ make -C /usr/ports/shells/bash build-dir-depends | tsort -r
devel/ccache
archivers/xz
converters/libiconv
devel/gettext
shells/bash
Here, I've instructed tsort
to reverse the resulting ordering (not possible on GNU systems as -r
is not an option to GNU tsort
), which gives me the order in which the system needs to build the packages while at the same time honouring the dependencies between them (ending up with building the final shells/bash
package).
If tsort
gets an input line
a b c d
then this is the same as
a b
c d
and as
a b c
d
That is, it always reads the nodes of the graph in pairs, no matter whether these are separated by spaces or newlines. The issue with your data,
a b c
b c d e
is that it can't be read as a list of pairs as it contains an odd number of nodes.
tsort
does a topological sorting of a directed graph. It gets the graph as pairs of nodes. These constitute a partial ordering of the graph and tsort
gives you a total ordering as the result (there may be more than one total ordering of the graph though, see the documentation for the -f
and -h
options on BSD systems (not available on GNU systems AFAIK)).
Example of a real graph (these are the OpenBSD packages required to build the shells/bash
package on an OpenBSD system):
$ make -C /usr/ports/shells/bash build-dir-depends
shells/bash devel/ccache
shells/bash devel/gettext
devel/gettext devel/ccache
devel/gettext archivers/xz
archivers/xz devel/ccache
devel/gettext converters/libiconv
converters/libiconv devel/ccache
devel/gettext converters/libiconv
A pair, A B
, in this list means "A
is connected to B
" (in that order, since it's a directed graph), and in the particular case shown here it means "A
depends on B
" (converters/libiconv
needs to be built before devel/gettext
because the latter depends on the former).
tsort
takes the the partial ordering of pairs of nodes and returns a list of nodes in a total ordering compatible with that partial ordering:
$ make -C /usr/ports/shells/bash build-dir-depends | tsort -r
devel/ccache
archivers/xz
converters/libiconv
devel/gettext
shells/bash
Here, I've instructed tsort
to reverse the resulting ordering (not possible on GNU systems as -r
is not an option to GNU tsort
), which gives me the order in which the system needs to build the packages while at the same time honouring the dependencies between them (ending up with building the final shells/bash
package).
If tsort
gets an input line
a b c d
then this is the same as
a b
c d
and as
a b c
d
That is, it always reads the nodes of the graph in pairs, no matter whether these are separated by spaces or newlines. The issue with your data,
a b c
b c d e
is that it can't be read as a list of pairs as it contains an odd number of nodes.
edited Nov 17 at 19:48
answered Nov 17 at 16:35
Kusalananda
118k16223361
118k16223361
add a comment |
add a comment |
up vote
4
down vote
Yes, tsort reads its inputs in pairs separated by any whitespace, including newlines.
So the example from the tsort documentation:
tsort <<EOF
a b c
d
e f
b c d e
EOF
Defines the following pairs of orderings:
- a < b
- c < d
- e < f
- b < c
- d < e
And putting these all together, you get to a ordering of a < b < c < d < e < f, which in this case is a total ordering.
A reading of the source code confirms that, tsort uses readtoken() from gnulib with a set of delimiters comprised by space, tab and newline, in other words, any whitespace.
(My initial interpretation of that tsort example, to answer your other question, was that a line with b c d e
created three implicit pairs, b < c, c < d and d < e, but that's really not the case, all whitespace is interpreted the same, including newlines, and a single pair is read at a time.)
add a comment |
up vote
4
down vote
Yes, tsort reads its inputs in pairs separated by any whitespace, including newlines.
So the example from the tsort documentation:
tsort <<EOF
a b c
d
e f
b c d e
EOF
Defines the following pairs of orderings:
- a < b
- c < d
- e < f
- b < c
- d < e
And putting these all together, you get to a ordering of a < b < c < d < e < f, which in this case is a total ordering.
A reading of the source code confirms that, tsort uses readtoken() from gnulib with a set of delimiters comprised by space, tab and newline, in other words, any whitespace.
(My initial interpretation of that tsort example, to answer your other question, was that a line with b c d e
created three implicit pairs, b < c, c < d and d < e, but that's really not the case, all whitespace is interpreted the same, including newlines, and a single pair is read at a time.)
add a comment |
up vote
4
down vote
up vote
4
down vote
Yes, tsort reads its inputs in pairs separated by any whitespace, including newlines.
So the example from the tsort documentation:
tsort <<EOF
a b c
d
e f
b c d e
EOF
Defines the following pairs of orderings:
- a < b
- c < d
- e < f
- b < c
- d < e
And putting these all together, you get to a ordering of a < b < c < d < e < f, which in this case is a total ordering.
A reading of the source code confirms that, tsort uses readtoken() from gnulib with a set of delimiters comprised by space, tab and newline, in other words, any whitespace.
(My initial interpretation of that tsort example, to answer your other question, was that a line with b c d e
created three implicit pairs, b < c, c < d and d < e, but that's really not the case, all whitespace is interpreted the same, including newlines, and a single pair is read at a time.)
Yes, tsort reads its inputs in pairs separated by any whitespace, including newlines.
So the example from the tsort documentation:
tsort <<EOF
a b c
d
e f
b c d e
EOF
Defines the following pairs of orderings:
- a < b
- c < d
- e < f
- b < c
- d < e
And putting these all together, you get to a ordering of a < b < c < d < e < f, which in this case is a total ordering.
A reading of the source code confirms that, tsort uses readtoken() from gnulib with a set of delimiters comprised by space, tab and newline, in other words, any whitespace.
(My initial interpretation of that tsort example, to answer your other question, was that a line with b c d e
created three implicit pairs, b < c, c < d and d < e, but that's really not the case, all whitespace is interpreted the same, including newlines, and a single pair is read at a time.)
answered Nov 17 at 16:35
Filipe Brandenburger
6,6801732
6,6801732
add a comment |
add a comment |
Thanks for contributing an answer to Unix & Linux Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2funix.stackexchange.com%2fquestions%2f482356%2ftsort-input-contains-an-odd-number-of-tokens%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown