Better grilling with topological sorting

Today I'll just lay out the problem I'm trying to solve, and tomorrow we'll walk through the code to solve our problem.

On a summer weekend, I can't help but listen to the call of the grill. We're in the northern hemisphere here, my apologies to those currently in winter that might feel left out.

One of the things I'm always striving to improve is the rhythm at which I get things off the grill, so there's a good flow of food that minimizes waits but doesn't outpace the diners and lets any item grow cold or dry out.

A first step is figuring out in what order to place things on the grill and prepare other items. Here is a short list of what I had to prepare recently.

• Portobello mushrooms. These were already marinated and had to be grilled for a while.
• Burgers: Yum.
• Bread: I had some that I had baked the day before, and I just wanted to re-heat it in the grill to get it warm and crisp and to give it a bit of smokey flavor.
• Salad: Lettuce, onions and tomatoes, with some vinegar or lemon. Yum.
• Corn: Also to be grilled.
• Charcoal: I have a grill that can prepare the charcoal in two steps. First I light up the gas for about 7 minutes with the charcoal on top, then I turn that off and let the charcoal heat up until it gets a light ash coating, about 25 minutes.

Here is a list of "what things need to be ready before I can start with something".

• gas: nothing
• charcoal: gas
• portobello: charcoal
• burgers: charcoal
• bread: charcoal
• corn: charcoal
• salad: nothing
• serve: portobello, burgers, salad, bread, corn

Now, imagine that this is a graph, where each item is a node, and each dependency is an arc. There is an algorithm that enumerates the nodes in order such that all dependencies appear before their dependant node - a topological sort. We'll look at the code for that tomorrow then.

Enjoy!