Better grilling with topological sorting - the code

Article
08/04/2010

Yesterday we set out the problem of figuring out the right order in which to prepare items for grilling by establishing dependencies for them. Today we'll look at the code that resolves the order.

We'll write the code abstracting out the elements we work with when possible, just so we can use the code for other purpose some other day. Let's start by having a couple of supporting classes to hold our cooking tasks and their dependencies.

public class Element<T> {
public Element(T value) {
this.Dependencies = new List<Element<T>>();
this.Value = value;
}
public T Value { get; private set; }
public List<Element<T>> Dependencies { get; private set; }
public override string ToString() { return this.Value.ToString(); }
}

public class CookingTask : Element<string> {
public CookingTask(string name) : base(name) {}
}

Next, we'll introduce a Scratch class for the program and write out the Main method, and then we'll fill in the rest of the code as we need to.

public static void Main() {
  var namedElements = new Dictionary<string, CookingTask>();
  foreach (string line in ReadUntilEmpty()) {
    string[] parts = line.Split(':');
    var firstPart = GetOrCreate(parts[0].Trim(), namedElements);
    if (parts.Length > 1) {
      var dependencies = parts[1].Split(" ".ToCharArray(), StringSplitOptions.RemoveEmptyEntries);
      foreach (var item in dependencies) {
        firstPart.Dependencies.Add(GetOrCreate(item.Trim(), namedElements));
      }
    }
  }

  var elements = namedElements.Values;
  foreach (var item in TopologicalSort(elements, e => e.Dependencies.Cast<CookingTask>())) {
    Console.WriteLine("item: " + item);
  }

Console.ReadKey();
}

This method will keep reading lines from the console to create cooking tasks and setting up dependencies between them. There's no error handling here, so watch out! There is a helper ReadUntilEmpty method and a helper GetOrCreate that we use to read from the console and to use a single instance per named item, respectively.

private static CookingTask GetOrCreate(string name, Dictionary<string, CookingTask> dictionary) {
  if (dictionary.ContainsKey(name)) {
    return dictionary[name];
  }

  var result = new CookingTask(name);
  dictionary.Add(name, result);
  return result;
}

public static IEnumerable<string> ReadUntilEmpty() {
  /*
for (; ; ) {
string result = Console.ReadLine().Trim();
if (String.IsNullOrEmpty(result)) yield break;
yield result;
}
*/
  return new string[] {
    "portobello: charcoal",
    "burgers: charcoal",
    "gas",
    "charcoal: gas",
    "salad",
    "bread: charcoal",
    "corn: charcoal",
    "serve: portobello burgers salad bread corn"
  };
}

Note that I've commented out the 'real' ReadUntilEmpty implementation and I'm simply returning some hard-coded lines, to save you the typing when you run the program in case you're following along.

Now comes the tricky bit, implementing TopologicalSort. Our first version will simply delegate to another one that selects an equality comparer that we'll use when we have lookaside collections to figure out whether we've seen a node before or not.

public static IEnumerable<T> TopologicalSort<T>(IEnumerable<T> elements, Func<T, IEnumerable<T>> dependenciesSelector) {
return TopologicalSort(elements, dependenciesSelector, EqualityComparer<T>.Default);
}

Next, the real sorting works as follows: first we'll figure out what the 'roots' are, then when we have that bit of information we'll do the sorting. The 'roots' in this case are those with no incoming edges or arcs (if you're thinking in terms of graph), or those tasks that don't enable anything further (the "last things you'll do" if you're thinking in terms of work).

public static IEnumerable<T> TopologicalSort<T>(
    IEnumerable<T> elements,
    Func<T, IEnumerable<T>> dependenciesSelector,
    IEqualityComparer<T> comparer) {
  return TopologicalSortFromRoots(
    FindRoots(elements, dependenciesSelector, comparer),
    dependenciesSelector,
    comparer);
}

I'm including two implementations of finding roots. The first one works by creating a set of all elements, then removing those that are dependencies for something else. The second does the same thing but instead of constructing the two collections in one go and then doing the subtraction with "ExceptWith", it creates them as it processes the original list.

public static IEnumerable<T> FindRoots<T>(
    IEnumerable<T> elements,
    Func<T, IEnumerable<T>> dependenciesSelector,
    IEqualityComparer<T> comparer) {
/*
HashSet<T> elementsWithNoIncomingEdges = new HashSet<T>(elements);
var elementsWithIncomingEdges = elements.SelectMany(dependenciesSelector).ToList();
elementsWithNoIncomingEdges.ExceptWith(elementsWithIncomingEdges);
return elementsWithNoIncomingEdges;
*/

return elementsWithNoIncomingEdges;
}

Now we the only remaining method to implement is TopologicalSortFromRoots. The way to think about how this works is as follows: starting from the nodes that go 'last', make our way backward by visiting all of their dependencies (recursively), then they can be enumerated.

public static IEnumerable<T> TopologicalSortFromRoots<T>(
    IEnumerable<T> roots,
    Func<T, IEnumerable<T>> dependenciesSelector,
    IEqualityComparer<T> comparer) {
  var visited = new HashSet<T>(comparer);
  var result = new List<T>();
  Action<T> visit = null; // keeps the compiler happy
  visit = new Action<T>((node) => {
    if (visited.Add(node) == false) return;
    foreach (var m in dependenciesSelector(node)) visit(m);
    result.Add(node);
  });

  foreach (var element in roots) {
    visit(element);
    foreach (var item in result) { yield return item; }
    result.Clear();
  }
}

The implementation is a straightforward one where we visit each root recursively, adding each processed element to a result collection, and keeping a 'visited' collection to make sure we don't enumerate twice nodes that are present in more than one chain of dependencies.

So now when you run this program, you'll get this output:

item: gas
item: charcoal
item: portobello
item: burgers
item: salad
item: bread
item: corn
item: serve

And you're ready to start grilling - enjoy!

Better grilling with topological sorting - the code

Additional resources