Revenge of The Cycle Detector

Revenge of The Cycle Detector

  • Comments 3

Mike Schinkel takes even longer to get to the point than I do, and that's saying something!  Mike tells a long story about another application of partial order sorts, and asks how to modify the partial order sort algorithm so that it has a new property.  Namely, in addition to returning a list ordered such that every item comes after all of its precursors, he wants the list to be ordered so that the set of all the "no precursor" items happen first, and then the set of everything that depends only on that first set happens next, and so on.

Why's that?  Because then each set can be done entirely in parallel -- all the items in each set don't depend on each other, and so if you have multiple processors, you can assign a different processor to each item in the current set and be guaranteed that you'll still do everything in a good order.  That is, do all of the first set in parallel, then all of the second set in parallel, and so on.  (This isn't the best possible processor scheduling algorithm for this class of problems, but it's pretty decent.  Exercise for the reader: improve it!)

The trick here is to define the "height" of a node as the length of the longest chain of child dependencies you can make that include it.  Clearly all of the "height one" nodes -- the ones with only themselves on the chain of child dependencies because they have no children -- can be done in parallel.  All of the "height two" nodes -- that only have "height one" children -- can be done in parallel once the height one nodes are done, and so on.

This gives us a straightforward way to compute the height -- the height is one if you have no children, otherwise it is one plus the height of your tallest child.

var unknown = 0;
var undead = -1;
function topoSort(dependencies)
{
  var height = [];
  var list = [];
  for (var dependency in dependencies)
    height[dependency] = unknown; 
  for (var dependency in dependencies)
    visit(dependencies, dependency, list, height);
  return list;
}

function visit(dependencies, dependency, list, height)

  if (height[dependency] == undead)
    throw "Hey, you've got a cycle in dependency " + dependency;
  if (height[dependency] != unknown)
    return height[dependency];
  var max = 0;
  height[dependency] = undead;
  for (var child in dependencies[dependency])
  {
    var childheight = visit(dependencies, dependencies[dependency][child], list, height); 
    if (childheight > max)
      max = childheight;
  }
  height[dependency] = max + 1;
  if (typeof(list[max + 1]) == "undefined")
    list[max + 1] = [];
  list[max + 1].push(dependency);
  return max + 1;
}

print(topoSort(deps).join("\n"));

Which produces

tophat,shirt,socks,underpants,gloves
bowtie,vest,trousers,cufflinks
pocketwatch,shoes,tailcoat

Which is still not the order in which I'd normally dress, but again, it would work.

  • Another use for this revised algorithm is when you want to lay out a dependency graph on a plane. You would then do a topological sort, then put all the height 0 nodes on the first line, height 1 nodes on a line below, and so on. This layout then minimizes the vertical space occupied.

    Of course, this is not necessary the nicest layout possible, as (1) you also try to minimize edge intersections, and (2) if the plane is not infinite, it would be better to try to fit everything in a given width.
  • >> Mike Schinkel takes even longer to get to the point than I do, and that's saying something!

    Hey, watch it!!! :)
  • (I know it's an old post, but I just found it for the first time)

    I needed to implement a partial order a while back and I implemented it a bit differently.

    I had a  queue of items I need to push, a hash set of values I returned already and the dependency array

    Then I had the following simple loop:

    public IEnumerable<Item> Sort(Dictionary<Item, HashSet<Item>> dependencyGraph) {

      Queue<Item> queue = new Queue<Item>(dependencyGraph.Keys);

      HashSet<Item> returned = new HashSet<Item>();

      while (queue.Count > 0) {

         Item item = queue.Dequeue();

         HashSet<Item> deps = dependencyGraph[item];

         deps.ExceptWith(returned);

         if (deps.Count == 0) {

            // no more dependencies!

            yield return item;

            returned.Add(item);

         } else {

            // retry later after we've returned other stuff

            queue. Enqueue(item);

         }

      }

    }

    What do you think of this algorithm? Note that cycle detection was done as part of an earlier stage anyway so I wasn't worried about it at all.

Page 1 of 1 (3 items)