Take the 2-minute tour ×

Is there a good algorithm for doing a topological sort of a subgraph of a multigraph? More specifically, given a multigraph G and a node n in the graph. Consider the subgraph G' all the nodes reachable from n in G. Is there a good way to find a topological sort of G'? For example

A --> B --> C---\
|     |     |   |
v     v     v   |
D --> E --> F<--/

Given the starting node of B, the subgraph G' is {B,C,E,F} and a valid topological sort would be {B,C,E,F}.

Really, I could just form an entirely new multigraph G' and do a traditional topological sort, but the graphs in my case are really big, so I don't want to copy the memory. It seems to me the difficult part of this setup is that it's hard to look at just the incoming edges to a node since it's not clear a priori whether or not the incoming edge is a part of G' or G\G'. For example, in the above graph, F has three incoming edges E, C, and H, but only the incoming edges from E and C matter in the subgraph G'. Another option would be to do two passes. First, do some sort of search and determine how many incoming edges there are at each node in the subgraph. Then, do a second pass that does a topological sort based on this information. This is a little burdensome due to the multigraph structure, so we'd probably have to color the nodes to make sure that we're not processing some node more than once. In any case, I'm curious if there are better options.

share|improve this question

Your Answer



Browse other questions tagged or ask your own question.