How to find all results of topological sorting

Question

Since the results in topological sorting are not unique, there are other reasonable results. I have some relations like a->b b->c... etc. These relations are parts of a graph. I need to find all lists between root and destination(just one destination). Let root n, and destination i.

n-a-b-i

n-a-d-i

n-c-b-i

n-c-d-i

I thought i can reach these results using topological sorting but how? Thanks in advance.

Answer 1

You shouldn't need topological sorting. Just use either breadth-first search or depth-first search from the root and store all paths that end at the destination.

Example pseudocode DFS:

paths_to_destination = []

def dfs_store_destination(node, dest, path=None):
    if path is None:
         path = []

    Append node to path

    if node == dest:
        Add path to paths_to_destination
    else:
        for new_node in node.reachable_nodes:
            dfs_store_destination(new_node, dest, path)

    Remove node from path

dfs_store_destination(root, my_dest)