AFAICT the auto-tiering thing is pretty simple: 1) "Compress" the DAG to minimize distance from the root to every other node while maintaining proper dependencies, basically maximal path compression. 2) Classify into tiers based on distance from the root node. This will give you the minimal number of necessary tiers and the nodes in each tier.
I can think of at least one simple way to this: Do a topo-sort and build the tiers iteratively: If the next node in the topo-sorted list is pointed to directly by any node in the current tier, then start a new tier. If it isn't, then simply add to current tier. (With appropriate degenerate cases for the root, etc.)
There may be far better algorithms for doing this, but it's been a few (well, many) years since I took any Graph Theory classes
I can think of at least one simple way to this: Do a topo-sort and build the tiers iteratively: If the next node in the topo-sorted list is pointed to directly by any node in the current tier, then start a new tier. If it isn't, then simply add to current tier. (With appropriate degenerate cases for the root, etc.)
There may be far better algorithms for doing this, but it's been a few (well, many) years since I took any Graph Theory classes
Leave a comment: