How to specify root for do-dfs traversal?

[elfprince13]

I'd like to implement a modified topological sort that only builds up the result list from a specified root element. Given that the existing tsort is based on do-dfs, that seems like the obvious route to go, but the documentation is pretty unclear as to how I could specify the starting point for a traversal, so as to exclude vertices which aren't descended from a particular node.

[stchang]

Thanks for the report.

I'm wondering if tsort is the right function to use here? Since you already know the root, would a simple bfs give you what do want?

That being said, it still might be a good idea to add another argument for specifying a starting dfs node. It's currently possible in a roundabout way using the #:order argument, but a cleaner solution would be better. (I won't be able to get to it right away, but I'll leave this issue open in the meantime.)

[elfprince13]

Yeah, I have a DAG representing a partial ordering, and need to be able to flatten it into a list consistent with that partial ordering, but only from the subgraph rooted at a particular node. Obviously one solution would just be to do a full tsort and trim the list to that node, but I'm going to be doing this a lot, and would prefer not to have the extraneous sibling nodes possibly taking up space in the list. I thought about trying to do some hacks with #:order, but suspect that would be quite inefficient.

[elfprince13]

As a concrete example, let's say I have the following relationships.

B -> A
C -> A
D -> A
E -> B
E -> C
F -> D
F -> E

If I want to list the nodes in subgraph rooted at E, sorted consistently with their partial order, then one strategy would be to list out the whole graph, F D E B C A, and then trim it to just E B C A, but since F E B C D A is also a valid topological sort, I could potentially end up with E B C D A, in which D is extraneous.