Bash: tsort with tie-break
I want to be able to topologically sort a directed graph, but be able to specify the tie-break sort used.
Eg, given:
horse cat
dog cat
elephant cat
cat mouse
mouse snake
dog snake
elephant snake
I would like to sort tie-breaks alphabetically.
tsort gives the following output:
elephant
dog
horse
cat
mouse
snake
I would like:
dog
elephant
horse
cat
mouse
snake
Is there any easy way to force this behaviour? I cannot alter the source list but can manipulate it before applying tsort. The solution must be bash, but I am not wedded to using tsort itself.
bash sorting directed-acyclic-graphs
asked Nov 15 '18 at 14:23
GesarGesar
1037
add a comment |
I want to be able to topologically sort a directed graph, but be able to specify the tie-break sort used.
Eg, given:
horse cat
dog cat
elephant cat
cat mouse
mouse snake
dog snake
elephant snake
I would like to sort tie-breaks alphabetically.
tsort gives the following output:
elephant
dog
horse
cat
mouse
snake
I would like:
dog
elephant
horse
cat
mouse
snake
Is there any easy way to force this behaviour? I cannot alter the source list but can manipulate it before applying tsort. The solution must be bash, but I am not wedded to using tsort itself.
bash sorting directed-acyclic-graphs
asked Nov 15 '18 at 14:23
GesarGesar
1037
add a comment |
I want to be able to topologically sort a directed graph, but be able to specify the tie-break sort used.
Eg, given:
horse cat
dog cat
elephant cat
cat mouse
mouse snake
dog snake
elephant snake
I would like to sort tie-breaks alphabetically.
tsort gives the following output:
elephant
dog
horse
cat
mouse
snake
I would like:
dog
elephant
horse
cat
mouse
snake
Is there any easy way to force this behaviour? I cannot alter the source list but can manipulate it before applying tsort. The solution must be bash, but I am not wedded to using tsort itself.
bash sorting directed-acyclic-graphs
asked Nov 15 '18 at 14:23
GesarGesar
1037
I want to be able to topologically sort a directed graph, but be able to specify the tie-break sort used.
Eg, given:
horse cat
dog cat
elephant cat
cat mouse
mouse snake
dog snake
elephant snake
I would like to sort tie-breaks alphabetically.
tsort gives the following output:
elephant
dog
horse
cat
mouse
snake
I would like:
dog
elephant
horse
cat
mouse
snake
Is there any easy way to force this behaviour? I cannot alter the source list but can manipulate it before applying tsort. The solution must be bash, but I am not wedded to using tsort itself.
bash sorting directed-acyclic-graphs
bash sorting directed-acyclic-graphs
asked Nov 15 '18 at 14:23
GesarGesar
1037
asked Nov 15 '18 at 14:23
GesarGesar
1037
asked Nov 15 '18 at 14:23
GesarGesar
1037
asked Nov 15 '18 at 14:23
GesarGesar
1037
asked Nov 15 '18 at 14:23
GesarGesar
1037
1037
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
I assume you want to sort by name the key pair that would have the same topology order.
In that case, you could simply perform a "standard" sort before tsort.
sort file | tsort
The (GNU) version of tsort I'm using doesn't have an option to do that type of sort.
answered Nov 15 '18 at 14:54
olivoliv
8,4341130
Correct. Is tsort always guaranteed to produce the same output for an alphabetised source list? It seems like it might do that, but by accident rather than design.
– Gesar
Nov 15 '18 at 15:04
I don't know if this is by design, but that's how I used it and so far so good ;-)
– oliv
Nov 15 '18 at 15:11
This isn't guaranteed to work (in fact, it doesn't work when I try it). The original input already listsdog catbeforeelephant cat, butelephantstill appeared beforedogin the output oftsort.
– chepner
Nov 15 '18 at 15:44
add a comment |
Your Answer
StackExchange.ifUsing("editor", function ()
StackExchange.using("externalEditor", function ()
StackExchange.using("snippets", function ()
StackExchange.snippets.init();
);
);
, "code-snippets");
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "1"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
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%2fstackoverflow.com%2fquestions%2f53321557%2fbash-tsort-with-tie-break%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
I assume you want to sort by name the key pair that would have the same topology order.
In that case, you could simply perform a "standard" sort before tsort.
sort file | tsort
The (GNU) version of tsort I'm using doesn't have an option to do that type of sort.
answered Nov 15 '18 at 14:54
olivoliv
8,4341130
Correct. Is tsort always guaranteed to produce the same output for an alphabetised source list? It seems like it might do that, but by accident rather than design.
– Gesar
Nov 15 '18 at 15:04
I don't know if this is by design, but that's how I used it and so far so good ;-)
– oliv
Nov 15 '18 at 15:11
This isn't guaranteed to work (in fact, it doesn't work when I try it). The original input already listsdog catbeforeelephant cat, butelephantstill appeared beforedogin the output oftsort.
– chepner
Nov 15 '18 at 15:44
add a comment |
I assume you want to sort by name the key pair that would have the same topology order.
In that case, you could simply perform a "standard" sort before tsort.
sort file | tsort
The (GNU) version of tsort I'm using doesn't have an option to do that type of sort.
answered Nov 15 '18 at 14:54
olivoliv
8,4341130
Correct. Is tsort always guaranteed to produce the same output for an alphabetised source list? It seems like it might do that, but by accident rather than design.
– Gesar
Nov 15 '18 at 15:04
I don't know if this is by design, but that's how I used it and so far so good ;-)
– oliv
Nov 15 '18 at 15:11
This isn't guaranteed to work (in fact, it doesn't work when I try it). The original input already listsdog catbeforeelephant cat, butelephantstill appeared beforedogin the output oftsort.
– chepner
Nov 15 '18 at 15:44
add a comment |
I assume you want to sort by name the key pair that would have the same topology order.
In that case, you could simply perform a "standard" sort before tsort.
sort file | tsort
The (GNU) version of tsort I'm using doesn't have an option to do that type of sort.
answered Nov 15 '18 at 14:54
olivoliv
8,4341130
I assume you want to sort by name the key pair that would have the same topology order.
In that case, you could simply perform a "standard" sort before tsort.
sort file | tsort
The (GNU) version of tsort I'm using doesn't have an option to do that type of sort.
answered Nov 15 '18 at 14:54
olivoliv
8,4341130
answered Nov 15 '18 at 14:54
olivoliv
8,4341130
answered Nov 15 '18 at 14:54
olivoliv
8,4341130
answered Nov 15 '18 at 14:54
olivoliv
8,4341130
8,4341130
Correct. Is tsort always guaranteed to produce the same output for an alphabetised source list? It seems like it might do that, but by accident rather than design.
– Gesar
Nov 15 '18 at 15:04
I don't know if this is by design, but that's how I used it and so far so good ;-)
– oliv
Nov 15 '18 at 15:11
This isn't guaranteed to work (in fact, it doesn't work when I try it). The original input already listsdog catbeforeelephant cat, butelephantstill appeared beforedogin the output oftsort.
– chepner
Nov 15 '18 at 15:44
add a comment |
Correct. Is tsort always guaranteed to produce the same output for an alphabetised source list? It seems like it might do that, but by accident rather than design.
– Gesar
Nov 15 '18 at 15:04
I don't know if this is by design, but that's how I used it and so far so good ;-)
– oliv
Nov 15 '18 at 15:11
This isn't guaranteed to work (in fact, it doesn't work when I try it). The original input already listsdog catbeforeelephant cat, butelephantstill appeared beforedogin the output oftsort.
– chepner
Nov 15 '18 at 15:44
Correct. Is tsort always guaranteed to produce the same output for an alphabetised source list? It seems like it might do that, but by accident rather than design.
– Gesar
Nov 15 '18 at 15:04
Correct. Is tsort always guaranteed to produce the same output for an alphabetised source list? It seems like it might do that, but by accident rather than design.
– Gesar
Nov 15 '18 at 15:04
I don't know if this is by design, but that's how I used it and so far so good ;-)
– oliv
Nov 15 '18 at 15:11
I don't know if this is by design, but that's how I used it and so far so good ;-)
– oliv
Nov 15 '18 at 15:11
This isn't guaranteed to work (in fact, it doesn't work when I try it). The original input already lists
dog cat before elephant cat, but elephant still appeared before dog in the output of tsort.– chepner
Nov 15 '18 at 15:44
This isn't guaranteed to work (in fact, it doesn't work when I try it). The original input already lists
dog cat before elephant cat, but elephant still appeared before dog in the output of tsort.– chepner
Nov 15 '18 at 15:44
add a comment |
Thanks for contributing an answer to Stack Overflow!
- 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%2fstackoverflow.com%2fquestions%2f53321557%2fbash-tsort-with-tie-break%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
