How to do a topological sort from a subset of items from a given graph?

Question

I have the following problem: You are given a todo list, some items of which depend on others. Write a function that takes a subset of those todos and returns an ordered list of all the todos to complete. The given subset contains one or more of these todos.

I have written a topological sort using Kahn's Algorithm, turning the list I'm given into an adjacency list. When I have the ordered list of todos, I start adding them into another array and stop when it contains all of the items in the given subset.

This works, but I feel like it's a little bit clumsy and inefficient since I am doing a sort on the entire list and then returning a truncated version.

Any thoughts on how to make this solution a little more elegant?

Answer 1

Don't think of this as a topological sort. Think of this as "do dependencies first, do not do them twice." Which is simple recursive function as long as we keep track of what we will do, and what has been done.

The following Python solution may make this clearer.

def arrange_tasks(dependencies, todo, in_order=None, done=None):
    if in_order is None:
        in_order = []
    if done is None:
        done = set()

    for item in todo:
        # Do we need to?
        if item not in done:
            # Marking it done first avoids deep recursion on dependency loops!
            done.add(item)
            # Make sure that dependencies happened.
            arrange_tasks(dependencies, dependencies[item], in_order, done)
            # And now this can happen.
            in_order.append(item)
    return in_order

print(arrange_tasks(
    {
        'make a sandwich': ['buy groceries'],
        'buy groceries': ['go to store'],
        'go to store': []
    },
    ['buy groceries']
))